Room 327

Locating Linear Decision Lists within TC^0

Meena Mahajan

IMSc

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.