Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Communication complexity of approximate Nash equilibria

Aviad Rubinstein
University of California, Berkeley
October 31, 2016

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. Joint work with Yakov Babichenko.

Sum of squares, quantum entanglement, and log rank

David Steurer
Cornell University; Member, School of Mathematics
October 25, 2016
The sum-of-squares (SOS) method is a conceptually simple algorithmic technique for polynomial optimization that---quite surprisingly---captures and generalizes the best known efficient algorithms for a wide range of NP-hard optimization problems. For many of these, especially problems related to Khot's Unique Games Conjecture, no strong limitations for SOS are known, unlike for many other algorithmic techniques. Therefore, there is hope that SOS gives efficient algorithms with significantly stronger guarantees than other techniques.

On the query complexity of Boolean monotonicity testing

Xi Chen
Columbia University
October 24, 2016
Monotonicity testing has been a touchstone problem in property testing for more than fifteen years, with many exciting recent developments in just the past few years. When specialized to Boolean-valued functions over $\{0,1\}^n$, we are interested in the number of queries required to distinguish whether an unknown function is monotone or far from every monotone function. In this talk we discuss recent results on Boolean monotonicity testing and some related problems, focusing on the lower bound side.

Real rooted polynomials and multivariate extensions

Adam Marcus
Princeton University; von Neumann Fellow, School of Mathematics
October 18, 2016
I will introduce two notions that generalize the idea of real rootedness to multivariate polynomials: real stability and hyperbolicity. I will then show two applications of these types of polynomials that will (hopefully) be of interest to the CS audience---Gurvits' method for lower bounding the permanent and a generalization of semidefinite programming known as hyperbolic programming.

Matrix invariants and algebraic complexity theory

Harm Derksen
University of Michigan
October 17, 2016
The determinant of an $n\times n$ matrix is an invariant polynomial of degree $n$ that is invariant under left and right multiplication with matrices in ${\rm SL}_n$. It generates in the sense that every other invariant polynomial is a polynomial expression in the determinant. In this talk we consider the simultaneous left and right action of ${\rm SL}_n$ on $m$-tuples of $n\times n$ matrices. I will explain a joint result with Visu Makam that shows that invariants of degree $\leq n^6$ are sufficient to generate all polynomial invariants.

Counting solutions to random constraint satisfaction problems

Allan Sly
Princeton University
September 26, 2016
Random constraint satisfaction problems encode many interesting questions in random graphs such as the chromatic and independence numbers. Ideas from statistical physics provide a detailed description of phase transitions and properties of these models. I will discuss the question of the number of solutions to random regular NAE-SAT. This involves understanding the condensation regime where the model undergoes what is known as a one step replica symmetry breaking transition. We expect these approaches to extend to a range of other models in the same universality class.

Algebraic geometric codes and their applications

Gil Cohen
Princeton University
September 20, 2016
In 1975 Goppa suggested a general method for constructing error correcting codes based on algebraic geometry. In a long line of research such codes were constructed, constituting as a precious example of a construction that beats the probabilistic method (namely, the Gilbert-Varshamov bound). In this talk we give a brief introduction to algebraic geometric codes, and present applications to small-bias sets and, if time permits, also to hitting set generators for low degree polynomials. No prior knowledge in algebraic geometry is assumed.

Fourier tails for Boolean functions and their applications

Avishay Tal
Member, School of Mathematics
May 3, 2016

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

Reed-Muller codes for random erasures and errors

Amir Shpilka
Tel Aviv University
April 26, 2016
Reed-Muller codes encode an $m$-variate polynomial of degree $r$ by evaluating it on all points in $\{0,1\}^m$. Its distance is $2^{m-r}$ and so it cannot correct more than that many errors/erasures in the worst case. For random errors one may hope for a better result. In his seminal paper Shannon exactly determined the amount of errors and erasures one can hope to correct for codes of a given rate. Codes that achieve Shannon's bound are called capacity achieving codes.

A characterization of functions with vanishing averages over products of disjoint sets

Pooya Hatami
Member, School of Mathematics
April 19, 2016
We characterize all complex-valued (Lebesgue) integrable functions $f$ on $[0,1]^m$ such that $f$ vanishes when integrated over the product of $m$ measurable sets which partition $[0,1]$ and have prescribed Lebesgue measures $\alpha_1,\ldots,\alpha_m$. We characterize the Walsh expansion of such functions $f$ via a first variation argument. Janson and Sos asked this analytic question motivated by questions regarding quasi-randomness of graph sequences in the dense model. We use this characterization to answer a few conjectures from [S. Janson and V.