Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SUM OF SET-MULTILINEAR:
Reports tagged with sum of set-multilinear:
TR14-085 | 29th June 2014
Manindra Agrawal, Rohit Gurjar, Arpita Korwar, Nitin Saxena

Hitting-sets for ROABP and Sum of Set-Multilinear circuits

We give a $n^{O(\log n)}$-time ($n$ is the input size) blackbox polynomial identity testing algorithm for unknown-order read-once oblivious algebraic branching programs (ROABP). The best time-complexity known for this class was $n^{O(\log^2 n)}$ due to Forbes-Saptharishi-Shpilka (STOC 2014), and that too only for multilinear ROABP. We get rid of their ... more >>>




ISSN 1433-8092 | Imprint