6 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…
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…
Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits
Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi
For every constant , we design a subexponential time deterministic algorithm that takes as input a multivariate polynomial given as a constant depth algebraic circuit over t…