# Computer Science and Discrete Mathematics (CSDM)

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

## Representation Theory and Expansion in Groups

## Representation Theory and Expansion in Groups I

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