Loading...
Please wait, while we are loading the content...
Similar Documents
Learning DNF in Time 2 Õ ( n 1 / 3 )
| Content Provider | Semantic Scholar |
|---|---|
| Author | Klivans, Adam R. |
| Copyright Year | 2001 |
| Abstract | Using techniques from learning theory, we show that any s-term DNF over n variables can be computed by a polynomial threshold function of degree O(n log s). This upper bound matches, up to a logarithmic factor, the longstanding lower bound given by Minsky and Papert in their 1968 book Perceptrons. As a consequence of this upper bound we obtain the fastest known algorithm for learning polynomial size DNF, one of the central problems in computational learning theory. Supported in part by NSF grant CCR-97-01304. Supported in part by NSF grant CCR-95-04436 and by NSF grant CCR-98-77049. |
| File Format | PDF HTM / HTML |
| Alternate Webpage(s) | http://www.cs.columbia.edu/~rocco/Public/dnfjcss.pdf |
| Alternate Webpage(s) | http://www1.cs.columbia.edu/~rocco/Public/dnfjcss.pdf |
| Alternate Webpage(s) | http://www.deas.harvard.edu/~rocco/Public/dnf.ps |
| Language | English |
| Access Restriction | Open |
| Content Type | Text |
| Resource Type | Article |
