In this talk we will discuss information complexity -- a measure
of the amount of information Alice and Bob need to exchange to
solve a problem over distributed inputs. We will present an
information-theoretically optimal protocol for computing the...
For all practical purposes, the Micali-Vazirani algorithm,
discovered in 1980, is still the most efficient known maximum
matching algorithm (for very dense graphs, slight asymptotic
improvement can be obtained using fast matrix
multiplication)...
The PCP theorem (Arora et. al., J. ACM 45(1,3)) asserts the
existence of proofs that can be verified by reading a very small
part of the proof. Since the discovery of the theorem, there has
been a considerable work on improving the theorem in terms...
Some important mechanisms considered in game theory require
solving optimization problems that are computationally hard.
Solving these problems approximately may not help, as it may change
the players’ rational behavior in the original mechanisms...
Polynomial Identity Testing (PIT) is the problem of identifying
whether a given algebraic circuit computes the identically zero
polynomial. It is well-known that this problem can be solved with
small error probability by testing whether the circuit...
One of the major insights of the ``fixed-parameter
tractability’’ (FPT) approach to algorithm design is that, for many
NP-hard problems, it is possible to efficiently *shrink* instances
which have some underlying simplicity. This preprocessing
can...
We prove a strong limitation on the ability of entangled provers
to collude in a multiplayer game. Our main result is the first
nontrivial lower bound on the class MIP* of languages having
multi-prover interactive proofs with entangled provers...
I present some of the very fundamental notions in game theory,
with emphasis on their role in the theory of mechanism design and
implementation. Examples include (1) normal-form games: Nash
equilibrium and full implementation, dominant strategy...
