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.
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.
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 performance.
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 uses a seed of length $O((log d + log log n + log(1/p)) log n)$ to produce $n$ bits that cannot be distinguished from a uniformly random string by any regular width $d$ length $n$ read-once branching program, except with probability $p > 0$
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 Newton’s gravitational law shows chaotic dynamics. Earlier, Euler (1707–83) and Lagrange (1736–1813) found instances of stable motion; a spacecraft in the gravitational fields of the sun, earth, and the moon provides an interesting system of this kind. Helmut Hofer, Professor in the School of Mathematics, explains how these observations have led to the development of a geometry based on area rather than distance.