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
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$.
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 . . . )
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.
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