Talks
Fall 2018

Locating Linear Decision Lists within TC^0
Tuesday, September 11th, 2018, 4:30 pm–5:00 pm
Event:
Speaker:
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.
Attachment | Size |
---|---|
![]() | 976.9 KB |