Mrinal Kumar

According to our database, Mrinal Kumar authored at least 63 papers between 2011 and 2025.

Collaborative distances:

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

2025

An exposition of recent list-size bounds of FRS Codes.

Abhibhav Garg, Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Ashutosh Shankar

Electron. Colloquium Comput. Complex., 2025

Constant-depth circuits for polynomial GCD over any characteristic.

Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2025

Closure under factorization from a result of Furstenberg.

Somnath Bhattacharjee, Mrinal Kumar, Shanthanu S. Rai, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2025

Deterministic factorization of constant-depth algebraic circuits in subexponential time.

Somnath Bhattacharjee, Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi, Shubhangi Saraf

Electron. Colloquium Comput. Complex., 2025

High Rate Multivariate Polynomial Evaluation Codes.

Swastik Kopparty, Mrinal Kumar, Harry Sha

Proceedings of the 57th Annual ACM Symposium on Theory of Computing, 2025

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

Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits.

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi

Proceedings of the 2024 ACM-SIAM Symposium on Discrete Algorithms, 2024

Determinants vs. Algebraic Branching Programs.

Abhranil Chatterjee, Mrinal Kumar, Ben Lee Volk

Proceedings of the 15th Innovations in Theoretical Computer Science Conference, 2024

An Improved Line-Point Low-Degree Test.

Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

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

Rohan Goyal, Prahladh Harsha, Mrinal Kumar, Ashutosh Shankar

Proceedings of the 65th IEEE Annual Symposium on Foundations of Computer Science, 2024

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

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models.

Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse

Theory Comput., 2023

Algorithmizing the Multiplicity Schwartz-Zippel Lemma.

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Ashutosh Shankar

Proceedings of the 2023 ACM-SIAM Symposium on Discrete Algorithms, 2023

Fast Numerical Multivariate Multipoint Evaluation.

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

Proceedings of the 64th IEEE Annual Symposium on Foundations of Computer Science, 2023

2022

Derandomization from Algebraic Hardness.

Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon

SIAM J. Comput., 2022

Quadratic Lower Bounds for Algebraic Branching Programs and Formulas.

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

Comput. Complex., 2022

Fast, algebraic multivariate multipoint evaluation in small characteristic and applications.

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

Proceedings of the STOC '22: 54th Annual ACM SIGACT Symposium on Theory of Computing, Rome, Italy, June 20, 2022

If VNP Is Hard, Then so Are Equations for It.

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

Proceedings of the 39th International Symposium on Theoretical Aspects of Computer Science, 2022

Fast Multivariate Multipoint Evaluation Over All Finite Fields.

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

Proceedings of the 63rd IEEE Annual Symposium on Foundations of Computer Science, 2022

2021

Decoding multivariate multiplicity codes on product sets.

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan

Proceedings of the STOC '21: 53rd Annual ACM SIGACT Symposium on Theory of Computing, 2021

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

Mrinal Kumar, Ben Lee Volk

Proceedings of the 12th Innovations in Theoretical Computer Science Conference, 2021

A Lower Bound on Determinantal Complexity.

Mrinal Kumar, Ben Lee Volk

Proceedings of the 36th Computational Complexity Conference, 2021

Ideal-Theoretic Explanation of Capacity-Achieving Decoding.

Siddharth Bhandari, Prahladh Harsha, Mrinal Kumar, Madhu Sudan

Proceedings of the Approximation, 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

Monotone Circuit Lower Bounds from Robust Sunflowers.

Bruno Pasqualotto Cavalar, Mrinal Kumar, Benjamin Rossman

Proceedings of the LATIN 2020: Theoretical Informatics, 2020

On the Existence of Algebraically Natural Proofs.

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

Proceedings of the 61st IEEE Annual Symposium on Foundations of Computer Science, 2020

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

Proceedings of the 35th Computational Complexity Conference, 2020

A Quadratic Lower Bound for Algebraic Branching Programs.

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

Proceedings of the 35th Computational Complexity Conference, 2020

Lower Bounds for Matrix Factorization.

Mrinal Kumar, Ben Lee Volk

Proceedings of the 35th Computational Complexity Conference, 2020

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

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

Proceedings of the Approximation, 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

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

Chi-Ning Chou, Mrinal Kumar, Noam Solomon

Electron. Colloquium Comput. Complex., 2019

Hardness-Randomness Tradeoffs for Algebraic Computation.

Mrinal Kumar, Ramprasad Saptharishi

Bull. EATCS, 2019

Near-optimal Bootstrapping of Hitting Sets for Algebraic Circuits.

Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse

Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, 2019

Towards Optimal Depth Reductions for Syntactically Multilinear Circuits.

Mrinal Kumar, Rafael Mendes de Oliveira, Ramprasad Saptharishi

Proceedings of the 46th International Colloquium on Automata, Languages, and Programming, 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

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

Hardness vs Randomness for Bounded Depth Arithmetic Circuits.

Chi-Ning Chou, Mrinal Kumar, Noam Solomon

Proceedings of the 33rd Computational Complexity Conference, 2018

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

Noga Alon, Mrinal Kumar, Ben Lee Volk

Proceedings of the 33rd Computational Complexity Conference, 2018

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

An Exponential Lower Bound for Homogeneous Depth-5 Circuits over Finite Fields.

Mrinal Kumar, Ramprasad Saptharishi

Proceedings of the 32nd Computational Complexity Conference, 2017

A Quadratic Lower Bound for Homogeneous Algebraic Branching Programs.

Mrinal Kumar

Proceedings of the 32nd Computational Complexity Conference, 2017

2016

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

Mrinal Kumar, Gaurav Maheshwari, Jayalal Sarma

ACM Trans. Comput. Theory, 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

Finer Separations Between Shallow Arithmetic Circuits.

Mrinal Kumar, Ramprasad Saptharishi

Proceedings of the 36th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2016

Functional Lower Bounds for Arithmetic Circuits and Connections to Boolean Circuit Complexity.

Michael A. Forbes, Mrinal Kumar, Ramprasad Saptharishi

Proceedings of the 31st Conference on Computational Complexity, 2016

Sums of Products of Polynomials in Few Variables: Lower Bounds and Polynomial Identity Testing.

Mrinal Kumar, Shubhangi Saraf

Proceedings of the 31st Conference on Computational Complexity, 2016

Arithmetic Circuits with Locally Low Algebraic Rank.

Mrinal Kumar, Shubhangi Saraf

Proceedings of the 31st Conference on Computational Complexity, 2016

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

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

Mrinal Kumar, Shubhangi Saraf

Proceedings of the Symposium on Theory of Computing, 2014

Superpolynomial Lower Bounds for General Homogeneous Depth 4 Arithmetic Circuits.

Mrinal Kumar, Shubhangi Saraf

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

Efficient Indexing of Necklaces and Irreducible Polynomials over Finite Fields.

Swastik Kopparty, Mrinal Kumar, Michael E. Saks

Proceedings of the Automata, Languages, and Programming - 41st International Colloquium, 2014

On the Power of Homogeneous Depth 4 Arithmetic Circuits.

Mrinal Kumar, Shubhangi Saraf

Proceedings of the 55th IEEE Annual Symposium on Foundations of Computer Science, 2014

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

Proceedings of the Automata, Languages, and Programming - 40th International Colloquium, 2013

2012

Faster Parameterized Algorithms for Deletion to Split Graphs.

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

Proceedings of the Algorithm Theory - SWAT 2012, 2012

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