Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

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.

A local central limit theorem for triangles in a random graph

Swastik Kopparty
March 28, 2016
What is the distribution of the number of triangles in the random graph $G(n, 1/2)$? It was known for a long time that this distribution obeys a central limit theorem: from the point of view of large intervals (~ standard-deviation length), the distribution looks like a Gaussian random variable. We show that it even obeys a LOCAL central limit theorem: the distribution is pointwise close to a suitable discrete Gaussian random variable. Joint work with Justin Gilmer.

The Resolution proof system

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics
March 22, 2016
The Resolution proof system is perhaps the simplest and most universally used in verification system and automated theorem proving. It was introduced by Davis and Putnam in 1960. The study of its efficiency, both in terms of proof length of natural tautologies and in terms of the complexity of finding short proofs has lead over the decades to a rich understanding which is nonetheless incomplete.

Polynomial-time tensor decompositions via sum-of-squares

Tengyu Ma
Princeton University
March 21, 2016
Tensor decompositions have been the key algorithmic components in provable learning of a wide range of hidden variable models such as topic models, Gaussian mixture models, independent component analysis, dictionary learning. Despite its success, one of the challenges in this area is to decompose over-complete 3rd-order tensors robustly.

Proof complexity - an introduction

Avi Wigderson
Herbert H. Maass Professor, School of Mathematics
March 15, 2016
Proof systems pervade all areas of mathematics (often in disguise: e.g. Reidemeister moves is a sound and complete proof system for proving the equivalence of knots given by their diagrams). Proof complexity seeks to to understand the minimal *length* of proofs relative to the length of theorem proved, mainly for propositional proof systems. In this talk I plan to survey some of the main motivations and goals, results and challenges of proof complexity, as well as its connections with circuit complexity.