Monotone Expanders -- Constructions and Applications

Zeev Dvir
Princeton University; Member, School of Mathematics
April 22, 2011

A Monotone Expander is an expander graph which can be decomposed into a union of a constant number of monotone matchings, under some fixed ordering of the vertices. A matching is monotone if every two edges (u,v) and (u',v') in it satisfy u < u' --> v < v'. It is not clear a priori if monotone expanders exist or not. This is partially due to the fact that the natural application of the probabilistic method does not work in this special case.

On Zaremba's Conjecture

Alex Kontorovich
Stony Brook University
April 22, 2011

Inspired by the theory of good lattice points in numerical integration, Zaremba conjectured in 1972 that for every denominator q, there is some coprime numerator p, such that the continued fraction expansion of p/q has uniformly bounded quotients. We will present recent progress on this problem, joint with Jean Bourgain.

Pseudorandomness in Mathematics and Computer Science Mini-Workshop

Institute for Advanced Study
April 22, 2011

In math, one often studies random aspects of deterministic systems and structures.  In CS, one often tries to efficiently create structures and systems with specific random-like properties.  Recent work has shown many connections between these two approaches through the concept of "pseudorandomness".  This workshop highlights these connections, aimed at a joint audience of mathematicians and computer scientists.

Universality in the 2D Coulomb Gas

Pierluigi Falco
Member, School of Mathematics
April 20, 2011

The Coulomb Gas is a model of Statistical Mechanics with a special type of phase transition. In the first part of the talk I will review the expected features conjectured by physicists and the few mathematical results so far obtained. The second part will be an introductory discussion of a general technique (Renormalization Group) to approach the problem.

New Tools for Graph Coloring

Rong Ge
Princeton University
April 19, 2011

How to color $3$ colorable graphs with few colors is a problem of longstanding interest. The best polynomial-time algorithm uses $n^{0.2130}$ colors.

We explore the possibility that more levels of Lasserre Hierarchy can give improvements over previous algorithms. While the case of general graphs is still open, we can give analyse the Lasserre relaxation for two interesting families of graphs.

Quantum Fingerprints that Keep Secrets

Dmitry Gavinsky
NEC Research Laboratories
April 18, 2011

In a joint work with Tsuyoshi Ito we have constructed a fingerprinting scheme (i.e., hashing) that leaks significantly less than log(1/epsilon) bits about the preimage, where epsilon is the error ("collision") probability. It is easy to see that classically this is not achievable; our construction is quantum, and it gives a new example of (unconditional) qualitative advantage of quantum computers.