Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Decision lists:
TR12-056 | 1st May 2012
Rocco Servedio, Li-Yang Tan, Justin Thaler

Attribute-Efficient Learning and Weight-Degree Tradeoffs for Polynomial Threshold Functions

Revisions: 1

We study the challenging problem of learning decision lists attribute-efficiently, giving both positive and negative results.

Our main positive result is a new tradeoff between the running time and mistake bound for learning length-$k$ decision lists over $n$ Boolean variables. When the allowed running time is relatively high, our new ... more >>>

ISSN 1433-8092 | Imprint