Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > HITTING-SET, TINY, ARITY, DEPTH-3, DEPTH-4, DERANDOMIZATION, IDENTITY TESTING, LOWER BOUND, VP:
Reports tagged with hitting-set, tiny, arity, depth-3, depth-4, derandomization, identity testing, lower bound, VP:
TR17-035 | 23rd February 2017
Manindra Agrawal, Michael Forbes, Sumanta Ghosh, Nitin Saxena

Small hitting-sets for tiny arithmetic circuits or: How to turn bad designs into good

Research in the last decade has shown that to prove lower bounds or to derandomize polynomial identity testing (PIT) for general arithmetic circuits it suffices to solve these questions for restricted circuits. In this work, we study the smallest possibly restricted class of circuits, in particular depth-$4$ circuits, which would ... more >>>




ISSN 1433-8092 | Imprint