Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR19-007 | 17th January 2019 18:32

#### Lower Bounds for Linear Decision Lists

TR19-007
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 completely answers an open question of Tur{\'a}n and Vatan [FoCM'97]. We also show that the spectral classes $PL_1, PL_\infty$, and the polynomial threshold function classes $\widehat{PT}_1, PT_1$, are incomparable to linear decision lists.