Mrinal Kumar

Orcid: 0000-0002-6430-0219

Affiliations:
  • Tata Institute of Fundamental Research, Mumbai, India
  • Indian Institute of Technology Bombay, Mumbai, India (former)
  • University of Toronto, Canada (former)
  • Harvard University, Cambridge, MA, USA (former)
  • Rutgers University, Newark, NJ, USA (PhD)


According to our database1, Mrinal Kumar authored at least 58 papers between 2011 and 2024.

Collaborative distances:
  • Dijkstra number2 of three.
  • Erdős number3 of two.

Timeline

Legend:

Book 
In proceedings 
Article 
PhD thesis 
Dataset
Other 

Links

Online presence:

On csauthors.net:

Bibliography

2024
Determinants vs. Algebraic Branching Programs.
Comput. Complex., December, 2024

High Rate Multivariate Polynomial Evaluation Codes.
Electron. Colloquium Comput. Complex., 2024

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits.
Electron. Colloquium Comput. Complex., 2024

2023
Schur Polynomials Do Not Have Small Formulas If the Determinant does not.
Comput. Complex., June, 2023

An Improved Line-Point Low-Degree Test.
Electron. Colloquium Comput. Complex., 2023

Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes.
Electron. Colloquium Comput. Complex., 2023

Fast Numerical Multivariate Multipoint Evaluation.
Electron. Colloquium Comput. Complex., 2023

Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits.
Electron. Colloquium Comput. Complex., 2023

2022
A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits.
ACM Trans. Comput. Theory, 2022

Derandomization from Algebraic Hardness.
SIAM J. Comput., 2022

Fast Multivariate Multipoint Evaluation Over All Finite Fields.
Electron. Colloquium Comput. Complex., 2022

A Lower Bound on Determinantal Complexity.
Comput. Complex., 2022

Quadratic Lower Bounds for Algebraic Branching Programs and Formulas.
Comput. Complex., 2022

2021
Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications.
Electron. Colloquium Comput. Complex., 2021

Algorithmizing the Multiplicity Schwartz-Zippel Lemma.
Electron. Colloquium Comput. Complex., 2021

Ideal-theoretic Explanation of Capacity-achieving Decoding.
Electron. Colloquium Comput. Complex., 2021

Lower Bounds for Matrix Factorization.
Comput. Complex., 2021

2020
On the Power of Border of Depth-3 Arithmetic Circuits.
ACM Trans. Comput. Theory, 2020

A Polynomial Degree Bound on Defining Equations of Non-rigid Matrices and Small Linear Circuits.
Electron. Colloquium Comput. Complex., 2020

If VNP is hard, then so are equations for it.
Electron. Colloquium Comput. Complex., 2020

On the Existence of Algebraically Natural Proofs.
Electron. Colloquium Comput. Complex., 2020

Monotone Circuit Lower Bounds from Robust Sunflowers.
Electron. Colloquium Comput. Complex., 2020

Decoding Multivariate Multiplicity Codes on Product Sets.
Electron. Colloquium Comput. Complex., 2020

Unbalancing Sets and An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits.
Comb., 2020

2019
Closure Results for Polynomial Factorization.
Theory Comput., 2019

The Computational Power of Depth Five Arithmetic Circuits.
SIAM J. Comput., 2019

Derandomization from Algebraic Hardness: Treading the Borders.
Electron. Colloquium Comput. Complex., 2019

Towards Optimal Depth Reductions for Syntactically Multilinear Circuits.
Electron. Colloquium Comput. Complex., 2019

Closure of VP under taking factors: a short and simple proof.
Electron. Colloquium Comput. Complex., 2019

Schur Polynomials do not have small formulas if the Determinant doesn't!
Electron. Colloquium Comput. Complex., 2019

A Quadratic Lower Bound for Algebraic Branching Programs.
Electron. Colloquium Comput. Complex., 2019

Hardness-Randomness Tradeoffs for Algebraic Computation.
Bull. EATCS, 2019

A quadratic lower bound for homogeneous algebraic branching programs.
Comput. Complex., 2019

Derandomization from Algebraic Hardness: Treading the Borders.
Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018
Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits.
Electron. Colloquium Comput. Complex., 2018

On top fan-in vs formal degree for depth-3 arithmetic circuits.
Electron. Colloquium Comput. Complex., 2018

Some Closure Results for Polynomial Factorization and Applications.
Electron. Colloquium Comput. Complex., 2018

On Multilinear Forms: Bias, Correlation, and Tensor Rank.
Electron. Colloquium Comput. Complex., 2018

Hardness vs Randomness for Bounded Depth Arithmetic Circuits.
Proceedings of the 33rd Computational Complexity Conference, 2018

2017
On the Power of Homogeneous Depth 4 Arithmetic Circuits.
SIAM J. Comput., 2017

An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits.
Electron. Colloquium Comput. Complex., 2017

Towards an algebraic natural proofs barrier via polynomial identity testing.
Electron. Colloquium Comput. Complex., 2017

2016
Arithmetic Circuit Lower Bounds via Maximum-Rank of Partial Derivative Matrices.
ACM Trans. Comput. Theory, 2016

Finer separations between shallow arithmetic circuits.
Electron. Colloquium Comput. Complex., 2016

Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity.
Electron. Colloquium Comput. Complex., 2016

The Chasm at Depth Four, and Tensor Rank : Old results, new insights.
Electron. Colloquium Comput. Complex., 2016

2015
The Limits of Depth Reduction for Arithmetic Formulas: It's All About the Top Fan-In.
SIAM J. Comput., 2015

An exponential lower bound for homogeneous depth-5 circuits over finite fields.
Electron. Colloquium Comput. Complex., 2015

Efficient indexing of necklaces and irreducible polynomials over finite fields.
Electron. Colloquium Comput. Complex., 2015

Arithmetic circuits with locally low algebraic rank.
Electron. Colloquium Comput. Complex., 2015

Sums of products of polynomials in few variables : lower bounds and polynomial identity testing.
Electron. Colloquium Comput. Complex., 2015

Faster Parameterized Algorithms for Deletion to Split Graphs.
Algorithmica, 2015

2014
Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization.
Theor. Comput. Sci., 2014

2013
Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits.
Electron. Colloquium Comput. Complex., 2013

Lower Bounds for Depth 4 Homogenous Circuits with Bounded Top Fanin.
Electron. Colloquium Comput. Complex., 2013

Arithmetic Circuit Lower Bounds via MaxRank.
Electron. Colloquium Comput. Complex., 2013

2011
A Characterization of all Stable Minimal Separator Graphs
CoRR, 2011

Approximation Algorithms for Minimum Chain Vertex Deletion.
Proceedings of the WALCOM: Algorithms and Computation - 5th International Workshop, 2011


  Loading...