Ramprasad Saptharishi

According to our database, Ramprasad Saptharishi authored at least 46 papers between 2009 and 2024.

Collaborative distances:

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

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

2023

Near-Optimal Bootstrapping of Hitting Sets for Algebraic Models.

Mrinal Kumar, Ramprasad Saptharishi, Anamay Tengse

Theory Comput., 2023

An Improved Line-Point Low-Degree Test.

Prahladh Harsha, Mrinal Kumar, Ramprasad Saptharishi, Madhu Sudan

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

Deterministic Algorithms for Low Degree Factors of Constant Depth Circuits.

Mrinal Kumar, Varun Ramanathan, Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 2023

2022

Derandomization from Algebraic Hardness.

Zeyu Guo, Mrinal Kumar, Ramprasad Saptharishi, Noam Solomon

SIAM J. Comput., 2022

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

Siddharth Bhandari, Prahladh Harsha, Ramprasad Saptharishi, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2022

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

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

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

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

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

Constructing Faithful Homomorphisms over Fields of Finite Characteristic.

Prerona Chatterjee, Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 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

Efficiently Decoding Reed-Muller Codes From Random Errors.

Ramprasad Saptharishi, Amir Shpilka, Ben Lee Volk

IEEE Trans. Inf. Theory, 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

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

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

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

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

Mrinal Kumar, Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 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

Approaching the Chasm at Depth Four.

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

J. ACM, 2014

Recent Progress on Arithmetic Circuit Lower Bounds.

Ramprasad Saptharishi

Bull. EATCS, 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

Fast Integer Multiplication Using Modular Arithmetic.

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

SIAM J. Comput., 2013

A super-polynomial lower bound for regular arithmetic formulas.

Neeraj Kayal, Chandan Saha, Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 2013

Arithmetic circuits: A chasm at depth three.

Ankit Gupta, Pritish Kamath, Neeraj Kayal, Ramprasad Saptharishi

Electron. Colloquium Comput. Complex., 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

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

2011

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

Electron. Colloquium Comput. Complex., 2011

2009

The Power of Depth 2 Circuits over Algebras.

Chandan Saha, Ramprasad Saptharishi, Nitin Saxena

Electron. Colloquium Comput. Complex., 2009