School of Mathematics

On the Comparison of Trace Formulas

Jim Arthur
University of Toronto
April 28, 2011 - 2:15pm

GALOIS REPRESENTATIONS AND AUTOMORPHIC FORMS SEMINAR

We shall recall the spectral terms from the trace formula for G and its stabilaization, as well as corresponding terms from the twisted trace formula for GL(N). We shall then discuss aspects of the proof of the theorems stated in the first talk that are related to the comparison of these formulas.


Classification of Representations

Jim Arthur
University of Toronto
April 28, 2011 - 1:00pm

GALOIS REPRESENTATIONS AND AUTOMORPHIC FORMS SEMINAR

Suppose that G is a connected, quasisplit, orthogonal or symplectic group over a field F of characteristic 0. We shall describe a classification of the irreducible representations of G(F) if F is local, and the automorphic representations of G in the discrete spectrum if F is global. The classification is by harmonic analysis and endoscopic transfer, which ultimately ties the representations of G to those of general linear groups.


Computer Science and Homotopy Theory

Vladimir Voevodsky
Professor, School of Mathematics
April 27, 2011 - 6:00pm

Quadratic Goldreich-Levin Theorems

Madhur Tulsiani
Member, School of Mathematics
April 26, 2011 - 10:30am

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


Learning and Testing k-Model Distributions

Rocco Servidio
Columbia University
April 25, 2011 - 11:15am

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.


Pseudorandomness in Mathematics and Computer Science Mini-Workshop

Institute for Advanced Study
April 22, 2011 (All day)

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.


The Unique Games Conjecture

Ryan O'Donnell
Carnegie Mellon University; Member, School of Mathematics
April 20, 2011 - 6:00pm

Universality in the 2D Coulomb Gas

Pierluigi Falco
Member, School of Mathematics
April 20, 2011 - 2:00pm

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 - 10:30am

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 - 11:15am

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.