Stein Structures: Existence and Flexibility

Kai Cieliebak
Ludwig-Maximilians-Universitat, Munich, Germany
February 29, 2012

This is a series of 3 talks on the topology of Stein manifolds, based on work of Eliashberg since the early 1990ies. More specifically, I wish to explain to what extent Stein structures are flexible, i.e. obey an h-principle. After providing some general background on Stein manifolds, the first talk will focus on the construction of plurisubharmonic functions with specific properties. Using these, I will in the second talk present the proof of Eliashberg's existence theorem for Stein structures.

The Complexity of Distributions

Emanuele Viola
Northeastern University
March 5, 2012

Complexity theory, with some notable exceptions, typically studies the complexity of computing a function h(x) of a *given* input x. We advocate the study of the complexity of generating -- or sampling -- the output distribution h(x) for random x, given random bits.

In particular, we present first-of-their-kind lower bounds for generating distributions in various restricted computational models. We also discuss connections to succinct data structures and to randomness extractors.

Local Correction of Codes and Euclidean Incidence Geometry

Avi Wigderson
Institute for Advanced Study
March 5, 2012

A classical theorem in Euclidean geometry asserts that if a set of points has the property that every line through two of them contains a third point, then they must all be on the same line. We prove several approximate versions of this theorem (and related ones), which are motivated from questions about locally correctable codes and matrix rigidity. The proofs use an interesting combination of combinatorial, algebraic and analytic tools.

Joint work with Boaz Barak, Zeev Dvir and Amir Yehudayoff