All reports by Author Pranav Bisht:

__
TR22-070
| 8th May 2022
__

Pranav Bisht, Ilya Volkovich#### On Solving Sparse Polynomial Factorization Related Problems

__
TR20-042
| 31st March 2020
__

Pranav Bisht, Nitin Saxena#### Poly-time blackbox identity testing for sum of log-variate constant-width ROABPs

Pranav Bisht, Ilya Volkovich

In a recent result of Bhargava, Saraf and Volkovich [FOCS’18; JACM’20], the first sparsity bound for constant individual degree polynomials was shown. In particular, it was shown that any factor of a polynomial with at most $s$ terms and individual degree bounded by $d$ can itself have at most $s^{O(d^2\log ... more >>>

Pranav Bisht, Nitin Saxena

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 ... more >>>