Recently Added

Pseudorandom Generators for Regular Branching Programs

Amir Yehudayoff
Institute for Advanced Study
March 16, 2010

We shall discuss new pseudorandom generators for regular read-once branching programs of small width. A branching program is regular if the in-degree of every vertex in it is (either 0 or) 2. For every width d and length n, the pseudorandom generator uses a seed of length $O((log d + log log n + log(1/p)) log n)$ to produce $n$ bits that cannot be distinguished from a uniformly random string by any regular width $d$ length $n$ read-once branching program, except with probability $p > 0$

Edward T. Cone Concert Talk

Nate Chinen, Vijay Iyer, Craig Taborn, and Derek Bermel
March 20, 2010

Jazz journalist Nate Chinen, who writes for the New York Times, the Village Voice, and JazzTimes, is joined by pianists Vijay Iyer and Craig Taborn, along with Institute Artist-in-Residence, for a conversation about improvisational jazz and performance.

Celestial Mechanics and a Geometry Based on Area

Helmut Hofer
Institute for Advanced Study
March 10, 2010

The mathematical problems arising from modern celestial mechanics, which originated with Isaac Newton’s Principia in 1687, have led to many mathematical theories. Poincaré (1854-1912) discovered that a system of several celestial bodies moving under Newton’s gravitational law shows chaotic dynamics. Earlier, Euler (1707–83) and Lagrange (1736–1813) found instances of stable motion; a spacecraft in the gravitational fields of the sun, earth, and the moon provides an interesting system of this kind. Helmut Hofer, Professor in the School of Mathematics, explains how these observations have led to the development of a geometry based on area rather than distance.

A Theory of Cryptographic Complexity

Manoj M. Prabhakaran
University of Illinois at Urbana-Champaign
March 1, 2010

In this talk, I shall describe an ongoing project to develop a complexity theory for cryptographic (multi-party computations. Different kinds of cryptographic computations involve different constraints on how information is accessed. Our goal is to qualitatively -- and if possible, quantitatively -- characterize the "cryptographic complexity" (defined using appropriate notions of reductions) of these different modes of accessing information. Also, we explore the relationship between such cryptographic complexity and computational intractability.

The Audience as Prisoner: Reflections on the Activity of the Object

Horst Bredekamp
Professor of Art History, Humboldt-Universität zu Berlin
March 2, 2010

The basic problem of all pictures is grounded in their bipolar existence. They are created objects, but nonetheless present themselves as physical beings. This paradoxical double-structure is exemplified in the “ME FECIT” of numberless inscriptions. With its “EGO,” the pictorial work declares that it does not consist of artificially shaped dead material, but of a living form. Dramatizing this problem, Leonardo da Vinci created the formula that pictures “imprison” the audience.

In this lecture Horst Bredekamp follows a chain of examples from antiquity, the Middle Ages, early modernity, and the twentieth century in order to question the traditional concept of the relationship between the work of art and the beholder. conceptualizing the theory of picture-act, which tries to develop alternatives to traditional concepts of representation, illustration, and mimesis.

Average Sensitivity of Polynomial Threshold Functions

Rocco Servedio
Columbia University
February 22, 2010

How many edges of the n-dimensional Boolean hypercube can be sliced by a degree-d polynomial surface? This question can be equivalently stated as "What is the maximum average sensitivity of any degree-d polynomial threshold function?" In 1994 Gotsman and Linial posed this question and gave a conjectured answer: the symmetric function slicing the middle d layers of the Boolean hypercube has the highest average sensitivity of all degree-d polynomial threshold functions.