Mrinal Kumar

According to our database, Mrinal Kumar authored at least 57 papers between 2011 and 2024.

Collaborative distances:

• Dijkstra number of three.
• Erdős number of two.

2024

Towards Deterministic Algorithms for Constant-Depth Factors of Constant-Depth Circuits.

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

Electron. Colloquium Comput. Complex., 2024

2023

Fast, Algebraic Multivariate Multipoint Evaluation in Small Characteristic and Applications.

Vishwas Bhargava, Sumanta Ghosh, Mrinal Kumar, Chandra Kanta Mohapatra

J. ACM, December, 2023

Schur Polynomials Do Not Have Small Formulas If the Determinant does not.

Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan

Comput. Complex., June, 2023

An Improved Line-Point Low-Degree Test.

Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan

Electron. Colloquium Comput. Complex., 2023

Fast list-decoding of univariate multiplicity and folded Reed-Solomon codes.

Rohan Goyal, Prahladh Harsha, Mrinal Kumar, Ashutosh Shankar

Electron. Colloquium Comput. Complex., 2023

Fast Numerical Multivariate Multipoint Evaluation.

Sumanta Ghosh, Prahladh Harsha, Simão Herdade, Mrinal Kumar, Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 2023

Determinants vs. Algebraic Branching Programs.

Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk

Electron. Colloquium Comput. Complex., 2023

Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits.

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 2023

2022

A Polynomial Degree Bound on Equations for Non-rigid Matrices and Small Linear Circuits.

Ben Lee Volk, Mrinal Kumar

ACM Trans. Comput. Theory, 2022

Derandomization from Algebraic Hardness.

Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon

SIAM J. Comput., 2022

Fast Multivariate Multipoint Evaluation Over All Finite Fields.

Vishwas Bhargava, Sumanta Ghosh, Zeyu Guo, Mrinal Kumar, Chris Umans

Electron. Colloquium Comput. Complex., 2022

A Lower Bound on Determinantal Complexity.

Mrinal Kumar, Ben Lee Volk

Comput. Complex., 2022

Quadratic Lower Bounds for Algebraic Branching Programs and Formulas.

Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk

Comput. Complex., 2022

Monotone Circuit Lower Bounds from Robust Sunflowers.

Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman

Algorithmica, 2022

2021

Algorithmizing the Multiplicity Schwartz-Zippel Lemma.

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Ashutosh Shankar

Electron. Colloquium Comput. Complex., 2021

Ideal-theoretic Explanation of Capacity-achieving Decoding.

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan

Electron. Colloquium Comput. Complex., 2021

Lower Bounds for Matrix Factorization.

Ben Lee Volk, Mrinal Kumar

Comput. Complex., 2021

2020

On the Power of Border of Depth-3 Arithmetic Circuits.

Mrinal Kumar

ACM Trans. Comput. Theory, 2020

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

Mrinal Kumar, Ben Lee Volk

Electron. Colloquium Comput. Complex., 2020

If VNP is hard, then so are equations for it.

Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, Anamay Tengse

Electron. Colloquium Comput. Complex., 2020

On the Existence of Algebraically Natural Proofs.

Prerona Chatterjee, Mrinal Kumar, C. Ramya, Ramprasad Saptharishi, Anamay Tengse

Electron. Colloquium Comput. Complex., 2020

Decoding Multivariate Multiplicity Codes on Product Sets.

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan

Electron. Colloquium Comput. Complex., 2020

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

Noga Alon, Mrinal Kumar, Ben Lee Volk

Comb., 2020

2019

Closure Results for Polynomial Factorization.

Chi-Ning Chou, Mrinal Kumar, Noam Solomon

Theory Comput., 2019

The Computational Power of Depth Five Arithmetic Circuits.

Mrinal Kumar, Ramprasad Saptharishi

SIAM J. Comput., 2019

Derandomization from Algebraic Hardness: Treading the Borders.

Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon

Electron. Colloquium Comput. Complex., 2019

Towards Optimal Depth Reductions for Syntactically Multilinear Circuits.

Mrinal Kumar, Rafael Mendes de Oliveira, Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 2019

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

Chi-Ning Chou, Mrinal Kumar, Noam Solomon

Electron. Colloquium Comput. Complex., 2019

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

Prasad Chaugule, Mrinal Kumar, Nutan Limaye, Chandra Kanta Mohapatra, Adrian She, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2019

A Quadratic Lower Bound for Algebraic Branching Programs.

Prerona Chatterjee, Mrinal Kumar, Adrian She, Ben Lee Volk

Electron. Colloquium Comput. Complex., 2019

Hardness-Randomness Tradeoffs for Algebraic Computation.

Mrinal Kumar, Ramprasad Saptharishi

Bull. EATCS, 2019

A quadratic lower bound for homogeneous algebraic branching programs.

Mrinal Kumar

Comput. Complex., 2019

Derandomization from Algebraic Hardness: Treading the Borders.

Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon

Proceedings of the 60th IEEE Annual Symposium on Foundations of Computer Science, 2019

2018

Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits.

Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse

Electron. Colloquium Comput. Complex., 2018

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

Mrinal Kumar

Electron. Colloquium Comput. Complex., 2018

Some Closure Results for Polynomial Factorization and Applications.

Chi-Ning Chou, Mrinal Kumar, Noam Solomon

Electron. Colloquium Comput. Complex., 2018

On Multilinear Forms: Bias, Correlation, and Tensor Rank.

Abhishek Bhrushundi, Prahladh Harsha, Pooya Hatami, Swastik Kopparty, Mrinal Kumar

Electron. Colloquium Comput. Complex., 2018

Hardness vs Randomness for Bounded Depth Arithmetic Circuits.

Chi-Ning Chou, Mrinal Kumar, Noam Solomon

Proceedings of the 33rd Computational Complexity Conference, 2018

2017

Arithmetic Circuits with Locally Low Algebraic Rank.

Mrinal Kumar, Shubhangi Saraf

Theory Comput., 2017

An Almost Quadratic Lower Bound for Syntactically Multilinear Arithmetic Circuits.

Mrinal Kumar, Ben Lee Volk

Electron. Colloquium Comput. Complex., 2017

Towards an algebraic natural proofs barrier via polynomial identity testing.

Joshua A. Grochow, Mrinal Kumar, Michael E. Saks, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2017

2016

Arithmetic Circuit Lower Bounds via Maximum-Rank of Partial Derivative Matrices.

Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma

ACM Trans. Comput. Theory, 2016

Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields.

Swastik Kopparty, Mrinal Kumar, Michael E. Saks

Theory Comput., 2016

Finer separations between shallow arithmetic circuits.

Mrinal Kumar, Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 2016

Functional lower bounds for arithmetic circuits and connections to boolean circuit complexity.

Michael A. Forbes, Mrinal Kumar, Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 2016

The Chasm at Depth Four, and Tensor Rank : Old results, new insights.

Suryajith Chillara, Mrinal Kumar, Ramprasad Saptharishi, V. Vinay

Electron. Colloquium Comput. Complex., 2016

2015

An exponential lower bound for homogeneous depth-5 circuits over finite fields.

Mrinal Kumar, Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 2015

Sums of products of polynomials in few variables : lower bounds and polynomial identity testing.

Mrinal Kumar, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2015

Faster Parameterized Algorithms for Deletion to Split Graphs.

Esha Ghosh, Sudeshna Kolay, Mrinal Kumar, Pranabendu Misra, Fahad Panolan, Ashutosh Rai, M. S. Ramanujan

Algorithmica, 2015

2014

Approximation algorithms for node deletion problems on bipartite graphs with finite forbidden subgraph characterization.

Mrinal Kumar, Sounaka Mishra, N. Safina Devi, Saket Saurabh

Theor. Comput. Sci., 2014

On the power of homogeneous depth 4 arithmetic circuits.

Mrinal Kumar, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2014

2013

Superpolynomial lower bounds for general homogeneous depth 4 arithmetic circuits.

Mrinal Kumar, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2013

The Limits of Depth Reduction for Arithmetic Formulas: It's all about the top fan-in.

Mrinal Kumar, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2013

Lower Bounds for Depth 4 Homogenous Circuits with Bounded Top Fanin.

Mrinal Kumar, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2013

Arithmetic Circuit Lower Bounds via MaxRank.

Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma

Electron. Colloquium Comput. Complex., 2013

2011

A Characterization of all Stable Minimal Separator Graphs

Mrinal Kumar, Gaurav Maheshwari, N. Sadagopan

CoRR, 2011

Approximation Algorithms for Minimum Chain Vertex Deletion.

Mrinal Kumar, Sounaka Mishra, N. Safina Devi, Saket Saurabh

Proceedings of the WALCOM: Algorithms and Computation - 5th International Workshop, 2011