11 citations · 18 across the 12 of their papers we have counts for
7 papers · 1 filter
Fast list recovery of univariate multiplicity and folded Reed-Solomon codes
Rohan Goyal, Prahladh Harsha, Mrinal Kumar +1
A recent work of Goyal, Harsha, Kumar and Shankar gave nearly linear time algorithms for the list decoding of Folded Reed-Solomon codes (FRS) and univariate multiplicity codes up t…
Deterministic list decoding of Reed-Solomon codes
Soham Chatterjee, Prahladh Harsha, Mrinal Kumar
We show that Reed-Solomon codes of dimension and block length over any finite field can be deterministically list decoded from agreement in tim…
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…
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…