## Complexity, Approximability, and Mechanism Design

Christos Papadimitriou

University of California at Berkeley

February 28, 2012

Christos Papadimitriou

University of California at Berkeley

February 28, 2012

Gopal Prasad

University of Michigan; Member, School of Mathematics

February 27, 2012

Noga Zewi

Technion

February 27, 2012

Amir Yehudayoff

Technion-Israel; Institute for Advanced Study

February 23, 2012

The talk will have 2 parts (between the parts we will have a break).

In the first part, we will discuss two options for using groups to construct expander graphs (Cayley graphs and Schreier diagrams). Specifically, we will see how to construct monotone expanders in this way. As in recent works (e.g. of Bourgain and Gamburd), we will see that the proof consists of 3 different steps. We will shortly discuss these 3 steps.

Boaz Barak

Microsoft Research New England

February 23, 2012

I'll describe a physical implementation of zero knowledge proofs whose goal is to verify that two physical objects are identical, without revealing any information about them. Our motivation is the task of verifying that an about-to-be-dismantled nuclear warhead is authentic without revealing its classified design. This is one of the technical hurdles that arises in implementing nuclear disarmament. I will not assume any background in either cryptography or nuclear disarmament.

Joel Spencer

Courant Institute, NYU

February 21, 2012

Lars Hakan Eliasson

University of Paris VI; Institute for Advanced Study

February 21, 2012

We shall discuss reducibility of these equations on the torus with a small potential that depends quasi-periodically on time. Reducibility amounts to "reduce” the equation to a time-independent linear equation with pure point spectrum in which case all solutions will be of Floquet type.

For the Schrodinger equation, this has been proven in a joint work with S. Kuksin, and for the wave equation we shall report on a work in progress with B. Grebert and S. Kuksin.

Joel Spencer

Courant Institute; NYU

February 21, 2012

Tudor Ratiu

EPFL (Ecole Polytechnique Federale de Lausanne), Switzerland

February 17, 2012

Gopal Prasad

University of Michigan

February 16, 2012

A fake projective plane is a smooth complex projective algebraic surface whose Betti numbers are same as those of the complex projective plane but which is not the complex projective plane. The first fake projective plane was constructed by David Mumford in 1978 using p-adic uniformization. This construction is so indirect that it is hard to obtain geometric properties of the fake projective plane. A major problem in the theory of complex algebraic surfaces was to find all fake projective planes in a way which allows us to discover their geometric properties.