1 citations · 1 across the 4 of their papers we have counts for
4 papers · 1 filter
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…
New Bounds for the Ideal Proof System in Positive Characteristic
Amik Raj Behera, Nutan Limaye, Varun Ramanathan +1
In this work, we prove upper and lower bounds over fields of positive characteristics for several fragments of the Ideal Proof System (IPS), an algebraic proof system introduced by…
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…