In his seminal work, Valiant defined algebraic analogs for the
classes P and NP, which are known today as VP and VNP. He also
showed that the permanent is VNP-complete (that is, the permanent
is in VNP and any problem in VNP is reducible to it). We...
An affine disperser over F2n for sources of dimension d is a
function f: F2n --> F2 such that for any affine subspace S in
F2n of dimension at least d, we have {f(s) : s in S} = F2 . Affine
dispersers have been considered in the context of...
We prove that every graph has a spectral sparsifier with a
number of edges linear in its
number of vertices. As linear-sized spectral sparsifiers of
complete graphs are expanders, our
sparsifiers of arbitrary graphs can be viewed as
generalizations...
This series of three talks will give a nontechnical, high level
overview of geometric complexity theory (GCT), which is an approach
to the P vs. NP problem via algebraic geometry, representation
theory, and the theory of a new class of quantum...
