Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

On the effect of randomness on planted 3-coloring models

Uri Feige
Weizmann Institute of Science
November 21, 2016
The random planted 3-coloring model generates a 3-colorable graph $G$ by first generating a random host graph $H$ of average degree $d$, and then planting in it a random 3-coloring (by giving each vertex a random color and dropping the monochromatic edges). For a sufficiently large constant $c$, Alon and Kahale [SICOMP 1997] presented a spectral algorithm that finds (with high probability) the planted 3-coloring of such graphs whenever $d > c\log n$.

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

Eshan Chattopadhyay
Member, School of Mathematics
November 15, 2016
Seeded and seedless non-malleable extractors are non-trivial generalizations of the more commonly studied seeded and seedless extractors. The original motivation for constructing such non-malleable extractors are from applications to cryptography (privacy amplification and tamper-resilient cryptography). Interestingly, explicitly constructing non-malleable extractors have led to many new connections and progress in pseudoranomness as well.

The mathematics of natural algorithms

Bernard Chazelle
Princeton University
November 14, 2016
I will review some of the recent techniques we've used in our study of natural algorithms. These include Dirichlet series for matrix products, mean-field approximations in opinion dynamics, graph sequence grammars, and tools for renormalizing network-based dynamical systems. If time permits, I will also discuss anti-mixing techniques for self-sustaining iterated learning. The talk will be self-contained and non-technical.

Exact tensor completion via sum of squares

Aaron Potechin
Member, School of Mathematics
November 8, 2016
In the matrix completion problem, we have a matrix $M$ where we are only given a small number of its entries and our goal is to fill in the rest of the entries. While this problem is impossible to solve for general matrices, it can be solved if $M$ has additional structure, such as being low rank. In this talk, I will describe how the matrix completion problem can be solved by nuclear norm minimization and how this can be generalized to tensor completion via the sum of squares hierarchy.

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

Amit Singer
Princeton University
November 7, 2016
Let $G$ be a compact group and let $f_{ij}\in L_2(G)$ be bandlimited functions. We define the Non-Unique Games (NUG) problem as finding $g_1\ldots,g_n\in G$ to minimize $\sum_{i,j=1}^n f_{ij}(g_i g_j^{-1})$. We devise a relaxation of the NUG problem to a semidefinite program (SDP) by taking the Fourier transform of $f_{ij}$ over $G$, which can then be solved efficiently.

Settling the complexity of computing approximate two-player Nash equilibria

Aviad Rubinstein
University of California, Berkeley
November 1, 2016
We prove that there exists a constant $\epsilon > 0$ such that, assuming the Exponential Time Hypothesis for PPAD, computing an $\epsilon$-approximate Nash equilibrium in a two-player ($n \times n$) game requires quasi-polynomial time, $n^{\log^{1-o(1)}n}$. This matches (up to the $o(1)$ term) the algorithm of Lipton, Markakis, and Mehta [LMM03]. Our proof relies on a variety of techniques from the study of probabilistically checkable proofs (PCP); this is the first time that such ideas are used for a reduction between problems inside PPAD.

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.