All reports by Author Varun Ramanathan:

__
TR24-043
| 4th March 2024
__

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Ben Lee Volk#### Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits

__
TR23-139
| 18th September 2023
__

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi#### Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Ben Lee Volk

We design a deterministic subexponential time algorithm that takes as input a multivariate polynomial $f$ computed by a constant-depth circuit over rational numbers, and outputs a list $L$ of circuits (of unbounded depth and possibly with division gates) that contains all irreducible factors of $f$ computable by constant-depth circuits. This ... more >>>

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi

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