Prahladh Harsha

According to our database, Prahladh Harsha authored at least 76 papers between 1999 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

Sparse juntas on the biased hypercube.

Irit Dinur, Yuval Filmus, Prahladh Harsha

TheoretiCS, 2024

Rigid Matrices from Rectangular PCPs.

Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal

SIAM J. Comput., 2024

Dot-Product Proofs and Their Applications.

Nir Bitansky, Ron D. Rothblum, Prahladh Harsha, Yuval Ishai, David J. Wu

Electron. Colloquium Comput. Complex., 2024

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

Criticality of AC⁰-Formulae.

Prahladh Harsha, Tulasimohan Molli, Ashutosh Shankar

Proceedings of the 38th Computational Complexity Conference, 2023

2022

From Local to Robust Testing via Agreement Testing.

Irit Dinur, Prahladh Harsha, Tali Kaufman, Noga Ron-Zewi

Adv. Math. Commun., 2022

Criticality of AC0-Formulae.

Prahladh Harsha, Tulasimohan Molli, Ashutosh Shankar

Electron. Colloquium Comput. Complex., 2022

Downward Self-Reducibility in TFNP.

Prahladh Harsha, Daniel Mitropolsky, Alon Rosen

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

Criticality of AC⁰ formulae.

Prahladh Harsha, Tulasimohan Molli, Ashutosh Shankar

CoRR, 2022

2021

List-Decoding with Double Samplers.

Irit Dinur, Prahladh Harsha, Tali Kaufman, Inbal Livni Navon, Amnon Ta-Shma

SIAM J. Comput., 2021

Mixing of 3-term progressions in Quasirandom Groups.

Amey Bhangale, Prahladh Harsha, Sourya Roy

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

Explicit SoS Lower Bounds from High-Dimensional Expanders.

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani

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

2020

A Characterization of Hard-to-Cover CSPs.

Amey Bhangale, Prahladh Harsha, Girish Varma

Theory Comput., 2020

Explicit and structured sum of squares lower bounds from high dimensional expanders.

Irit Dinur, Yuval Filmus, Prahladh Harsha, Madhur Tulsiani

Electron. Colloquium Comput. Complex., 2020

Locally testable codes via high-dimensional expanders.

Yotam Dikstein, Irit Dinur, Prahladh Harsha, Noga Ron-Zewi

Electron. Colloquium Comput. Complex., 2020

A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet.

Siddharth Bhandari, Prahladh Harsha

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

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

Rigid Matrices From Rectangular PCPs or: Hard Claims Have Complex Proofs.

Amey Bhangale, Prahladh Harsha, Orr Paradise, Avishay Tal

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

2019

On polynomial approximations to AC.

Prahladh Harsha, Srikanth Srinivasan

Random Struct. Algorithms, 2019

Improved 3LIN Hardness via Linear Label Cover.

Prahladh Harsha, Subhash Khot, Euiwoong Lee, Devanathan Thiruvenkatachari

Electron. Colloquium Comput. Complex., 2019

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

Prahladh Harsha, Ramprasad Saptharishi

CoRR, 2019

Analyzing Boolean functions on the biased hypercube via higher-dimensional agreement tests: [Extended abstract].

Irit Dinur, Yuval Filmus, Prahladh Harsha

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

2018

Boolean function analysis on high-dimensional expanders.

Irit Dinur, Yotam Dikstein, Yuval Filmus, Prahladh Harsha

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

On the Probabilistic Degree of OR over the Reals.

Siddharth Bhandari, Prahladh Harsha, Tulasimohan Molli, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2018

Boolean functions on high-dimensional expanders.

Yotam Dikstein, Irit Dinur, Yuval Filmus, Prahladh Harsha

CoRR, 2018

2017

Special Issue: CCC 2016: Guest Editor's Foreword.

Prahladh Harsha

Theory Comput., 2017

Super-Polylogarithmic Hypergraph Coloring Hardness via Low-Degree Long Codes.

Venkatesan Guruswami, Prahladh Harsha, Johan Håstad, Srikanth Srinivasan, Girish Varma

SIAM J. Comput., 2017

Agreement tests on graphs and hypergraphs.

Irit Dinur, Yuval Filmus, Prahladh Harsha

Electron. Colloquium Comput. Complex., 2017

Low degree almost Boolean functions are sparse juntas.

Irit Dinur, Yuval Filmus, Prahladh Harsha

Electron. Colloquium Comput. Complex., 2017

On polynomial approximations over ℤ/2^kℤ.

Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2017

On Polynomial Approximations Over Z/2^kZ*.

Abhishek Bhrushundi, Prahladh Harsha, Srikanth Srinivasan

Proceedings of the 34th Symposium on Theoretical Aspects of Computer Science, 2017

Multiplayer Parallel Repetition for Expanding Games.

Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

Proceedings of the 8th Innovations in Theoretical Computer Science Conference, 2017

2016

Locally Testable Codes.

Prahladh Harsha

Encyclopedia of Algorithms, 2016

Robust Multiplication-based Tests for Reed-Muller Codes.

Prahladh Harsha, Srikanth Srinivasan

Electron. Colloquium Comput. Complex., 2016

Multiplayer parallel repetition for expander games.

Irit Dinur, Prahladh Harsha, Rakesh Venkat, Henry Yuen

Electron. Colloquium Comput. Complex., 2016

Partition Bound Is Quadratically Tight for Product Distributions.

Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan

Proceedings of the 43rd International Colloquium on Automata, Languages, and Programming, 2016

Embedding Approximately Low-Dimensional l_2^2 Metrics into l_1.

Amit Deshpande, Prahladh Harsha, Rakesh Venkat

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

On Polynomial Approximations to AC^0.

Prahladh Harsha, Srikanth Srinivasan

Proceedings of the Approximation, 2016

2015

Relaxed partition bound is quadratically tight for product distributions.

Prahladh Harsha, Rahul Jain, Jaikumar Radhakrishnan

Electron. Colloquium Comput. Complex., 2015

Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition.

Irit Dinur, Prahladh Harsha, Guy Kindler

Electron. Colloquium Comput. Complex., 2015

Embedding approximately low-dimensional ℓ_2² metrics into ℓ₁.

Amit Deshpande, Prahladh Harsha, Rakesh Venkat

CoRR, 2015

Polynomially Low Error PCPs with polyloglog n Queries via Modular Composition.

Irit Dinur, Prahladh Harsha, Guy Kindler

Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, 2015

Derandomized Graph Product Results Using the Low Degree Long Code.

Irit Dinur, Prahladh Harsha, Srikanth Srinivasan, Girish Varma

Proceedings of the 32nd International Symposium on Theoretical Aspects of Computer Science, 2015

2014

Bounding the Sensitivity of Polynomial Threshold Functions.

Prahladh Harsha, Adam R. Klivans, Raghu Meka

Theory Comput., 2014

2013

Composition of Low-Error 2-Query PCPs Using Decodable PCPs.

Irit Dinur, Prahladh Harsha

SIAM J. Comput., 2013

A Strong Direct Product Theorem for the Tribes Function via the Smooth-Rectangle Bound.

Prahladh Harsha, Rahul Jain

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

2011

Almost settling the hardness of noncommutative determinant.

Steve Chien, Prahladh Harsha, Alistair Sinclair, Srikanth Srinivasan

Proceedings of the 43rd ACM Symposium on Theory of Computing, 2011

2010

Lower bounds for bounded depth Frege proofs via Pudlák-Buss games.

Eli Ben-Sasson, Prahladh Harsha

ACM Trans. Comput. Log., 2010

Limits of Approximation Algorithms: PCPs and Unique Games (DIMACS Tutorial Lecture Notes)

Prahladh Harsha, Moses Charikar, Matthew Andrews, Sanjeev Arora, Subhash Khot, Dana Moshkovitz, Lisa Zhang, Ashkan Aazami, Dev Desai, Igor Gorodezky, Geetha Jagannathan, Alexander S. Kulikov, Darakhshan J. Mir, Alantha Newman, Aleksandar Nikolov, David Pritchard, Gwen Spencer

CoRR, 2010

Bounding the average sensitivity and noise sensitivity of polynomial threshold functions.

Ilias Diakonikolas, Prahladh Harsha, Adam R. Klivans, Raghu Meka, Prasad Raghavendra, Rocco A. Servedio, Li-Yang Tan

Proceedings of the 42nd ACM Symposium on Theory of Computing, 2010

Composition of Low-Error 2-Query PCPs Using Decodable PCPs.

Irit Dinur, Prahladh Harsha

Proceedings of the Property Testing - Current Research and Surveys, 2010

2009

An Invariance Principle for Polytopes.

Prahladh Harsha, Adam R. Klivans, Raghu Meka

Electron. Colloquium Comput. Complex., 2009

2008

Complexity of Inference in Graphical Models.

Venkat Chandrasekaran, Nathan Srebro, Prahladh Harsha

Proceedings of the UAI 2008, 2008

Minimizing average latency in oblivious routing.

Prahladh Harsha, Thomas P. Hayes, Hariharan Narayanan, Harald Räcke, Jaikumar Radhakrishnan

Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, 2008

2007

Sound 3-query PCPPs are Long.

Arie Matsliah, Eli Ben-Sasson, Prahladh Harsha, Oded Lachish

Electron. Colloquium Comput. Complex., 2007

Communication vs. Computation.

Prahladh Harsha, Yuval Ishai, Joe Kilian, Kobbi Nissim, Srinivasan Venkatesh

Comput. Complex., 2007

2006

Robust PCPs of Proximity, Shorter PCPs, and Applications to Coding.

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan

SIAM J. Comput., 2006

The communication complexity of correlation.

Prahladh Harsha, Rahul Jain, David A. McAllester, Jaikumar Radhakrishnan

Electron. Colloquium Comput. Complex., 2006

Communicating Distributed H systems with Simple Splicing Rules.

Kamala Krithivasan, Prahladh Harsha, Muralidhar Talupur

Proceedings of the 2006 International Conference on Computer Design & Conference on Computing in Nanotechnology, 2006

2005

Some 3CNF Properties Are Hard to Test.

Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova

SIAM J. Comput., 2005

Short PCPs Verifiable in Polylogarithmic Time.

Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan

Proceedings of the 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 2005

2004

Robust Probabilistically Checkable Proofs of proximity and shorter Robust Probabilistically Checkable Proofs.

Prahladh Harsha

PhD thesis, 2004

Communication Versus Computation.

Prahladh Harsha, Yuval Ishai, Joe Kilian, Kobbi Nissim, Srinivasan Venkatesh

Proceedings of the Automata, Languages and Programming: 31st International Colloquium, 2004

2003

3CNF Properties are Hard to Test

Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova

Electron. Colloquium Comput. Complex., 2003

Lower Bounds for Bounded-Depth Frege Proofs via Buss-Pudlack Games

Eli Ben-Sasson, Prahladh Harsha

Electron. Colloquium Comput. Complex., 2003

2000

Small PCPs with low query complexity.

Prahladh Harsha, Madhu Sudan

Comput. Complex., 2000

1999

Distributed Processing in Automata.

Kamala Krithivasan, M. Sakthi Balan, Prahladh Harsha

Int. J. Found. Comput. Sci., 1999