Computer Science and Discrete Mathematics (CSDM)

A popular method in combinatorial optimization is to express polytopes \(P\), which may potentially have exponentially many facets, as solutions of linear programs that use few extra variables to reduce the number of constraints down to a polynomial...

The Martians built an amazingly fast computer and they run it to answer the great question of life, the universe and everything. They claim that the answer is 42. Will they be able to convince us that this is the right answer, assuming that we do...

We give two structural results concerning low degree polynomials over the field \(\mathbb{F}_2\). The first states that for any degree d polynomial f in n variables, there exists a subspace of \(\mathbb{F}_2^n\) with dimension \(\Omega(n^{1/(d-1)})\...

How many arithmetic operations does it take to multiply two square matrices? This question has captured the imagination of computer scientists ever since Strassen showed in 1969 that \(O(n^{2.81})\) operations suffice. We survey the classical theory...

The celebrated Green-Tao theorem states that there are arbitrarily long arithmetic progressions in the primes. In this talk, I will explain the ideas of the proof and discuss our recent simplifications. One of the main ingredients in the proof is a...

How many arithmetic operations does it take to multiply two square matrices? This question has captured the imagination of computer scientists ever since Strassen showed in 1969 that \(O(n^{2.81})\) operations suffice. We survey the classical theory...

In this talk, I will describe a new framework for approximately solving flow problems in capacitated, undirected graphs, and I will apply it to find approximately maximum s-t flows in almost-linear time, improving on the best previous bound of \(...

I will survey what is known about the complexity of arithmetic circuits computing polynomials and rational functions with non-commuting variables, focusing on recent results and open problems. Strangely enough, some elementary questions in...

One of the key results in Robertson and Seymour's seminal work on graph minors is the Grid-Minor Theorem (also known as the Excluded Grid Theorem). The theorem states that any graph of treewidth at least \(k\) contains a grid minor of size \(f(k)\)...

Expanders are highly connected sparse graphs. Simplicial complexes are a natural generalization of graphs to higher dimension, and the notions of connectedness and expansion turn out to have interesting analogues, which relate to the homology and...