Or Meir: Toward the KRW conjecture: Cubic lower bounds via communication complexity
Tid: Må 2018-05-21 kl 12.00
Plats: Room 4523, Lindstedtsvägen 5, KTH
Medverkande: Or Meir, University of Haifa
PRACTICALITIES
Lunch is served at 12:00 noon (register at tinyurl.com/TCS180521 at the latest the Saturday before, but preferably earlier). The presentation starts at 12:10 pm and ends at 1 pm. Those of us who wish reconvene after a short break for 1½-2 hours of more technical discussions.
ABSTRACT
One of the major challenges of the research in circuit complexity is proving super-polynomial lower bounds for de-Morgan formulas. Karchmer, Raz, and Wigderson suggested to approach this problem by proving that formula complexity behaves "as expected" with respect to the composition of functions. They showed that this conjecture, if proved, would imply super-polynomial formula lower bounds.
In this talk, I will present the background on this conjecture and the known results. I will then describe a new proof of the special case where the inner function is the parity function. While this special case was already known to follow from a work of Håstad, our proof seems to be more generalizable for other cases.