## Quadratic Goldreich-Levin Theorems

Decompositions in theorems in classical Fourier analysis which decompose a function into large Fourier coefficients and a part that is pseudorandom

Madhur Tulsiani

Member, School of Mathematics

April 26, 2011

Decompositions in theorems in classical Fourier analysis which decompose a function into large Fourier coefficients and a part that is pseudorandom

Rocco Servidio

Columbia University

April 25, 2011

A k-modal probability distribution over the domain {1,...,N} is one whose histogram has at most k "peaks" and "valleys". Such distributions are a natural generalization of the well-studied class of monotone increasing (or monotone decreasing) probability distributions.

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.

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.

Ryan O'Donnel

Carnegie Mellon University; Member, School of Mathematics

April 20, 2011

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.

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.

David Helm

University of Texas

April 14, 2011

Alvaro Pelayo

Member, School of Mathematics

April 13, 2011

Nick Harvey

University of Waterloo

April 11, 2011

A "sparsifier" of a graph is a weighted subgraph for which every cut has approximately the same value as the original graph, up to a factor of (1 +/- eps). Sparsifiers were first studied by Benczur and Karger (1996). They have wide-ranging applications, including fast network flow algorithms, fast linear system solvers, etc. Batson, Spielman and Srivastava (2009) showed that sparsifiers with O(n/eps^2) edges exist, and they can be computed in time poly(n,eps).