School of Mathematics
Workshop on Pseudorandomness in Mathematical Structures
June 14 - 18, 2010
Organizers: Jean Bourgain, Russell Impagliazzo, Peter Sarnak and Avi Wigderson
Workshop Homepage:http://www.math.ias.edu/pseudo2010
Program: http://www.math.ias.edu/pseudo2010/program.
Hardness of Approximately Solving Linear Equations Over Reals
We consider the problem of approximately solving a system of homogeneous linear equations over reals, where each equation contains at most three variables. Since the all-zero assignment always satisfies all the equations exactly, we restrict the assignments to be "non-trivial".
Can Complexity Theory Ratify the Invisible Hand of the Market?
*It is not from the benevolence of the butcher, the brewer, or the baker, that we expect our dinner, but from their regard for their own interest. Each participant in a competitive economy is led by an invisible hand to promote an end which was no part of his intention.*
Adam Smith, 1776
Critical Slowdown for the Ising Model on the Two-Dimensional Lattice
Intensive study throughout the last three decades has yielded a rigorous understanding of the spectral-gap of the Glauber dynamics for the Ising model on Z2 everywhere except at criticality. While the critical behavior of the Ising model has long been the focus for physicists, mathematicians have only recently developed an understanding of its critical geometry with the advent of SLE, CLE and new tools to study conformally invariant systems. A rich interplay exists between the static and dynamic models.
Cover Times, Blanket Times, and Majorizing Measures
The cover time of a graph is one of the most basic and well-studied properties of the simple random walk, and yet a number of fundamental questions concerning cover times have remained open. We show that there is a deep connection between cover times of graphs and Talagrand's majorizing measure theory. In particular, we prove that the cover time can be characterized, up to universal constants, by the majorizing measure value of a certain metric space on the underlying graph.
Measuring Shape With Homology
The ordinary homology of a subset S of Euclidean space depends only on its topology. By systematically organizing homology of neighborhoods of S, we get quantities that measure the shape of S, rather than just its topology. These quantities can be used to define a new notion of fractional dimension of S. They can also be effectively calculated on a computer.
Compressing Bounded-Round Communication
In this talk we will present a near-optimal compression scheme for bounded-round randomized 2-party communication protocols. Previously, such a scheme was only known for protocols where the inputs to the parties are independent. The results yield a new optimal direct sum theorem for bounded-round communication. They also reveal a tight connection between the Information Cost of a problem and its amortized Communication Complexity. Joint work with Anup Rao.
A Combinatorial Proof of the Chernoff-Hoeffding Bound, With Applications to Direct-Product Theorems
We give a simple combinatorial proof of the Chernoff-Hoeffding concentration
bound for sums of independent Boolean random variables. Unlike the standard
proofs, our proof does not rely on the method of higher moments, but rather uses
an intuitive counting argument. In addition, this new proof is constructive in the
following sense: if the given random variables fail the concentration bound, then
we can efficiently find a subset of the variables that are statistically dependent.
As easy corollaries, we also get concentration bounds for [0, 1]-valued random
Product Rules in Semidefinite Programming
Semidefinite programming bounds are widely used in combinatorial optimization, quantum computing and complexity theory. The first semidefinite programming bound to gain fame is the so-called theta number developed by Lov\'asz to compute the Shannon capacity of the five-cycle graph. The semidefinite relaxation for the maximal cut problem has led to the near ubiquitous use of semidefinite programming in designing approximation algorithms.
EINSTEIN DRIVE
PRINCETON
NEW JERSEY
08540
609.734.8000