5 papers
Deterministic Algorithms for Low Individual Degree Factors of Sparse Polynomials
Somnath Bhattacharjee, Rishabh Kothary, Shanthanu S. Rai +1
We study factoring algorithms for general sparse polynomials and sparse polynomials of bounded individual degree and prove the following results. 1. We give a deterministic polynom…
Modular composition & polynomial GCD in the border of small, shallow circuits
Robert Andrews, Mrinal Kumar, Shanthanu S. Rai
Modular composition is the problem of computing the coefficient vector of the polynomial , given as input the coefficient vectors of univariate polynomials ,…
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…
Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields
Shanthanu S Rai
We present a polynomial-time pseudo-deterministic algorithm for constructing irreducible polynomial of degree over finite field . A pseudo-deterministic algorithm…