Mrinal Kumar 0001

FOCS Conference 2025 Conference Paper

Deterministic factorization of constant-depth algebraic circuits in subexponential time

• Somnath Bhattacharjee
• Mrinal Kumar 0001
• Varun Ramanathan 0002
• Ramprasad Saptharishi
• Shubhangi Saraf

While efficient randomized algorithms for factorization of polynomials given by algebraic circuits have been known for decades, obtaining an even slightly non-trivial deterministic algorithm for this problem has remained an open question of great interest. This is true even when the input algebraic circuit has additional structure, for instance, when it is a constant-depth circuit. Indeed, no efficient deterministic algorithms are known even for the seemingly easier problem of factoring sparse polynomials or even the problem of testing the irreducibility of sparse polynomials. In this work, we make progress on these questions: we design a deterministic algorithm that runs in subexponential time, and when given as input a constant-depth algebraic circuit C over the field of rational numbers, it outputs algebraic circuits (of potentially unbounded depth) for all the irreducible factors of C, together with their multiplicities. In particular, we give the first subexponential time deterministic algorithm for factoring sparse polynomials. For our proofs, we rely on a finer understanding of the structure of power series roots of constant-depth circuits and the analysis of the Kabanets-Impagliazzo generator. In particular, we show that the Kabanets-Impagliazzo generator constructed using low-degree hard polynomials (explicitly constructed in the work of Limaye, Srinivasan & Tavenas) preserves not only the non-zeroness of small constant-depth circuits (as shown by Chou, Kumar & Solomon), but also their irreducibility and the irreducibility of their factors.

STOC Conference 2025 Conference Paper

High Rate Multivariate Polynomial Evaluation Codes

• Swastik Kopparty
• Mrinal Kumar 0001
• Harry Sha

The classical Reed-Muller codes over a finite field F q are based on evaluations of m -variate polynomials of degree at most d over a product set U m , for some d 0. In fact, we give two quite different constructions, and for both we develop efficient decoding algorithms for these codes that can decode from half the minimum distance. The first of these codes is based on evaluating multivariate polynomials on simplex-like sets. The distance of this code is proved via a generalized Schwartz-Zippel lemma on the probability of non-zeroness when evaluating polynomials on sparser subsets of U m – the final bound only depends on the “shape” of the set, and recovers the Schwartz-Zippel bound for the case of the full U m , while still being Ω(1) for much sparser simplex-like subsets of U m . The second of these codes is more algebraic and, surprisingly (to us), has some strong locality properties. It is based on evaluating multivariate polynomials at the intersection points of hyperplanes in general position. It turns out that these evaluation points have many large subsets of collinear points. These subsets form the basis of a simple local characterization, and using some deeper algebraic tools generalizing ideas from Polischuk-Spielman, Raz-Safra, and Ben-Sasson-Sudan, we show that this gives a local test for these codes. Interestingly, the set of evaluation points for these locally testable multivariate polynomial evaluation codes can be as small as O ( d m ), and need not occupy a constant or even noticeable fraction of the full space F q m .

FOCS Conference 2024 Conference Paper

An Improved Line-Point Low-Degree Test

• Prahladh Harsha
• Mrinal Kumar 0001
• Ramprasad Saptharishi
• Madhu Sudan 0001

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: \mathbb{F}_{q}^{m}\rightarrow \mathbb{F}_{q}$ from the space of degree-d polynomials, i. e. , the expected agreement of the function from univariate degree-d polynomials over a randomly chosen line in $\mathbb{F}_{q}^{m}$, and prove that if this local agreement is $\varepsilon\geq\Omega((d/q)^{\tau}))$ for some fixed $\tau > 0$, then there is a global degree-d polynomial $Q: \mathbb{F}_{q}^{m}\rightarrow \mathbb{F}_{q}$ with agreement nearly $\varepsilon$ with $f$. This settles a long-standing open question in the area of low-degree testing, yielding an $O(d)$ -query robust test in the “high-error” regime (i. e. , when $\varepsilon < 1/2)$. The previous results in this space either required $\varepsilon > 1/2$ (Polishchuk & Spielman, STOC 1994), or $q=\Omega(d^{4})$ (Arora & Sudan, Combinatorica 2003), orneeded to measure local distance on 2-dimensional “planes” rather than one-dimensional lines leading to $\Omega(d^{2})$ -query complexity (Raz & Safra, STOC 1997). Our analysis follows the spirit of most previous analyses in first analyzing the low-variable case $(m=O(1))$ and then “boot-strapping” to general multivariate settings. Our main technical novelty is a new analysis in the bivariate setting that exploits a previously known connection between multivariate factorization and finding (or testing) low-degree polynomials, in a non “black-box” manner. This connection was used roughly in a black-box manner in the work of Arora & Sudan — and we show that opening up this black box and making some delicate choices in the analysis leads to our essentially optimal analysis. A second contribution is a bootstrapping analysis which manages to lift analyses for $m=2$ directly to analyses for general $m$, where previous works needed to work with $m=3$ or $m=4$ — arguably this bootstrapping is significantly simpler than those in prior works.

SODA Conference 2024 Conference Paper

Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits

• Mrinal Kumar 0001
• Varun Ramanathan 0002
• Ramprasad Saptharishi

FOCS Conference 2024 Conference Paper

Fast List Decoding of Univariate Multiplicity and Folded Reed-Solomon Codes

• Rohan Goyal
• Prahladh Harsha
• Mrinal Kumar 0001
• Ashutosh Shankar 0001

We show that the known list-decoding algorithms for univariate multiplicity and folded Reed-Solomon (FRS) codes can be made to run in $\tilde{O}(n)$ time. Univariate multiplicity codes and FRS codes are natural variants of Reed-Solomon codes that were discovered and studied for their applications to list decoding. It is known that for every $\varepsilon > 0$, and rate $r\in(0, 1)$, there exist explicit families of these codes that have rate $r$ and can be list decoded from a $(1-r-\varepsilon)$ fraction of errors with constant list size in polynomial time (Guruswami & Wang (IEEE Trans. Inform. Theory 2013) and Kopparty, Ron-Zewi, Saraf & Wootters (SIAM J. Comput. 2023)). In this work, we present randomized algorithms that perform the above list-decoding tasks in $\tilde{O}(n)$, where $n$ is the block-length of the code. Our algorithms have two main components. The first component builds upon the lattice-based approach of Alekhnovich (IEEE Trans. Inf. Theory 2005), who designed a $\tilde{O}(n)$ time list-decoding algorithm for Reed-Solomon codes approaching the Johnson radius. As part of the second component, we design $\tilde{O}(n)$ time algorithms for two natural algebraic problems: given a $(m+2)$ -variate polynomial $Q(x, y_{0}, \ldots, y_{m})=\tilde{Q}(x)+\sum\nolimits_{i=0}^{m} Q_{i}(x) \cdot y_{i}$ the first algorithm solves order-m linear differential equations of the form $Q\left(x, f(x), \frac{d f}{d x}, \ldots, \frac{d^{m} f}{d x^{m}}\right) \equiv 0$ while the second solves functional equations of the form $Q(x, f(x), f(\gamma x), \ldots, f(\gamma^{m}x))\equiv 0$, where $m$ is an arbitrary constant and $\gamma$ is a field element of sufficiently high order. These algorithms can be viewed as generalizations of classical $\tilde{O}(n)$ time algorithms of Sieveking (Computing 1972) and Kung (Numer. Math. 1974) for computing the modular inverse of a power series, and might be of independent interest.

SODA Conference 2023 Conference Paper

Algorithmizing the Multiplicity Schwartz-Zippel Lemma

• Siddharth Bhandari
• Prahladh Harsha
• Mrinal Kumar 0001
• Ashutosh Shankar 0001

FOCS Conference 2023 Conference Paper

Fast Numerical Multivariate Multipoint Evaluation

• Sumanta Ghosh
• Prahladh Harsha
• Simao Herdade
• Mrinal Kumar 0001
• 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 exact and approximate versions of the algorithm. The input to the algorithms are (1) coefficients of an m-variate polynomial f with degree d in each variable, and (2) points $\mathbf{a}_{1}, \ldots, \mathbf{a}_{N}$ each of whose coordinate has absolute value bounded by one. Approximate version: Given additionally an accuracy parameter t, the algorithm computes rational numbers $\beta_{1}, \ldots, \beta_{N}$ such that $\left|f\left(\mathbf{a}_{i}\right)-\beta_{i}\right| \leq 1 / 2^{t}$ for all i, and has a running time of $\left(\left(N m+d^{m}\right) t\right)^{1+o(1)}$ for all m and all sufficiently large d. Exact version (when over rationals): Given additionally a bound s on the bit-complexity of all the rational numbers in the input and output, the algorithm computes the rational numbers $f\left(\mathbf{a}_{1}\right), \ldots, f\left(\mathbf{a}_{N}\right)$, in time $\left(\left(N m+d^{m}\right) s\right)^{1+o(1)}$ for all m and all sufficiently large d. Our results also naturally extend to the case when the input is over the field of real or complex numbers under an appropriate standard model of representation of field elements in such fields. Prior to this work, a nearly-linear time algorithm for multivariate multipoint evaluation (exact or approximate) over any infinite field appears to be known only for the case of univariate polynomials, and was discovered in a recent work of Moroz [Proc. 62nd FOCS, 2021]. In this work, we extend this result from the univariate to the multivariate setting. However, our algorithm is based on ideas that seem to be conceptually different from those of Moroz [Proc. 62nd FOCS, 2021] and crucially relies on a recent algorithm of Bhargava, Ghosh, Guo, Kumar & Umans [Proc. 63rd FOCS, 2022] for multivariate multipoint evaluation over finite fields, and known efficient algorithms for the problems of rational number reconstruction and fast Chinese remaindering in computational number theory.

FOCS Conference 2022 Conference Paper

Fast Multivariate Multipoint Evaluation Over All Finite Fields

• Vishwas Bhargava
• Sumanta Ghosh
• Zeyu Guo 0001
• Mrinal Kumar 0001
• Chris Umans

Multivariate multipoint evaluation is the problem of evaluating a multivariate polynomial, given as a coefficient vector, simultaneously at multiple evaluation points. In this work, we show that there exists a deterministic algorithm for multivariate multipoint evaluation over any finite field F that outputs the evaluations of an m-variate polynomial of degree less than d in each variable at N points in time $(d^{m}+N)^{1+o(1)}$ poly $(m, \ d, \ \log|\mathbb{F}|)$ for all $m\in \mathbb{N}$ and all sufficiently large $d\in \mathbb{N}$. A previous work of Kedlaya and Umans (FOCS 2008, SICOMP 2011) achieved the same time complexity when the number of variables m is at most $d^{o(1)}$ and had left the problem of removing this condition as an open problem. A recent work of Bhargava, Ghosh, Kumar and Mohapatra (STOC 2022) answered this question when the underlying field is not too large and has characteristic less than $d^{o(1)}$. In this work, we remove this constraint on the number of variables over all finite fields, thereby answering the question of Kedlaya and Umans over all finite fields. Our algorithm relies on a non-trivial combination of ideas from three seemingly different previously known algorithms for multivariate multipoint evaluation, namely the algorithms of Kedlaya and Umans, that of Björklund, Kaski and Williams (IPEC 2017, Algorithmica 2019), and that of Bhargava, Ghosh, Kumar and Mohapatra, together with a result of Bombieri and Vinogradov from analytic number theory about the distribution of primes in an arithmetic progression. We also present a second algorithm for multivariate multipoint evaluation that is completely elementary and in particular, avoids the use of the Bombieri-Vinogradov Theorem. However, it requires a mild assumption that the field size is bounded by an exponential-tower in d of bounded height.

STOC Conference 2022 Conference Paper

Fast, algebraic multivariate multipoint evaluation in small characteristic and applications

• Vishwas Bhargava
• Sumanta Ghosh
• Mrinal Kumar 0001
• Chandra Kanta Mohapatra

STOC Conference 2021 Conference Paper

Decoding multivariate multiplicity codes on product sets

• Siddharth Bhandari
• Prahladh Harsha
• Mrinal Kumar 0001
• Madhu Sudan 0001

FOCS Conference 2020 Conference Paper

On the Existence of Algebraically Natural Proofs

• Prerona Chatterjee
• Mrinal Kumar 0001
• C. Ramya
• Ramprasad Saptharishi
• Anamay Tengse

For every constant, we show that there is a family {PN, c} of polynomials whose degree and algebraic circuit complexity are polynomially bounded in the number of variables, that satisfies the following properties: For every family {fn} of polynomials in VP, where fn is an n variate polynomial of degree at most n c with bounded integer coefficients and for N=n c +nn, PN, c vanishes on the coefficient vector of fn. There exists a family {hn} of polynomials where hn is an n variate polynomial of degree at most n c with bounded integer coefficients such that for N=n c +nn, PN, c does not vanish on the coefficient vector of hn. In other words, there are efficiently computable equations for polynomials in VP that have small integer coefficients. In fact, we also prove an analogous statement for the seemingly larger class VNP. Thus, in this setting of polynomials with small integer coefficients, this provides evidence against a natural proof like barrier for proving algebraic circuit lower bounds, a framework for which was proposed in the works of Forbes, Shpilka and Volk [1], and Grochow, Kumar, Saks and Saraf [2]. Our proofs are elementary and rely on the existence of (non-explicit) hitting sets for VP (and VNP) to show that there are efficiently constructible, low degree equations for these classes and also extend to finite fields of small size. Our proofs are elementary and rely on the existence of (non-explicit) hitting sets for VP (and VNP) to show that there are efficiently constructible, low degree equations for these classes and also extend to finite fields of small size.

FOCS Conference 2019 Conference Paper

Derandomization from Algebraic Hardness: Treading the Borders

• Zeyu Guo 0001
• Mrinal Kumar 0001
• Ramprasad Saptharishi
• Noam Solomon

A hitting-set generator (HSG) is a polynomial map Gen: F k → F n such that for all n-variate polynomials Q of small enough circuit size and degree, if Q is non-zero, then Q o Gen is non-zero. In this paper, we give a new construction of such a HSG assuming that we have an explicit polynomial of sufficient hardness in the sense of approximative or border complexity. Formally, we prove the following result over any characteristic zero field F: Suppose P(z 1, .. ., z k ) is an explicit k-variate degree d polynomial that is not in the border of circuits of size s. Then, there is an explicit hitting-set generator Gen(P): F 2k → F n such that every non-zero n-variate degree D polynomial Q(x) in the border of size s' circuits satisfies Q ≠ 0 ⇒ Q o Gen(P) ≠ 0 provided n 10k d Ds' 0 be a constant and k be a large enough constant. Suppose, for every s ≥ k, there is an explicit hitting set of size s k-δ for all degree s polynomials in the border of k-variate size s algebraic circuits. Then, there is an explicit hitting set of size poly(s) for the border s-variate algebraic circuits of size s and degree s. Unlike the prior constructions of such maps (e. g. [NW94], [KI04], [AGS19], [KST19]), our construction is purely algebraic and does not rely on the notion of combinatorial designs.

SODA Conference 2019 Conference Paper

Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits

• Mrinal Kumar 0001
• Ramprasad Saptharishi
• Anamay Tengse

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that any nonzero polynomial f ( x i, …, x n ) of degree at most s will evaluate to a nonzero value at some point on a grid with | S | > s. Thus, there is a deterministic polynomial identity test (PIT) for all degrees size- s algebraic circuits in n variables that runs in time poly( s ) · ( s + 1) n. In a surprising recent result, Agrawal, Ghosh and Saxena (STOC 2018) showed any deterministic blackbox PIT algorithm for degree- s, size- s, n -variate circuits with running time as bad as ( s n 0. 5−δ ) H uge ( n ), where δ > 0 and H uge ( n ) is an arbitrary function, can be used to construct blackbox PIT algorithms for degree- s size s circuits with running time s exp(exp( O (log* s ))). Agrawal et al. asked if a similar conclusion followed if their hypothesis was weakened to having deterministic PIT with running time s o ( n ) · H uge ( n ). In this paper, we answer their question in the affirmative. We show that, given a deterministic blackbox PIT that runs in time s o ( n ) · H uge ( n ) for all degree- s size- s algebraic circuits over n variables, we can obtain a deterministic blackbox PIT that runs in time s exp(exp( O (log* s ))) for all degree- s size- s algebraic circuits over n variables. In other words, any blackbox PIT with just a slightly nontrivial exponent of s compared to the trivial s O ( n ) test can be used to give a nearly polynomial time blackbox PIT algorithm.

FOCS Conference 2014 Conference Paper

On the Power of Homogeneous Depth 4 Arithmetic Circuits

• Mrinal Kumar 0001
• Shubhangi Saraf

We prove exponential lower bounds on the size of homogeneous depth 4 arithmetic circuits computing an explicit polynomial in VP. Our results hold for the Iterated Matrix Multiplication polynomial - in particular we show that any homogeneous depth 4 circuit computing the (1, 1) entry in the product of n generic matrices of dimension n O(1) must have size n Ω(√n). Our results strengthen previous works in two significant ways. 1) Our lower bounds hold for a polynomial in VP. Prior to our work, Kayal et al [KLSSa] proved an exponential lower bound for homogeneous depth 4 circuits (over fields of characteristic zero) computing a poly in VNP. The best known lower bounds for a depth 4 homogeneous circuit computing a poly in VP was the bound of n Ω(log n) by [KLSSb], [KLSSa]. Our exponential lower bounds also give the first exponential separation between general arithmetic circuits and homogeneous depth 4 arithmetic circuits. In particular they imply that the depth reduction results of Koiran [Koi12] and Tavenas [Tav13] are tight even for reductions to general homogeneous depth 4 circuits (without the restriction of bounded bottom fanin). 2) Our lower bound holds over all fields. The lower bound of [KLSSa] worked only over fields of characteristic zero. Prior to our work, the best lower bound for homogeneous depth 4 circuits over fields of positive characteristic was n Ω(log n) [KLSSb], [KLSSa].

STOC Conference 2014 Conference Paper

The limits of depth reduction for arithmetic formulas: it's all about the top fan-in

• Mrinal Kumar 0001
• Shubhangi Saraf

In recent years, a very exciting and promising method for proving lower bounds for arithmetic circuits has been proposed. This method combines the method of depth reduction developed in the works of Agrawal and Vinay[1], Koiran [11] and Tavenas [16], and the use of the shifted partial derivative complexity measure developed in the works of Kayal [9] and Gupta et al [5]. These results inspired a flurry of other beautiful results and strong lower bounds for various classes of arithmetic circuits, in particular a recent work of Kayal et al [10] showing superpolynomial lower bounds for regular arithmetic formulas via an improved depth reduction for these formulas. It was left as an intriguing question if these methods could prove superpolynomial lower bounds for general (homogeneous) arithmetic formulas, and if so this would indeed be a breakthrough in arithmetic circuit complexity. In this paper we study the power and limitations of depth reduction and shifted partial derivatives for arithmetic formulas. We do it via studying the class of depth 4 homogeneous arithmetic circuits. We show: (1) the first superpolynomial lower bounds for the class of homogeneous depth 4 circuits with top fan-in o (log n ). The core of our result is to show improved depth reduction for these circuits. This class of circuits has received much attention for the problem of polynomial identity testing. We give the first nontrivial lower bounds for these circuits for any top fan-in ≥ 2. (2) We show that improved depth reduction is not possible when the top fan-in is Ω(log n ). In particular this shows that the depth reduction procedure of Koiran and Tavenas [11, 16] cannot be improved even for homogeneous formulas, thus strengthening the results of Fournier et al [3] who showed that depth reduction is tight for circuits, and answering some of the main open questions of [10, 3]. Our results in particular suggest that the method of improved depth reduction and shifted partial derivatives may not be powerful enough to prove superpolynomial lower bounds for (even homogeneous) arithmetic formulas.