Chicago Journal of Theoretical Computer Science

Volume 2020

Article 1

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

Lower bounds for linear decision lists

Arkadev Chattopadhyay
Tata Institute of Fundamental Research
Mumbai, India
arkadev DOT c AT tifr DOT res DOT in

Meena Mahajan
The Institute of Mathematical Sciences
Chennai, India
meena AT imsc DOT res DOT in

Nikhil Mande
Georgetown University
Washington, DC
nikhil DOT mande AT georgetown DOT edu


Nitin Saurabh
Technion -- I.I.T
Haifa, Israel
nitinsau AT cs DOT technion DOT ac DOT il

May 30, 2020


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.

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

DOI: 10.4086/cjtcs.2020.001

[] Volume 2019, Article 3 [] Article 2
[back] Volume 2020 [back] Published articles
[CJCTS home]