Computer Science and Discrete Mathematics (CSDM)

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

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

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

Solving the following problem is crucial when compiling for a quantum computer: given a finite set $G$ of elements of $SU(2)$, target element $U$ from $SU(2)$ and real number $\epsilon$ find $g_1,\dotsc, g_N$ from $G$ such that $\| g_1 \dotsm g_N -...

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