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.
Done