Loading jsMath...
Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > SHANTHANU RAI:
All reports by Author Shanthanu Rai:

TR25-085 | 28th June 2025
Somnath Bhattacharjee, Mrinal Kumar, Shanthanu Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf

Constant-depth circuits for polynomial GCD over any characteristic

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, regardless of the characteristic. This extends a recent result of Andrews \& Wigderson who showed such an upper bound over fields of zero ... more >>>


TR25-084 | 28th June 2025
Somnath Bhattacharjee, Mrinal Kumar, Shanthanu Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf

Closure under factorization from a result of Furstenberg

We show that algebraic formulas and constant-depth circuits are \emph{closed} under taking factors. In other words, we show that if a multivariate polynomial over a field of characteristic zero has a small constant-depth circuit or formula, then all its factors can be computed by small constant-depth circuits or formulas ... more >>>


TR24-147 | 4th October 2024
Shanthanu Rai

Pseudo-Deterministic Construction of Irreducible Polynomials over Finite Fields

We present a polynomial-time pseudo-deterministic algorithm for constructing irreducible polynomial of degree d over finite field \mathbb{F}_q. A pseudo-deterministic algorithm is allowed to use randomness, but with high probability it must output a canonical irreducible polynomial. Our construction runs in time \tilde{O}(d^4 \log^4{q}).

Our construction extends Shoup's deterministic algorithm ... more >>>




ISSN 1433-8092 | Imprint