Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR20-042 | 31st March 2020 09:00

Poly-time blackbox identity testing for sum of log-variate constant-width ROABPs


Authors: Pranav Bisht, Nitin Saxena
Publication: 31st March 2020 16:31
Downloads: 154


Blackbox polynomial identity testing (PIT) affords 'extreme variable-bootstrapping' (Agrawal et al, STOC'18; PNAS'19; Guo et al, FOCS'19). This motivates us to study log-variate read-once oblivious algebraic branching programs (ROABP). We restrict width of ROABP to a constant and study the more general sum-of-ROABPs model. We give the first poly($s$)-time blackbox PIT for sum of constant-many, size-$s$, $O(\log s)$-variate constant-width ROABPs. The previous best for this model was quasi-polynomial time (Gurjar et al, CCC'15; CC'16) which is comparable to brute-force in the log-variate setting. Also, we handle unbounded-many such ROABPs if each ROABP computes a homogeneous polynomial.

Our new techniques comprise-- (1) an ROABP computing a homogeneous polynomial can be made syntactically homogeneous in the same width; and (2) overcome the hurdle of unknown variable order in sum-of-ROABPs in the log-variate setting (over any field).

ISSN 1433-8092 | Imprint