6 papers
On the CGGRT Criterion for Detecting Bipartite Perfect Matchings in NC
Swastik Kopparty, Shubhangi Saraf
The recent breakthrough work of Chatterjee, Ghosh, Gurjar, Raj and Thierauf [CGGRT26] gives the first deterministic NC algorithm for the bipartite matching problem. They show how t…
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…
Integer points in dilates of polytopes
Shubhangi Saraf, Narmada Varadarajan
In this paper we study how the number of integer points in a polytope grows as we dilate the polytope. We prove new and essentially tight bounds on this quantity by specifically st…
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…