Recently Added

Edward T. Cone Concert Talk

Joe Locke, Lisa Pegher, Bernard Woma, Paul Lansky, and Derek Bermel
December 11, 2010

As a part of the Mallet Madness concerts, percussionists Lisa Pegher, Joe Locke, and Bernard Woma join in conversation with Institute Artist-in-Residence Derek Bermel and composer Paul Lansky

Self-Correction, Distance Estimation and Local Testing of Codes

Dana Moshkovitz
Massachusetts Institute of Technology
November 29, 2010

We construct linear codes of almost-linear length and linear distance that can be locally self-corrected on average from a constant number of queries:

1. Given oracle access to a word $w\in\Sigma^n$ that is at least $\varepsilon$-close to a codeword $c$, and an index $i\in [n]$ to correct, with high probability over $i$ and over the internal randomness, the local algorithm returns a list of possible corrections that contains $c_i$.

(Some) Generic Properties of (Some) Infinite Groups

Igor Rivin
Temple University; Member, School of Mathematics
November 29, 2010

This talk will be a biased survey of recent work on various properties of elements of infinite groups, which can be shown to hold with high probability once the elements are sampled from a large enough subset of the group (examples of groups: linear groups over the integers, free groups, hyperbolic groups, mapping class groups, automorphism groups of free groups . . . )

The Permanents of Gaussian Matrices

Scott Aaronson
Massachusetts Institute of Technology
November 29, 2010

In recent joint work with Alex Arkhipov, we proposed a quantum optics experiment, which would sample from a probability distribution that we believe cannot be sampled (even approximately) by any efficient classical algorithm, unless the polynomial hierarchy collapses. Several optics groups are already working toward doing our experiment.

A Classical Approximation Point of View on Some Results in the Spectral Theory of Jacobi Matrices

Mira Shamis
Institute for Advanced Study
December 10, 2010

Deift--Simon and Poltoratskii--Remling proved upper bounds on the measure of the absolutely continuous spectrum of Jacobi matrices. Using methods of classical approximation theory, we give a new proof of their results, and generalize them in several ways. First, we prove a sharper inequality taking the distribution of the values of the potential into account. Second, we prove a generalization of a "local" inequality of Deift--Simon to the non-ergodic setting. Based on joint work with Sasha Sodin