Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

Lower bounds on the size of semidefinite programming relaxations

David Steurer
Cornell University
November 30, 2015
We introduce a method for proving lower bounds on the efficacy of semidefinite programming (SDP) relaxations for combinatorial problems. In particular, we show that the cut, TSP, and stable set polytopes on $n$-vertex graphs are not the linear image of the feasible region of any SDP (i.e., any spectrahedron) of dimension less than $2^{n^{\delta}}$, for some constant $\delta > 0$. This result yields the first super-polynomial lower bounds on the semidefinite extension complexity of any explicit family of polytopes.

General systems of linear forms: equidistribution and true complexity

Pooya Hatami
Member, School of Mathematics
November 24, 2015
Higher-order Fourier analysis is a powerful tool that can be used to analyse the densities of linear systems (such as arithmetic progressions) in subsets of Abelian groups. We are interested in the group $\mathbb{F}_p^n$, for fixed $p$ and large $n$, where it is known that analysing these averages reduces to understanding the joint distribution of a family of sufficiently pseudorandom (formally, high rank) nonclassical polynomials applied to the corresponding system of linear forms.

Advances on Ramsey numbers

Jacob Fox
Stanford University
November 23, 2015
Ramsey theory refers to a large body of deep results in mathematics whose underlying philosophy is captured succinctly by the statement that "Every very large system contains a large well-organized subsystem." Ramsey numbers capture how very large the system should be in order for this to be true. Despite much attention, Ramsey numbers are generally not well understood. This talk will discuss some major problems and recent advances in this area.

Cohomology for computer science II

Alex Lubotzky
Hebrew University of Jerusalem
November 17, 2015

We will start with presenting the basic notions of (co)homomology of simplical complexes (which requires only basic linear algebra over the field of order 2) and then we will indicate its relevance for several topics in computer science and combinatorics: 1) Property testing. 2) Quantum error correcting codes (where triangulation of some 4-dim hyperbolic manifolds lead to such codes with unexpected parameters) 3) High dimensional expanders. 4) Random simplical complexes.

Cohomology for computer science

Alex Lubotzky
Hebrew University of Jerusalem
November 17, 2015
We will start with presenting the basic notions of (co)homomology of simplical complexes (which requires only basic linear algebra over the field of order 2) and then we will indicate its relevance for several topics in computer science and combinatorics: 1) Property testing. 2) Quantum error correcting codes (where triangulation of some 4-dim hyperbolic manifolds lead to such codes with unexpected parameters) 3) High dimensional expanders. 4) Random simplical complexes.

Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs II

Gil Cohen
California Institute of Technology
November 3, 2015

In his 1947 paper that inaugurated the probabilistic method, Erdős proved the existence of $2 \log(n)$-Ramsey graphs on $n$ vertices. Matching Erdős' result with a constructive proof is a central problem in combinatorics that has gained a significant attention in the literature. In this talk we will present a recent work towards this goal (http://eccc.hpi-web.de/report/2015/095/).

Two-source dispersers for polylogarithmic entropy and improved Ramsey graphs I

Gil Cohen
California Institute of Technology
November 2, 2015

In his 1947 paper that inaugurated the probabilistic method, Erdős proved the existence of $2 \log(n)$-Ramsey graphs on $n$ vertices. Matching Erdős' result with a constructive proof is a central problem in combinatorics that has gained a significant attention in the literature. In this talk we will present a recent work towards this goal (http://eccc.hpi-web.de/report/2015/095/).

Algorithmic proof of the Lovasz Local Lemma via resampling oracles

Jan Vondrák
IBM Almaden Research Center; Member, School of Mathematics
October 27, 2015
For a collection of events on a probability space with specified dependencies, the Lovasz Local Lemma ("LLL") gives a sufficient condition for the existence of a point avoiding all the events. Following Moser's discovery of an efficient algorithm for many applications of the Lovasz Local Lemma, there has been extensive research on various extensions of this result. We present a unifying algorithmic proof of the Lovasz Local Lemma (and its stronger variants such as Shearer's Lemma), independent of the underlying probability space.