Computer Science/Discrete Mathematics Seminar I

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.