|
Abstract:
There are many mathematical problems that people want to solve with
computers- gathering statistics from databases, verifying hardware
and
software designs, solving systems of equations, et cetera. For some
of
these problems, there are known to be efficient algorithms. For the
others, no efficient algorithms are known, and for many of these
tasks, it is believed that all algorithms for solving these problems
are inherently inefficient. Identifying these hard problems and
rigorously and quantitatively establishing just how hard they are is
the
central task in computational complexity.
In this survey talk, I will discuss one of the most successful tools
in
computational complexity: Communication complexity—the study of how
many bits must be broadcast when the inputs to a function are split up
between multiple players and the players must communicate to arrive at the
answer.
The talk will discuss how communication complexity provides a bridge
between computing and combinatorics, some applications to
establishing
limitations for algorithmic techniques in streaming algorithms,
circuit
synthesis, and integer optimization, and hopefully prove a simple
foundational result or two, and hit on some open questions.
Prerequisites should be pretty minimal.
Nathan Segerlind is visiting/adjunct professor at Portland State
University. He received a PhD in 2003 in computer science from UC San
Diego under the direction of Sam Buss and Russell Impagliazzo. The
dissertation was awarded the Association for Symbolic Logic Sacks
Prize
for Outstanding Doctoral Dissertation as well as the European
Association of Computer Science Logic Ackermann Prize for Outstanding
doctoral dissertation. He has held postdoctoral appointments at the
Institute for Advanced Study and the University of Washington. He is
interested in the theory of computation, logic, combinatorics and
algorithms. Several of Nathan's current and recent projects make use
of communication complexity.
|