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.

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.

Critique of Humanitarian Reason

Didier Fassin
Institute for Advanced Study
February 17, 2010

Humanitarianism, which can be defined as the introduction of moral sentiments into human affairs, is a major component of contemporary politics—locally and globally—for the relief of poverty or the management of disasters, in times of peace as well as in times of war. But how different is the world and our understanding of it when we mobilize compassion rather than justice, call for emotions instead of rights, consider inequality in terms of suffering, and violence in terms of trauma? What is gained—and lost—in this translation? In this lecture, Didier Fassin, James D. Wolfensohn Professor in the School of Social Science, attempts to comprehend humanitarian government, to make sense of its expansion, and to assess its ethical and political consequences.

Complexity of Constraint Satisfaction Problems: Exact and Approximate

Prasad Raghavendra
University of Washington
February 16, 2010

 Is there a common explanation for 2SAT being solvable polynomial time, and Max2SAT being approximable to a 0.91 factor? More generally, it is natural to wonder what characterizes the complexity of exact constraint satisfaction problems (CSP) like 2SAT and what determines the approximation ratios for MaxCSPs like Max2SAT.

Artistic Collaboration: A Conversation with Alex and Vincent Katz

Alex and Vincent Katz
February 12, 2010

Painter Alex Katz and his son, writer Vincent Katz, discuss their personal experiences in artistic collaboration in a conversation with Derek Bermel, the Institute's Artist-in-Residence.  Both Alex and Vincent have been involved in numerous collaborative projects.  Alex has collaborated on books with many poets, including John Ashbery, Robert Creeley, and Kenneth Koch, and he has designed sets and costumes for choreographers Paul Taylor and David Parsons.  Vincent has collaborated with the artists Rudy Burckhardt, Francesco Clemente, and Wayne Gonzales.  He is an art critic who has authored numerous essays and articles on contemporary artists; he is the publisher of the poetry journal Vanitas and of Libellum Books; and he serves as Chair of the Board of the Bowery Poetry Club.