# Computer Science and Discrete Mathematics (CSDM)

## Settling the complexity of computing approximate two-player Nash equilibria

## Communication complexity of approximate Nash equilibria

For a constant $\epsilon$, we prove a $\mathrm{poly}(N)$ lower bound on the communication complexity of $\epsilon$-Nash equilibrium in two-player $N \times N$ games. For $n$-player binary-action games we prove an $\exp(n)$ lower bound for the communication complexity of $(\epsilon,\epsilon)$-weak approximate Nash equilibrium, which is a profile of mixed actions such that at least $(1-\epsilon)$-fraction of the players are $\epsilon$-best replying. https://arxiv.org/abs/1608.06580 Joint work with Yakov Babichenko.

## Sum of squares, quantum entanglement, and log rank

## On the query complexity of Boolean monotonicity testing

## Real rooted polynomials and multivariate extensions

## Matrix invariants and algebraic complexity theory

## Counting solutions to random constraint satisfaction problems

## Algebraic geometric codes and their applications

## Fourier tails for Boolean functions and their applications

The discrete Fourier transform is a widely used tool in the analysis of Boolean functions. One can view the Fourier transform of a Boolean function $f:\{0,1\}^n \to \{0,1\}$ as a distribution over sets $S \subseteq [n]$. The Fourier-tail at level $k$ is the probability of sampling a set $S$ of size at least $k$.