Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > DECISION LISTS:
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 >>>

TR19-007 | 17th January 2019
Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, Nitin Saurabh

#### Lower Bounds for Linear Decision Lists

We demonstrate a lower bound technique for linear decision lists, which are decision lists where the queries are arbitrary linear threshold functions.
We use this technique to prove an explicit lower bound by showing that any linear decision list computing the function \$MAJ \circ XOR\$ requires size \$2^{0.18 n}\$. This ... more >>>

TR19-137 | 24th September 2019
Shachar Lovett, Kewen Wu, Jiapeng Zhang

#### Decision list compression by mild random restrictions

Revisions: 1

A decision list is an ordered list of rules. Each rule is specified by a term, which is a conjunction of literals, and a value. Given an input, the output of a decision list is the value corresponding to the first rule whole term is satisfied by the input. Decision ... more >>>

TR23-012 | 16th February 2023
Yogesh Dahiya, Vignesh K, Meena Mahajan, Karteek Sreenivasaiah

#### Linear threshold functions in decision lists, decision trees, and depth-2 circuits

We show that polynomial-size constant-rank linear decision trees (LDTs) can be converted to polynomial-size depth-2 threshold circuits LTF\$\circ\$LTF. An intermediate construct is polynomial-size decision lists that query a conjunction of a constant number of linear threshold functions (LTFs); we show that these are equivalent to polynomial-size exact linear decision lists ... more >>>

ISSN 1433-8092 | Imprint