# Computer Science and Discrete Mathematics (CSDM)

## Theory of accelerated methods

In this talk I will show how to derive the fastest coordinate descent method [1] and the fastest stochastic gradient descent method [2], both from the linear-coupling framework [3]. I will relate them to linear system solving, conjugate gradient method, the Chebyshev approximation theory, and raise several open questions at the end. No prior knowledge is required on first-order methods.

## On the effect of randomness on planted 3-coloring models

## Non-malleable extractors for constant depth circuits, and affine functions

## The mathematics of natural algorithms

## Exact tensor completion via sum of squares

## Non-unique games over compact groups and orientation estimation in cryo-EM

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