Thursday, August 30 2018
11:30 - 13:00

Room 327

Locating Linear Decision Lists within TC^0

Meena Mahajan


The frontier of known circuit lower bounds is at depth-2 circuits with
linear threshold functions at each gate. This talk surveys the
landscape below these circuits - the low-depth threshold hierarchy -
and presents one new result concerning decision lists, obtained
jointly with Arkadev Chattopadhyay, Nikhil Mande and Nitin Saurabh.

Download as iCalendar