Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > FACTOR-SPARSITY:
Reports tagged with Factor-Sparsity:
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 >>>




ISSN 1433-8092 | Imprint