Mrinal Kumar | DeepAI

DeepAI AI Chat

Featured Co-authors

Noga Alon
35 publications
Madhu Sudan
27 publications
Rafael Oliveira
23 publications
Prahladh Harsha
21 publications
Srikanth Srinivasan
18 publications
Chi-Ning Chou
17 publications
Ramprasad Saptharishi
15 publications
Abhranil Chatterjee
11 publications
Ben Lee Volk
11 publications
Zeyu Guo
11 publications
Siddharth Bhandari
10 publications

∙ 09/18/2023

Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits

For every constant d, we design a subexponential time deterministic algo...

0 Mrinal Kumar, et al. ∙

∙ 08/08/2023

Determinants vs. Algebraic Branching Programs

We show that for every homogeneous polynomial of degree d, if it has det...

0 Abhranil Chatterjee, et al. ∙

∙ 04/03/2023

Fast Numerical Multivariate Multipoint Evaluation

We design nearly-linear time numerical algorithms for the problem of mul...

0 Sumanta Ghosh, et al. ∙

∙ 04/30/2022

Fast Multivariate Multipoint Evaluation Over All Finite Fields

Multivariate multipoint evaluation is the problem of evaluating a multiv...

0 Vishwas Bhargava, et al. ∙

∙ 11/15/2021

Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications

Multipoint evaluation is the computational task of evaluating a polynomi...

0 Vishwas Bhargava, et al. ∙

∙ 03/14/2021

Ideal-theoretic Explanation of Capacity-achieving Decoding

In this work, we present an abstract framework for some algebraic error-...

0 Siddharth Bhandari, et al. ∙

∙ 12/13/2020

If VNP is hard, then so are equations for it

Assuming that the Permanent polynomial requires algebraic circuits of ex...

0 Mrinal Kumar, et al. ∙

∙ 12/07/2020

Monotone Circuit Lower Bounds from Robust Sunflowers

Robust sunflowers are a generalization of combinatorial sunflowers that ...

0 Bruno Pasqualotto Cavalar, et al. ∙

∙ 12/02/2020

Decoding Multivariate Multiplicity Codes on Product Sets

The multiplicity Schwartz-Zippel lemma bounds the total multiplicity of ...

0 Siddharth Bhandari, et al. ∙

∙ 09/05/2020

A Lower Bound on Determinantal Complexity

The determinantal complexity of a polynomial P ∈𝔽[x_1, …, x_n] over a fi...

0 Mrinal Kumar, et al. ∙

∙ 04/29/2020

On the Existence of Algebraically Natural Proofs

For every constant c > 0, we show that there is a family {P_N, c} of pol...

0 Prerona Chatterjee, et al. ∙

∙ 03/29/2020

A Polynomial Degree Bound on Defining Equations of Non-rigid Matrices and Small Linear Circuits

We show that there is a defining equation of degree at most 𝗉𝗈𝗅𝗒(n) for ...

0 Mrinal Kumar, et al. ∙

∙ 11/28/2019

Schur Polynomials do not have small formulas if the Determinant doesn't!

Schur Polynomials are families of symmetric polynomials that have been c...

0 Prasad Chaugule, et al. ∙

∙ 11/26/2019

A Quadratic Lower Bound for Algebraic Branching Programs and Formulas

We show that any Algebraic Branching Program (ABP) computing the polynom...

0 Prerona Chatterjee, et al. ∙

∙ 11/26/2019

A Quadratic Lower Bound for Algebraic Branching Programs

We show that any Algebraic Branching Program (ABP) computing the polynom...

0 Prerona Chatterjee, et al. ∙

∙ 04/30/2019

Derandomization from Algebraic Hardness

A hitting-set generator (HSG) is a polynomial map G:F^k →F^n such that f...

0 Zeyu Guo, et al. ∙

∙ 04/30/2019

Derandomization from Algebraic Hardness: Treading the Borders

A hitting-set generator (HSG) is a polynomial map Gen:F^k →F^n such that...

0 Mrinal Kumar, et al. ∙

∙ 04/02/2019

Lower Bounds for Matrix Factorization

We study the problem of constructing explicit families of matrices which...

0 Mrinal Kumar, et al. ∙

∙ 03/06/2019

Closure of VP under taking factors: a short and simple proof

In this note, we give a short, simple and almost completely self contain...

0 Chi-Ning Chou, et al. ∙

∙ 02/19/2019

Towards Optimal Depth Reductions for Syntactically Multilinear Circuits

We show that any n-variate polynomial computable by a syntactically mult...

0 Mrinal Kumar, et al. ∙

∙ 07/17/2018

Near-optimal Bootstrapping of Hitting Sets for Algebraic Models

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel [Ore22,DL78,Zi...

0 Mrinal Kumar, et al. ∙

∙ 07/17/2018

Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits

The classical lemma of Ore-DeMillo-Lipton-Schwartz-Zippel states that an...

0 Mrinal Kumar, et al. ∙

∙ 06/15/2018

Arithmetic Circuits with Locally Low Algebraic Rank

In recent years, there has been a flurry of activity towards proving low...

0 Mrinal Kumar, et al. ∙

∙ 04/24/2018

On Multilinear Forms: Bias, Correlation, and Tensor Rank

In this paper, we prove new relations between the bias of multilinear fo...

0 Abhishek Bhrushundi, et al. ∙

∙ 04/10/2018

On top fan-in vs formal degree for depth-3 arithmetic circuits

We show that over the field of complex numbers, every homogeneous polyno...

0 Mrinal Kumar, et al. ∙

∙ 03/15/2018

Some Closure Results for Polynomial Factorization and Applications

In a sequence of seminal results in the 80's, Kaltofen showed that the c...

0 Chi-Ning Chou, et al. ∙

∙ 08/07/2017

Unbalancing Sets and an Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits

We prove a lower bound of Ω(n^2/^2 n) on the size of any syntactically m...

0 Noga Alon, et al. ∙

Are you a researcher?
Expose your work
to one of the largest
A.I. communities in the world