[Colloquium] Talk by Alexander Sherstov, University of Texas on January 30, 2009

[Katie Casey]

DEPARTMENT OF COMPUTER SCIENCE

UNIVERSITY OF CHICAGO

Date: Friday, January 30, 2009
Time: 2:30 p.m.
Place: RY 251

----------------------------------------------------------

Speaker:	Alexander Sherstov

From:		University of Texas at Austin

Website: 	http://www.cs.utexas.edu/~sherstov/

Title:   Lower Bounds for Communication Complexity Using Pattern  
Matrices

Abstract:  Communication complexity studies the amount of  
communication necessary to compute a given function when its arguments  
are distributed among several parties. This research area plays a  
fundamental role in theoretical computer science and beyond, with  
applications as diverse as circuit complexity, learning theory,  
pseudorandomness, and private information retrieval. I will present  
the pattern matrix method, a new approach that I have developed for  
studying communication complexity, based on analytic techniques such  
as linear-programming duality and approximation theory. Using my  
method, I will show how to solve several longstanding problems in the  
field.
  As a first such application, I will resolve a well-known question in  
circuit complexity on the limitations of neural networks. In  
particular, I will prove the optimality of Allender’s classic  
simulation of AND/OR/NOT circuits by neural networks. Second, I will  
show that polynomial-size formulas in disjunctive normal form (DNF)  
have a complicated geometry, namely, they cannot be embedded in  
halfspaces of subexponential dimension. This solves an open problem in  
communication complexity and helps explain the lack of progress on the  
computational learning of DNF formulas. As a final application, I will  
prove that for a large and natural class of problems, quantum  
communication is not more powerful than classical communication. I  
will also discuss the broader impact of the pattern matrix method,  
surveying a series of important advances by other researchers.



Refreshments will be served following the talk in RY 255 at 3:30.