Local Correctability of Expander Codes

Brett Hemenway
University of Pennsylvania
April 14, 2014
An error-correcting code is called locally decodable if there exists a decoding algorithm that can recover any symbol of the message with high probability by reading only a small number of symbols of the corrupted codeword. There is a fundamental tradeoff in locally decodable codes between the rate (the ratio of message length to codeword length) and the locality (the number of symbols read by the decoder). Ideally, one strives for high rate and low locality.

Toroidal Soap Bubbles: Constant Mean Curvature Tori in \(S^3\) and \(R^3\)

Emma Carberry
University of Sydney
April 14, 2014
Constant mean curvature (CMC) tori in \(S^3\), \(R^3\) or \(H^3\) are in bijective correspondence with spectral curve data, consisting of a hyperelliptic curve, a line bundle on this curve and some additional data, which in particular determines the relevant space form. This point of view is particularly relevant for considering moduli-space questions, such as the prevalence of tori amongst CMC planes. I will address these periodicity questions for the spherical and Euclidean cases, using Whitham deformations, which I will explain.

IP = PSPACE via error correcting codes

Or Meir
Institute for Advanced Study; Member, School of Mathematics
April 15, 2014
The IP theorem, which asserts that IP = PSPACE (Lund et. al., and Shamir, in J. ACM 39(4)), is one of the major achievements of complexity theory. The known proofs of the theorem are based on the arithmetization technique, which transforms a quantified Boolean formula into a related polynomial. The intuition that underlies the use of polynomials is commonly explained by the fact that polynomials constitute good error correcting codes. However, the known proofs seem tailored to the use of polynomials, and do not generalize to arbitrary error correcting codes.

Limiting Eigenvalue Distribution of Random Matrices Involving Tensor Product

Leonid Pastur
B. Verkin Institute for Low Temperature Physics and Engineering of the National Academy of Sciences of Ukraine
April 16, 2014
We consider two classes of \(n \times n\) sample covariance matrices arising in quantum informatics. The first class consists of matrices whose data matrix has \(m\) independent columns each of which is the tensor product of \(k\) independent \(d\)-dimensional vectors, thus \(n=d^k\). The matrices of the second class belong to \(\mathcal{M}_n(\mathbb{C}^{d_1} \otimes \mathbb{C}^{d_2}), \ n=d_1 d_2\) and are obtained from the standard sample covariance matrices by the partial transposition in \(\mathbb{C}^{d_2}\).

True Randomness: Its Origin and Expansion

Yaoyun Shi
University of Michigan
April 21, 2014
How can we produce randomness of almost perfect quality, in large quantities, and under minimal assumptions? This question is fundamental not only to modern day information processing but also to physics. Yet a satisfactory answer is still elusive to both the practice and the theory of randomness extraction. Here we propose a solution through a new paradigm of extracting randomness from physical systems and basing security on the validity of physical theories, such as quantum mechanics and special relativity.

A Riemann-Roch theorem in Bott-Chern cohomology

Jean-Michel Bismut
Université Paris-Sud
April 21, 2014
If \(M\) is a complex manifold, the Bott-Chern cohomology \(H_{\mathrm{BC}}^{(\cdot,\cdot)}\left(M,\mathbf{C}\right)\) of \(M\) is a refinement of de Rham cohomology, that takes into account the \((p,q)\) grading of smooth differential forms. By results of Bott and Chern, vector bundles have characteristic classes in Bott-Chern cohomology, which will be denoted with the subscript \(\mathrm{BC}\). Let \(p:M\to S\) be a proper holomorphic submersion of complex manifolds. Let \(F\) be a holomorphic vector bundle on \(M\) and let \(Rp_{*}F\) be its direct image.

Results and open problems in theory of quantum complexity

Andris Ambainis
University of Latvia; Member, School of Mathematics
April 22, 2014
I will survey recent results and open problems in several areas of quantum complexity theory, with emphasis on open problems which can be phrased in terms of classical complexity theory or mathematics but have implications for quantum computing:

1. Quantum vs. classical query complexity
2. Quantum vs. classical query complexity for almost all inputs
3. Quantum counterparts of Valiant-Vazirani theorem (reducing NP to unique-NP)