Computer Science and Discrete Mathematics (CSDM)

Theoretical Computer Science and Discrete Mathematics

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.

Non-constructive combinatorics

Noga Alon
Tel Aviv University; Visiting Professor, School of Mathematics
October 13, 2015
I will describe several old and new applications of topological and algebraic methods in the derivation of combinatorial results. In all of them the proofs provide no efficient solutions for the corresponding algorithmic problems. Finding such solutions is an intriguing challenge.

Factors of polynomials of low individual degree

Rafael Oliveira
Princeton University
October 12, 2015
In [kal89], Kaltofen proved the remarkable fact that multivariate polynomial factorization can be done efficiently, in randomized polynomial time. Still, more than twenty years after Kaltofen's work, many questions remain unanswered regarding the complexity aspects of polynomial factorization, such as the question of whether factors of polynomials efficiently computed by arithmetic formulas also have small arithmetic formulas, asked in [KSS14], and the question of bounding the depth of the circuits computing the factors of a polynomial.

Invariants of random knots

Chaim Even Zohar
Hebrew University of Jerusalem
October 6, 2015
A knot is a closed curve embedded in the three-dimensional space, like a rope whose two ends are joined together. As usual in Topology, two knots are equivalent if one can be deformed into the other by continuous moves, where stretching and squeezing are allowed but with no cutting and pasting. Random curves in space and how they are knotted give an insight into the behavior of "typical" knots and links. They have been studied by biologists and physicists in the context of the structure of random polymers.