Seminars

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 continue last week's discussion of this model, this time giving sketches of proofs of some of the theorems. No technical background is necessary for this lecture, but for motivation and background it is good to consult the Tue Feb 11 talk...

The Geometric Complexity Theory (GCT) Program is an approach towards P versus NP and other lower bounds using algebraic geometry and representation theory. In this talk, we discuss how essentially all known algebraic circuit lower bounds and...

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

An error-correcting code is called locally decodable if there exists a decoding algorithm that can recover any symbol of the message with high probability by reading only a small number of symbols of the corrupted codeword. There is a fundamental...

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

In this talk, I'll describe connections between the unique games conjecture (or more precisely, the closely relatedly problem of small-set expansion) and the quantum separability problem. Remarkably, not only are the problems related, but the...

We will discuss space and parallel complexity, ranging from some classical results which motivated the study, to some recent results concerning combinatorial lower bounds in restricted settings. We will highlight some of their connections to boolean...