[Colloquium] Reminder: Pankratov/MS Presentation/Mar 7, 2012

[Margaret Jaffey]

This is a reminder about Denis Pankratov's MS Presentation tomorrow.

------------------------------------------------------------------------------
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 Yao’s 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
=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=-=