Ramprasad Saptharishi

According to our database, Ramprasad Saptharishi authored at least 50 papers between 2008 and 2025.

Collaborative distances:

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

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

2024

On the Elementary Construction of High-Dimensional Expanders by Kaufman and Oppenheim.

Prahladh Harsha, Ramprasad Saptharishi

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

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

2023

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models.

Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse

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

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

Vanishing Spaces of Random Sets and Applications to Reed-Muller Codes.

Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan

Proceedings of the 37th Computational Complexity Conference, 2022

2020

City-Scale Agent-Based Simulators for the Study of Non-Pharmaceutical Interventions in the Context of the COVID-19 Epidemic.

Shubhada Agrawal, Siddharth Bhandari, Anirban Bhattacharjee, Anand Deo, Narendra M. Dixit, Prahladh Harsha, Sandeep Juneja, Poonam Kesarwani, Aditya Krishna Swamy, Preetam Patil, Nihesh Rathod, Ramprasad Saptharishi, Sharad Shriram, Piyush Srivastava, Rajesh Sundaresan, Nidhin Koshy Vaidhiyan, Sarath Yasodharan

CoRR, 2020

COVID-19 Epidemic Study II: Phased Emergence From the Lockdown in Mumbai.

Prahladh Harsha, Sandeep Juneja, Preetam Patil, Nihesh Rathod, Ramprasad Saptharishi, A. Y. Sarath, Sharad Shriram, Piyush Srivastava, Rajesh Sundaresan, Nidhin Koshy Vaidhiyan

CoRR, 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

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

Hardness-Randomness Tradeoffs for Algebraic Computation.

Mrinal Kumar, Ramprasad Saptharishi

Bull. EATCS, 2019

A note on the elementary HDX construction of Kaufman-Oppenheim.

Prahladh Harsha, Ramprasad Saptharishi

CoRR, 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

Constructing Faithful Homomorphisms over Fields of Finite Characteristic.

Prerona Chatterjee, Ramprasad Saptharishi

Proceedings of the 39th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 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

Quasipolynomial Hitting Sets for Circuits with Restricted Parse Trees.

Ramprasad Saptharishi, Anamay Tengse

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

2017

Quasi-polynomial Hitting Sets for Circuits with Restricted Parse Trees.

Ramprasad Saptharishi, Anamay Tengse

Electron. Colloquium Comput. Complex., 2017

Unexpected power of low-depth arithmetic circuits.

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Commun. ACM, 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

2016

Jacobian Hits Circuits: Hitting Sets, Lower Bounds for Depth-D Occur-k Formulas and Depth-3 Transcendence Degree-k Circuits.

Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

SIAM J. Comput., 2016

Arithmetic Circuits: A Chasm at Depth 3.

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

SIAM J. Comput., 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

Efficiently decoding Reed-Muller codes from random errors.

Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Proceedings of the 48th Annual ACM SIGACT Symposium on Theory of Computing, 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

Identity Testing and Lower Bounds for Read-k Oblivious Algebraic Branching Programs.

Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Proceedings of the 31st Conference on Computational Complexity, 2016

2015

On Fortification of General Games.

Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat

Electron. Colloquium Comput. Complex., 2015

Identity Testing and Lower Bounds for Read-<i>k</i> Oblivious Algebraic Branching Programs.

Matthew Anderson, Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

Electron. Colloquium Comput. Complex., 2015

Decoding high rate Reed-Muller codes from random errors in near linear time.

Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

CoRR, 2015

On Fortification of Projection Games.

Amey Bhangale, Ramprasad Saptharishi, Girish Varma, Rakesh Venkat

Proceedings of the Approximation, 2015

2014

Recent Progress on Arithmetic Circuit Lower Bounds.

Ramprasad Saptharishi

Bull. EATCS, 2014

A super-polynomial lower bound for regular arithmetic formulas.

Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi

Proceedings of the Symposium on Theory of Computing, 2014

Hitting sets for multilinear read-once algebraic branching programs, in any order.

Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka

Proceedings of the Symposium on Theory of Computing, 2014

2013

Pseudorandomness for Multilinear Read-Once Algebraic Branching Programs, in any Order.

Michael A. Forbes, Ramprasad Saptharishi, Amir Shpilka

Electron. Colloquium Comput. Complex., 2013

A Case of Depth-3 Identity Testing, Sparse Factorization and Duality.

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

Comput. Complex., 2013

Arithmetic Circuits: A Chasm at Depth Three.

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Proceedings of the 54th Annual IEEE Symposium on Foundations of Computer Science, 2013

Approaching the Chasm at Depth Four.

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Proceedings of the 28th Conference on Computational Complexity, 2013

2012

An exponential lower bound for homogeneous depth four arithmetic circuits with bounded bottom fanin.

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 2012

Jacobian hits circuits: hitting-sets, lower bounds for depth-D occur-k formulas & depth-3 transcendence degree-k circuits.

Manindra Agrawal, Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

Proceedings of the 44th Symposium on Theory of Computing Conference, 2012

2009

The Power of Depth 2 Circuits over Algebras.

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

Proceedings of the IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science, 2009

2008

Fast integer multiplication using modular arithmetic.

Anindya De, Piyush P. Kurur, Chandan Saha, Ramprasad Saptharishi

Proceedings of the 40th Annual ACM Symposium on Theory of Computing, 2008