28 citations · 79 across the 28 of their papers we have counts for
Showing 2017Show all
3 papers · 1 filter
cs.CC2017
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…
cs.LG2017★ 3 cited
A learning problem that is independent of the set theory ZFC axioms
Shai Ben-David, Pavel Hrubes, Shay Moran +2
We consider the following statistical estimation problem: given a family F of real valued functions over some domain X and an i.i.d. sample drawn from an unknown distribution P ove…
cs.CC2017★ 1 cited
Succinct Hitting Sets and Barriers to Proving Algebraic Circuits Lower Bounds
Michael A. Forbes, Amir Shpilka, Ben Lee Volk
We formalize a framework of algebraically natural lower bounds for algebraic circuits. Just as with the natural proofs notion of Razborov and Rudich for boolean circuit lower bound…