5 papers
Constant-depth circuits for polynomial GCD over any characteristic
Somnath Bhattacharjee, Mrinal Kumar, Shanthanu Rai +3
We show that the GCD of two univariate polynomials can be computed by (piece-wise) algebraic circuits of constant depth and polynomial size over any sufficiently large field, regar…
Closure under factorization from a result of Furstenberg
Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai +3
We show that algebraic formulas and constant-depth circuits are closed under taking factors. In other words, we show that if a multivariate polynomial over a field of characteristi…
Deterministic factorization of constant-depth algebraic circuits in subexponential time
Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan +2
While efficient randomized algorithms for factorization of polynomials given by algebraic circuits have been known for decades, obtaining an even slightly non-trivial deterministic…
On the Existence of Algebraic Natural Proofs
Prerona Chatterjee, Mrinal Kumar, C Ramya +2
The framework of algebraically natural proofs was independently introduced in the works of Forbes, Shpilka and Volk (2018), and Grochow, Kumar, Saks and Saraf (2017), to study the…
Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models
Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse
The Polynomial Ident…