Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

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.

Lower bounds for homogeneous depth-5 arithmetic circuits over finite fields

Mrinal Kumar
March 14, 2016
The last few years have seen substantial progress on the question of proving lower bounds for homogeneous depth-4 arithmetic circuits. Even though these results seem to come close to resolving the VP vs VNP question, it seems likely that the techniques involved may not be strong enough for this resolution. However, it is conceivable that we might be able to build upon these ideas to show super-polynomial lower bounds for weaker classes of arithmetic circuits, like arithmetic formula or constant depth circuits.

Fast learning requires good memory: a time-space lower bound for parity learning

Ran Raz
Weizmann Institute of Science; Visiting Professor, School of Mathematics
March 8, 2016
We prove that any algorithm for learning parities requires either a memory of quadratic size or an exponential number of samples. This proves a recent conjecture of Steinhardt, Valiant and Wager and shows that for some learning problems a large storage space is crucial. More formally, in the problem of parity learning, an unknown string $x \in \{0,1\}^n$ was chosen uniformly at random.

Almost optimal sum of squares lower bound for planted clique

Pravesh Kothari
University of Texas, Austin
March 7, 2016
Finding cliques in random graphs and the related planted variant where one wants to recover an added clique of size $k$ added to a random $G(n, 1/2)$ graph, have been extensively studied questions in algorithm design. Despite intense effort, state of the art polynomial time algorithms can find added cliques to random graphs only when $k \gg \sqrt{n}$.This has led to the conjectured hardness of the problem for $k \ll \sqrt{n}$ with many interesting applications.