# School of Mathematics

## Testing Correlations and Inverse Theorems

## 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.

## 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.

## Representation Theory and Expansion in Groups III

## Interpreting Polynomial Structure Analytically

## Representation Theory and Expansion in Groups II

## 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 v_{1}, . . . , v_{n}, we define the concentration probability as ρ(V ) := sup_{x} P(v_{1}η_{1} + · · · + v_{n}η_{n} = x).