*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...
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...
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...
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...
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...
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...
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...
Nate Chinen, Vijay Iyer, Craig Taborn, and Derek Bermel
Jazz journalist Nate Chinen, who writes for the New York
Times, the Village Voice, and JazzTimes, is
joined by pianists Vijay Iyer and Craig Taborn, along with
Institute Artist-in-Residence, for a conversation about
improvisational jazz and...
We shall discuss new pseudorandom generators for regular
read-once branching programs of small width. A branching program is
regular if the in-degree of every vertex in it is (either 0 or) 2.
For every width d and length n, the pseudorandom...
