2020-21 Seminars

In the max cut problem, we are given an n-vertex graph and we are asked what is the maximum fraction of edges "cut" by any partition of the vertices? This problem can be reformulated as an optimization problem over the cut polytope, which has...

Some of the central questions in complexity theory address the amortized complexity of computation (also sometimes known as direct sum problems). While these questions appear in many contexts, they are all variants of the following: 

Is the best...

What edge density of a graph guarantees that that it will contain a particular subgraph? Or one of a given family $\mathcal{F}$ of subgraphs? The celebrated Erdős--Stone--Simonovits Theorem characterizes the maximum edge density in $\mathcal{F}$...

Bernstein's theorem (also known as the Bernstein-Khovanskii-Kushnirenko theorem) gives a bound on the number of nonzero solutions of a polynomial system of equations in terms of the mixed volume of its Newton polytopes. In this talk, we will give...

The celebrated PCP theorem from the 90's shows that any mathematical proof can be encoded in such a way that its correctness can be verified locally by reading only a tiny number of bits from the encoding. This foundational result has had a...

Random sampling a subgraph of a graph is an important algorithmic technique.  Solving some problems on the (smaller) subgraph is naturally faster, and can give either a useful approximate answer, or sometimes even give a result that can be quickly...

For a fixed integer k > 1, the Boolean k-XOR problem consists of a system of linear equations mod 2 with each equation involving exactly k variables. We give an algorithm to strongly refute *semi-random* instances of the Boolean k-XOR problem on n...