2 papers
cs.CC2024
Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits
Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi +1
We design a deterministic subexponential time algorithm that takes as input a multivariate polynomial computed by a constant-depth circuit over rational numbers, and outputs a…
cs.CC2023
Determinants vs. Algebraic Branching Programs
Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk
We show that for every homogeneous polynomial of degree , if it has determinantal complexity at most , then it can be computed by a homogeneous algebraic branching program (A…