Volume 2020

Lower bounds for linear decision lists

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

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

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

and

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

May 30, 2020

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)