Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Varun Ramanathan:

TR23-139 | 18th September 2023
Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi

Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits

For every constant $d$, we design a subexponential time deterministic algorithm that takes as input a multivariate polynomial $f$ given as a constant depth algebraic circuit over the field of rational numbers, and outputs all irreducible factors of $f$ of degree at most $d$ together with their respective multiplicities. Moreover, ... more >>>

ISSN 1433-8092 | Imprint