Lower Bounds for Linear Decision Lists

Arkadev Chattopadhyay, Meena Mahajan, Nikhil Mande +1

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 prov…