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...
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 generator...
In this survey I will present several extremal problems, and
some solutions, concerning convex lattice polytopes.
A typical example is to determine the smallest area that a convex
lattice polygon can have if it has exactly n vertices.
The mathematical problems arising from
modern celestial mechanics, which originated with Isaac Newton’s
Principia in 1687, have led to many mathematical theories. Poincaré
(1854-1912) discovered that a system of several celestial bodies
moving under...
For four years now, we have been conducting "medium-scale"
experiments in how human subjects behave in strategic and economic
settings mediated by an underlying network structure. We have
explored a wide range of networks inspired by generative...
Collateralized Default Obligations (CDOs) and related financial
derivatives have been at the center of the last financial crisis
and subject of ongoing regulatory overhaul.
Despite their demonstrable benefits in economic theory,
derivatives suffer...
