3 citations · 8 across the 7 of their papers we have counts for
5 papers · 1 filter
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…
Hitting-sets for ROABP and Sum of Set-Multilinear circuits
Manindra Agrawal, Rohit Gurjar, Arpita Korwar +1
We give a -time ( is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious algebraic branching programs (ROABP). Th…
Hitting-sets for low-distance multilinear depth-3
Manindra Agrawal, Rohit Gurjar, Arpita Korwar +1
The depth- model has recently gained much importance, as it has become a stepping-stone to understanding general arithmetic circuits. Its restriction to multilinearity has known…
Quasi-polynomial Hitting-set for Set-depth-Delta Formulas
Manindra Agrawal, Chandan Saha, Nitin Saxena
We call a depth-4 formula C set-depth-4 if there exists a (unknown) partition (X_1,...,X_d) of the variable indices [n] that the top product layer respects, i.e. C(x) = \sum_{i=1}^…
Jacobian hits circuits: Hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits
Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi +1
We present a single, common tool to strictly subsume all known cases of polynomial time blackbox polynomial identity testing (PIT) that have been hitherto solved using diverse tool…