Abstract:
We consider functions computable efficiently by "linear decision lists", which are decision lists where the queries are linear threshold functions.
We observe that an argument of Turan and Vatan shows that functions efficiently computable by linear decision lists must have large monochromatic rectangles. We then use this fact to prove an exponential lower bound for the size of any linear decision list computing MAJ o XOR, completely resolving an open question posed by Turan and Vatan.
No background will be assumed.
Based on joint work with Arkadev Chattopadhyay, Meena Mahajan and Nitin Saurabh
