Lower bounds for linear decision lists

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 thefunction MAJ ◦ XOR requires size 20.18n. This completely answers an open question of Turán and Vatan [19]. We also show that the spectral classes PL1,PL∞, and the polynomialthreshold function classes PTc1,PT1, are incomparable to linear decision lists.