The choiceless computation model of Blass, Gurevich and Shelah
(1999, 2002) is an algorithmic framework for computing
isomorphism-invariant properties of unordered structures. Machines
in this model have the power of parallel execution, but lack...
The first lecture in this series is an introduction to the
theory of asymptotic spectra. This theory describes asymptotic
behavior of basic objects in mathematics like graphs and tensors.
Example applications that we will see are the matrix...
A sunflower with $r$ petals is a collection of $r$ sets so that
the intersection of each pair is equal to the intersection of all.
Erdos and Rado in 1960 proved the sunflower lemma: for any fixed
$r$, any family of sets of size $w$, with at least...
Worst-case analysis of algorithms has been the central method of
theoretical computer science for the last 60 years, leading to
great discoveries in algorithm design and a beautiful theory of
computational hardness. However, worst-case analysis...
The seminal result of Kahn, Kalai and Linial implies that a
coalition of a small number of players can bias the outcome of a
Boolean function with respect to the uniform measure. We extend
this result to arbitrary product measures, by combining...
We give a pseudorandom generator that fools $m$-facet polytopes
over $\{0,1\}^n$ with seed length $\mathrm{polylog}(m) \cdot
\mathrm{log}(n)$. The previous best seed length had superlinear
dependence on $m$. An immediate consequence is a...
Are factors of sparse polynomials sparse? This is a really basic
question and we are still quite far from understanding it in
general. In this talk, I will discuss a recent result showing that
this is in some sense true for multivariate polynomials...
Constraint satisfaction problems (CSPs) are a central topic of
study in computer science. A fundamental question about CSPs is as
follows. Given a CSP where each constraint has the form of some
predicate P and almost all of the constraints can be...
I will give a tour of some of the key concepts and ideas in
proof complexity. First, I will define all standard propositional
proof systems using the sequent calculus which gives rise to a
clean characterization of proofs as computationally limited...
We show that, as a consequence of a remarkable new result of
Attila P\'or on universal Tverberg partitions, any large-enough set
$P$ of points in $\Re^d$ has a $(d+2)$-sized subset whose Radon
point has half-space depth at least $c_d \cdot |P|$...
