Near-Linear Time Approximation Algorithm for Balanced Separator

Sushant Sachdeva
Institute for Advanced Study
April 16, 2012

The goal of the Balanced Separator problem is to find a balanced cut in a given graph G(V,E), while minimizing the number of edges that cross the cut. It is a fundamental problem with applications in clustering, image segmentation, community detection, and as a primitive for divide-and-conquer on graphs.

Sperm Bomb: Art, Feminism, and the American War in Vietnam

Mignon Nixon
The Courtald Institute of Art
April 17, 2012

A blue mushroom cloud fills the page, its contour traced by the comet-like tails of shrieking heads whose gaping mouths spew out furious curses in a rain of profanity over needle-stiff bodies littering the ground. This lecture by Mignon Nixon borrows its title, “Sperm Bomb,” from Nancy Spero, who, in 1964, in response to the escalating American war in Vietnam, abruptly abandoned ­painting on canvas for more immediate means: gouache and ink liberally diluted with spit. Returning to the scene of war ­resistance and nascent feminism in the Vietnam era, Nixon reflects upon newly pressing questions of what art concerned with ­subjectivity brings to a situation of war.

This lecture was the final one in the series Art and Its Spaces, cosponsored by the Institute for Advanced Study and the Department of Art and Archaeology at Princeton University.

Multiple Zeta Values

Francis Brown
CNRS/Institut de Math. de Jussieu, Paris
April 19, 2012

I will report on some recent work on multiple zeta values. I will sketch the definition of motivic multiple zeta values, which can be viewed as a prototype of a Galois theory for certain transcendental numbers, and then explain how they were used to prove a conjecture due to Hoffman giving a generating family for multiple zeta values, and a conjecture of Deligne and Ihara on the fundamental group of the projective line minus 3 points.

Pseudorandom Generators for Read-Once ACC^0

Srikanth Srinivasan
DIMACS
April 24, 2012

We consider the problem of constructing pseudorandom generators for read-once circuits. We give an explicit construction of a pseudorandom generator for the class of read-once constant depth circuits with unbounded fan-in AND, OR, NOT and generalized modulo m gates, where m is an arbitrary fixed constant. The seed length of our generator is poly-logarithmic in the number of variables and the error.

Joint work with Dmitry Gavinsky (NEC Labs) and Shachar Lovett (IAS).

Pay for Performance or Performance for Pay: The Economics of the Employment Contract from Roman Times to Our Time

W. Bentley MacLeod
Leon Levy Foundation Member, School of Social Science; Sami Mnaymneh Professor of Economics and Professor of International and Public Affairs, Columbia University
April 26, 2012

Employment contracts are central to many current policy debates. New York City is experimenting with rewarding teachers based on value added in the hope that it will improve performance. Compensation practices in the financial sector are often viewed as a contributing factor to the financial crisis, resulting in increased regulation. At the same time, there are continued calls to reduce the public sector and rely more on market forces. In the 2012 Leon Levy Lecture, W. Bentley MacLeod, Sami Mnaymneh Professor of Economics and Professor of International and Public Affairs at Columbia University, discusses two approaches to compensation: “pay for performance” and “performance for pay.” When preconditions for market supply of goods and services are satisfied, then pay for performance is effective. But when performance is difficult to measure, there is a need to reward performance with pay. MacLeod illustrates these ideas with examples taken from the management of Roman villas from the time of Columella and Pliny the Younger, and explains why the lack of effective management may be a key factor in the poor performance of schools and financial markets.