Fall 2018

Locating Linear Decision Lists within TC^0

Tuesday, September 11th, 2018 4:30 pm5:00 pm

Add to Calendar


Meena Mahajan (Institute of Mathematical Sciences)

Polynomial-size depth-2 circuits with linear threshold functions at each gate lie at the frontier of known circuit lower bounds. In this talk I will briefly survey the landscape below these circuits - the very-low-depth threshold hierarchy - and present one new result concerning decision lists, obtained jointly with Arkadev Chattopadhyay, Nikhil Mande and Nitin Saurabh. I will also describe a (somewhat related) question from proof complexity.