Title: Can Every Sequential Computation be Efficiently Parallelized? (or, towards the KRW conjecture on composing Boolean functions)
Speaker: Avi Wigderson, IAS
Date: Wednesday, February 5, 2014 11:00-12:00pm
Location: CoRE Bldg, Room 301A, Rutgers University, Busch Campus, Piscataway, NJ
Abstract:
One of the major open problems in complexity theory is proving explicit super-polynomial lower bounds for Boolean formulas (sometimes called the "P vs. NC1" problem). This problem essentially captures the power of parallel computation and of small-space computation.
20 years ago Karchmer, Raz, and Wigderson showed that such lower bounds will follow from the following conjecture: for any two Boolean functions f and g, the depth complexity of their composition is roughly the sum of the individual depth of each. Moreover, using the equivalence of circuit depth and communication complexity of Karchmer-Wigderson games, they suggested a path towards proving this conjecture through a series of communication lower bounds.
The first step in this path was achieved soon afterwards by Edmonds, Impagliazzo, Rudich and Sgall (and different proof was later given by Hastad and Wigderson). In this work we make the next natural step in this program.
The communication problems arising in this context are of somewhat different nature that are commonly studied. I plan to explain them, their nature, and why (unlike most other lower bounds) probabilistic and information theoretic arguments must be "protocol-specific". I plan sketch the proof of the our lower bound, and perhaps speculate on how close it brings us to the real goal.
No special background is assumed.
Based on joint work with Dima Gavinsky, Or Meir and Omry Weinstein
See: http://www.math.rutgers.edu/~sk1233/theory-seminar/S14/