[Colloquium] Pankratov/MS Presentation/Mar 7, 2012
Margaret Jaffey
margaret at cs.uchicago.edu
Tue Feb 21 09:45:22 CST 2012
This is an announcement of Denis Pankratov's MS Presentation.
------------------------------------------------------------------------------
Date: Wednesday, March 7, 2012
Time: 2:30 PM
Place: Ryerson 277
M.S. Candidate: Denis Pankratov
M.S. Paper Title: Direct Sum Questions in Classical Communication
Complexity
Abstract:
In 1988, Karchmer and Wigderson generalized Yaos two-party
communication model of functions to relations and showed a remarkable
connection of this model to the Boolean circuit model. A few years
later, continuing this line of work, Karchmer, Raz, and Wigderson
proposed a program to separate NC from P through direct-sum-type
inequalities in communication complexity. This spurred the study of
this fundamental question in communication complexity: given problems
A and B, is it easier to solve A and B together than separately? It
seems that we are still far from separating NC from P; however, during
the last 20 years of research our knowledge of the behavior of
different communication complexity measures with respect to the direct
sum has seen a lot of progress. We survey some of these results in
this paper and make a new observation about the recent approach to the
direct-sum question in the randomized setting.
Denis's advisor is Prof. Laszlo Babai
Login to the Computer Science Department website for details:
https://www.cs.uchicago.edu/phd/ms_announcements#pankratov
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
Margaret P. Jaffey margaret at cs.uchicago.edu
Department of Computer Science
Student Support Rep (Ry 156) (773) 702-6011
The University of Chicago http://www.cs.uchicago.edu
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=
More information about the Colloquium
mailing list