28 citations · 112 across the 18 of their papers we have counts for
20 papers
Ideals, Determinants, and Straightening: Proving and Using Lower Bounds for Polynomial Ideals
Robert Andrews, Michael A. Forbes
We show that any nonzero polynomial in the ideal generated by the minors of an matrix can be used to efficiently approximate the determinant. For any…
Pseudorandom Generators for Read-Once Branching Programs, in any Order
Michael A. Forbes, Zander Kelley
A central question in derandomization is whether randomized logspace (RL) equals deterministic logspace (L). To show that RL=L, it suffices to construct explicit pseudorandom gener…
Spatial Isolation Implies Zero Knowledge Even in a Quantum World
Alessandro Chiesa, Michael A. Forbes, Tom Gur +1
Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowledge can be achieved unconditionally for any…
A PSPACE Construction of a Hitting Set for the Closure of Small Algebraic Circuits
Michael A. Forbes, Amir Shpilka
In this paper we study the complexity of constructing a hitting set for the closure of VP, the class of polynomials that can be infinitesimally approximated by polynomials that are…
A Zero Knowledge Sumcheck and its Applications
Alessandro Chiesa, Michael A. Forbes, Nicholas Spooner
Many seminal results in Interactive Proofs (IPs) use algebraic techniques based on low-degree polynomials, the study of which is pervasive in theoretical computer science. Unfortun…
Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good
Manindra Agrawal, Michael Forbes, Sumanta Ghosh +1
We show that if we can design poly()-time hitting-sets for circuits of size , where is arbitrarily small and the number of variables, or ar…