All reports by Author Pranav Bisht:

__
TR24-041
| 1st March 2024
__

Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich#### Launching Identity Testing into (Bounded) Space

__
TR22-070
| 8th May 2022
__

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

Revisions: 6

__
TR20-042
| 31st March 2020
__

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

Pranav Bisht, Nikhil Gupta, Prajakta Nimbhorkar, Ilya Volkovich

In this work, we initiate the study of the space complexity of the Polynomial Identity Testing problem (PIT).

First, we observe that the majority of the existing (time-)efficient ``blackbox'' PIT algorithms already give rise to space-efficient ``whitebox'' algorithms for the respective classes of arithmetic formulas via a space-efficient ...
more >>>

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