[Colloquium] REMINDER: Talk by Alexander Sherstov Today

[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.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20090130/d626dc66/attachment.htm