Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > PRANAV BISHT:
All reports by Author Pranav Bisht:

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

On Solving Sparse Polynomial Factorization Related Problems

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