Event calendar file
School of Technology and Computer Science Seminars
On the Weakness of Linear Decision Lists
by Nikhil S. Mande (School of Technology and Computer Science)
Friday, July 20, 2018
from
to
(Asia/Kolkata)
at A-201 (STCS Seminar Room)
at A-201 (STCS Seminar Room)
| Description |
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 |
