Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > MANINDRA AGRAWAL:
All reports by Author Manindra Agrawal:

TR18-035 | 21st February 2018
Manindra Agrawal, Sumanta Ghosh, Nitin Saxena

Bootstrapping variables in algebraic circuits

We show that for the blackbox polynomial identity testing (PIT) problem it suffices to study circuits that depend only on the first extremely few variables. One only need to consider size-$s$ degree-$s$ circuits that depend on the first $\log^{\circ c} s$ variables (where $c$ is a constant and we are ... more >>>




ISSN 1433-8092 | Imprint