Computer Science and Discrete Mathematics (CSDM)

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...

Many polynomial-time solvable (combinatorial) optimization problems can be reduced to the feasibility problem and the intersection problem. In this talk, I will present the first nearly cubic time algorithm for both problems using a new cutting...

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...

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...

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...

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...

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...

Vapnik's fundamental theorem of statistical learning establishes a computational equivalence between optimization (empirical risk minimization) and learning in the statistical setting. Is the same true for learning in games? We give a precise answer...

The Ramsey number of a graph $G$ is the minimum integer $n$ for which every edge-coloring of the complete graph on $n$ vertices with two colors contains a monochromatic copy of $G$. A graph is $d$-degenerate if all its subgraphs have a vertex of...

We explicitly construct an extractor for two independent sources on $n$ bits, each with min-entropy at least $\log^C n$ for a large enough constant $C$. Our extractor outputs one bit and has error $n^{-\Omega(1)}$. The best previous extractor, by...