Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR19-007 | 17th January 2019 18:32

Lower Bounds for Linear Decision Lists

RSS-Feed




TR19-007
Authors: Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, Nitin Saurabh
Publication: 17th January 2019 18:40
Downloads: 935
Keywords: 


Abstract:

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 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.



ISSN 1433-8092 | Imprint