Toward the KRW conjecture: cubic lower bounds via communication complexity

Computer Science/Discrete Mathematics Seminar I
Topic:Toward the KRW conjecture: cubic lower bounds via communication complexity
Speaker:Or Meir
Affiliation:University of Haifa
Date:Monday, December 14
Time/Room:11:15am - 12:15pm/S-101
Video Link:https://video.ias.edu/csdm/2015/1214-Meir

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.