Average Sensitivity of Polynomial Threshold Functions
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
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
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
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.
Interpreting Polynomial Structure Analytically
I will be describing recent joint efforts with Tim Gowers to decompose a bounded function into a sum of polynomially structured phases and a uniform error, based on the recent inverse theorem for the Uk norms on Fpn by Bergelson, Tao and Ziegler. The main innovation is the idea of defining the rank of a cubic or higher- degree polynomial (or a locally defined quadratic phase) analytically via the corresponding exponential sum, which turns out to imply all the properties of rank needed in proofs.
A New Approach to the Inverse Littlewood-Offord Problem
Let η1, . . . , ηn be iid Bernoulli random variables, taking values 1, −1 with probability 1/2. Given a multiset V of n integers v1, . . . , vn, we define the concentration probability as ρ(V ) := supx P(v1η1 + · · · + vnηn = x).
Representation Theory and Expansion in Groups
In this survey lecture (which will be continued), I plan to explain basic aspects of the representation theory of finite groups, and how these are applied to various questions regarding expansion and random walks on groups.
Expanders and Communication-Avoiding Algorithms
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.
An Algorithmic Proof of Forster's Lower Bound
We give an algorithmic proof of Forster's Theorem, a fundamental result in communication complexity. Our proof is based on a geometric notion we call radial isotropic position which is related to the well-known isotropic position of a set of vectors. We point out an efficient algorithm to compute the radial isotropic position of a given set of vectors when it exists.
A Parallel Repetition Theorem for Any Interactive Argument
The question whether or not parallel repetition reduces the soundness error is a fundamental question in the theory of protocols. While parallel repetition reduces (at an exponential rate) the error in interactive proofs and (at a weak exponential rate) in special cases of interactive arguments (e.g., 3-message protocols - Bellare, Impagliazzo and Naor [FOCS '97], and public-coin protocols - Håstad, Pass, Pietrzak and WikstrÄm [Manuscript '08]), Bellare et. al gave example of interactive arguments for which parallel repetition does not reduce the soundness error at all.