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.

Expanders and Communication-Avoiding Algorithms

Oded Schwartz
Technical University Berlin
January 25, 2010

Algorithms spend time on performing arithmetic computations, but often more on moving data, between the levels of a memory hierarchy and between parallel computing entities. Judging by the hardware evolution of the last few decades, the fraction of running time spent on communication is expected to increase, and with it - the demand for communication-avoiding algorithms. We use geometric, combinatorial, and algebraic ideas and techniques, some of which are known in the context of expander graphs, to construct provably communication-optimal algorithms.