Skip to content (access key 's')
Logo of Technion
Logo of CS Department
Logo of CS4People

The Taub Faculty of Computer Science Events and Talks

Theory Seminar: Toward the KRW conjecture: Cubic Lower Bounds via Communication Complexity
event speaker icon
Or Meir (Haifa University)
event date icon
Wednesday, 30.03.2016, 12:30
event location icon
Taub 201
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 Hastad, our proof seems to be more generalizable for other cases.