Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

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

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

TR22-070 | 8th May 2022
Pranav Bisht, Ilya Volkovich

On Solving Sparse Polynomial Factorization Related Problems

Revisions: 6

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

TR20-042 | 31st March 2020
Pranav Bisht, Nitin Saxena

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

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

ISSN 1433-8092 | Imprint