All reports by Author Mrinal Kumar:

__
TR24-043
| 4th March 2024
__

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Ben Lee Volk#### Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits

__
TR23-185
| 27th November 2023
__

Rohan Goyal, Prahladh Harsha, Mrinal Kumar, A. Shankar#### Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes

Revisions: 3

__
TR23-182
| 21st November 2023
__

Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan#### An Improved Line-Point Low-Degree Test

__
TR23-139
| 18th September 2023
__

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi#### Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits

__
TR23-033
| 24th March 2023
__

Sumanta Ghosh, Prahladh Harsha, Simao Herdade, Mrinal Kumar, Ramprasad Saptharishi#### Fast Numerical Multivariate Multipoint Evaluation

Revisions: 1

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Ben Lee Volk

We design a deterministic subexponential time algorithm that takes as input a multivariate polynomial $f$ computed by a constant-depth circuit over rational numbers, and outputs a list $L$ of circuits (of unbounded depth and possibly with division gates) that contains all irreducible factors of $f$ computable by constant-depth circuits. This ... more >>>

Rohan Goyal, Prahladh Harsha, Mrinal Kumar, A. Shankar

We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon (FRS) codes can be made to run in nearly-linear time. This yields, to the best of our knowledge, the first known family of codes that can be decoded (and encoded) in nearly linear time, even as they ... more >>>

Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan

We prove that the most natural low-degree test for polynomials over finite fields is ``robust'' in the high-error regime for linear-sized fields. Specifically we consider the ``local'' agreement of a function $f\colon \mathbb{F}_q^m \to \mathbb{F}_q$ from the space of degree-$d$ polynomials, i.e., the expected agreement of the function from univariate ... more >>>

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi

For every constant $d$, we design a subexponential time deterministic algorithm that takes as input a multivariate polynomial $f$ given as a constant depth algebraic circuit over the field of rational numbers, and outputs all irreducible factors of $f$ of degree at most $d$ together with their respective multiplicities. Moreover, ... more >>>

Sumanta Ghosh, Prahladh Harsha, Simao Herdade, Mrinal Kumar, Ramprasad Saptharishi

We design nearly-linear time numerical algorithms for the problem of multivariate multipoint evaluation over the fields of rational, real and complex numbers. We consider both \emph{exact} and \emph{approximate} versions of the algorithm. The input to the algorithms are (1) coefficients of an $m$-variate polynomial $f$ with degree $d$ in each ... more >>>