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}\).

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.

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.

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.

Applications of additive combinatorics to Diophantine equations

Alexei Skorobogatov
Imperial College London
April 10, 2014
The work of Green, Tao and Ziegler can be used to prove existence and approximation properties for rational solutions of the Diophantine equations that describe representations of a product of norm forms by a product of linear polynomials. One can also prove that the Brauer-Manin obstruction precisely describes the closure of rational points in the adelic points for pencils of conics and quadrics over \(\mathbb Q\) when the degenerate fibres are all defined over \(\mathbb Q\).

Do NP-Hard Problems Require Exponential Time?

Andrew Drucker
Institute for Advanced Study; Member, School of Mathematics
April 8, 2014
The P != NP conjecture doesn't tell us what runtime is needed to solve NP-hard problems like 3-SAT and Hamiltonian Path. While some clever algorithms are known, they all require exponential time, and some researchers suspect that this is unavoidable. This idea is expressed in the influential "Exponential Time Hypothesis" (ETH) of Impagliazzo, Paturi, and Zane. In this survey talk, I will describe the ETH and its consequences (some of which are rather subtle). We will see that this hypothesis holds considerable explanatory power.

Minimal Discrepancy of Isolated Singularities and Reeb Orbits

Mark McLean
Stony Brook University
April 4, 2014
Let A be an affine variety inside a complex N dimensional vector space which either has an isolated singularity at the origin or is smooth at the origin. The intersection of A with a very small sphere turns out to be a contact manifold called the link of A. Any contact manifold contactomorphic to the link of A is said to be Milnor fillable by A. If the first Chern class of our link is 0 then we can assign an invariant of our singularity called the minimal discrepancy, which is an important invariant in birational geometry.

Byzantine Agreement in Expected Polynomial Time

Valerie King
University of Victoria; Member, School of Mathematics
April 1, 2014
Byzantine agreement is a fundamental problem of distributed computing which involves coordination of players when a constant fraction are controlled by a malicious adversary. Each player starts with a bit, and the goal is for all good players to agree on a bit whose value is is equal to some good player's initial bit. I'll present the first algorithm with polynomial expected time in the asynchronous message-passing model with a strong adversary.