# Computer Science and Discrete Mathematics (CSDM)

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

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

## Algorithmic Dense Model Theorems, Decompositions, and Regularity Theorems

Green and Tao used the existence of a dense subset indistinguishable from the primes under certain tests from a certain class to prove the existence of arbitrarily long prime arithmetic progressions. Reingold, Trevisan, Tulsiani and Vadhan, and independently, Gowers, give a quantitatively improved characterization of when such dense models exist. An equivalent formulation was obtained earlier by Barak, Shaltiel and Wigderson.

## The NOF Communication Complexity of Multiparty Pointer Jumping

We give new results on the number-on-the-forhead (NOF) communication complexity of the multiparty pointer jumping problem.

The origional motivation for this problem comes from circuit complexity. Specifically, there is no explicit function known to lie outside the complexity class ACC0. However, a long line of research in the early 90's showed that a sufficiently strong NOF communication lower bound for a function would place it outside ACC0. Pointer jumping is widely considered to be a strong candidate for such a lower bound.