Published by the Department of Computer Science, The University of Chicago.

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án and Vatan. We also show that the spectral classes $PL_1, PL_\infty$, and the polynomial threshold function classes PT$_1, PT_1$, are incomparable to linear decision lists.

• The article: PDF (284 KB)
• Source material: ZIP (71 KB)
• BibTeX entry for this article (304 bytes)

Submitted Submitted April 20,2019, revised May 5, 2020,published May 30, 2020.

© 2020 Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande, and Nitin Saurabh
Licensed under a Creative Commons Attribution License

Volume 2019, Article 3

Article 2

Volume 2020

Published articles