Please note: This seminar will take place in DC 1304 and online.
Abhibhav Garg, Postdoctoral Researcher
David R. Cheriton School of Computer Science
We show that Hilbert’s Nullstellensatz, the problem of deciding if a system of multivariate polynomial equations has a solution in the algebraic closure of the underlying field, lies in the counting hierarchy. More generally, we show that the number of solutions to a system of equations can be computed in polynomial time with oracle access to the counting hierarchy. Our results hold in particular for polynomials with coefficients in either the rational numbers or a finite field. Previously, the best-known bounds on the complexities of these problems were PSPACE and FPSPACE, respectively. Our main technical contribution is the construction of a uniform family of constant-depth arithmetic circuits that compute the multivariate resultant.
To attend this seminar in person, please go to DC 1304. You can also attend virtually on Zoom.