Lower Bounds for Linear Decision Lists

01/17/2019
by   Arkadev Chattopadhyay, et al.
0

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 ∘ XOR requires size 2^0.18 n. This completely answers an open question of Turán and Vatan [FoCM'97]. We also show that the spectral classes PL_1, PL_∞, and the polynomial threshold function classes PT_1, PT_1, are incomparable to linear decision lists.

READ FULL TEXT

Please sign up or login with your details

Forgot password? Click here to reset