Abstract:
Now that the geometrization conjecture has been proven, and
the virtual Haken conjecture has been proven, what is left in
3-manifold topology? One remaining topic is the computational
complexity of geometric topology problems. How difficult is it to
distinguish the unknot? Or 3-manifolds from each other? The right
approach to these questions is not just to consider quantitative
complexity, i.e., how much work they take for a computer; but also
qualitative complexity, whether there are efficient algorithms with
one or another kind of help. I will discuss various results on this
theme, such as that knottedness and unknottedness are both in NP; and
I will discuss high-dimensional questions for context.
Wednesday, Dec 6
02:00PM
WWH 805
Amir Shpilka (Tel-Aviv University)
Title: A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits
Abstract:
We study the complexity of constructing a hitting set for the class of polynomials that can be infinitesimally
approximated by polynomials that are computed by polynomial sized algebraic circuits, over the real or complex numbers.
Specifically, we show that there is a PSPACE algorithm that given nsr in unary outputs a set of inputs from of
size poly(nsr) , with poly(nsr) bit complexity, that hits all n-variate polynomials of degree r that are the limit
of size s algebraic circuits.
Previously it was known that
a random set of this size is a hitting set, but a construction that is certified to work was only
known in EXPSPACE (or EXPH assuming the generalized Riemann hypothesis). As a corollary we get that
a host of other algebraic problems such as Noether Normalization Lemma, can also be solved in PSPACE
deterministically, where earlier only randomized algorithms and EXPSPACE algorithms (or EXPH
assuming the generalized Riemann hypothesis) were known.
The proof relies on the new
notion of a robust hitting set which is a set of inputs such that any nonzero polynomial that can be
computed by a polynomial size algebraic circuit, evaluates to a not too small value on at least one
element of the set. Proving the existence of such a robust hitting set is the main technical
difficulty in the proof.
Our proof uses
anti-concentration results for polynomials, basic tools from algebraic geometry and the existential
theory of the reals.
Joint work with Michael Forbes.
Monday Dec 11
02:30PM
WWH 705
Justin Thaler (Georgetown University)
Title: The Polynomial Method Strikes Back: Tight Quantum Query Bounds via Dual Polynomials
Abstract: The eps-approximate degree of a Boolean function is the minimum degree of a real polynomial that point-wise approximates f to error eps. Approximate degree has wide-ranging applications in theoretical computer science. As one example, the approximate degree of a function is a lower bound on its quantum query complexity. Despite its importance, the approximate degree of many basic functions has resisted characterization.
In this talk, I will describe recent advances in proving both upper and lower bounds on the approximate degree of specific functions.
These advances yield tight (or nearly tight) bounds on the approximate degree of AC^0, as well as a variety of basic functions. Our approximate degree bounds settle (or nearly settle) the quantum query complexity of many of these functions, including k-distinctness, junta testing, approximating the statistical distance of two distributions, and entropy approximation.
Based on joint work with Mark Bun and Robin Kothari.
