Title: Can Every Sequential Computation be Efficiently Parallelized?
Speaker: Avi Wigderson, Institute for Advanced Study
Date: Tuesday, February 18, 2014 2:00pm
Location: Hill Center, Room 525, Rutgers University, Busch Campus, Piscataway, NJ
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 complexity lower bounds.
See: http://math.rutgers.edu/seminars/allseminars.php?sem_name=Discrete%20Math