Prahladh Harsha

Mrinal Kumar

Electron. Colloquium Comput. Complex., 2025

2024

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

[BibT_eX]

[DOI]

Theory Comput., 2024

Sparse juntas on the biased hypercube.

[BibT_eX]

[DOI]

TheoretiCS, 2024

An Improved Line-Point Low-Degree Test.

[BibT_eX]

[DOI]

Mrinal Kumar

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.

[BibT_eX]

[DOI]

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

Dot-Product Proofs and Their Applications.

[BibT_eX]

[DOI]

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

2023

Algorithmizing the Multiplicity Schwartz-Zippel Lemma.

[BibT_eX]

[DOI]

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

Downward Self-Reducibility in TFNP.

[BibT_eX]

[DOI]

Daniel Mitropolsky

Alon Rosen

Proceedings of the 14th Innovations in Theoretical Computer Science Conference, 2023

Fast Numerical Multivariate Multipoint Evaluation.

[BibT_eX]

[DOI]

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

Criticality of AC⁰-Formulae.

[BibT_eX]

[DOI]

Tulasimohan Molli

Proceedings of the 38th Computational Complexity Conference, 2023

2022

Criticality of AC0-Formulae.

[BibT_eX]

[DOI]

Tulasimohan Molli

Electron. Colloquium Comput. Complex., 2022

Criticality of AC0 formulae.

[BibT_eX]

[DOI]

Tulasimohan Molli

CoRR, 2022

Mixing of 3-Term Progressions in Quasirandom Groups.

[BibT_eX]

[DOI]

Amey Bhangale

Sourya Roy

Proceedings of the 13th Innovations in Theoretical Computer Science Conference, 2022

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

[BibT_eX]

[DOI]

Siddharth Bhandari

Proceedings of the 37th Computational Complexity Conference, 2022

2021

Decoding multivariate multiplicity codes on product sets.

[BibT_eX]

[DOI]

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

Explicit SoS Lower Bounds from High-Dimensional Expanders.

[BibT_eX]

[DOI]

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

Ideal-Theoretic Explanation of Capacity-Achieving Decoding.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2021

2020

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Locally testable codes via high-dimensional expanders.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

Rigid Matrices From Rectangular PCPs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2020

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

[BibT_eX]

[DOI]

Siddharth Bhandari

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.

[BibT_eX]

[DOI]

Shubhada Agrawal

Siddharth Bhandari

Anirban Bhattacharjee

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.

[BibT_eX]

[DOI]

Nidhin Koshy Vaidhiyan

CoRR, 2020

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

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2020

2019

On polynomial approximations to AC.

[BibT_eX]

[DOI]

Random Struct. Algorithms, 2019

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

[BibT_eX]

[DOI]

CoRR, 2019

List Decoding with Double Samplers.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

From Local to Robust Testing via Agreement Testing.

[BibT_eX]

[DOI]

Proceedings of the 10th Innovations in Theoretical Computer Science Conference, 2019

Improved 3LIN Hardness via Linear Label Cover.

[BibT_eX]

[DOI]

Devanathan Thiruvenkatachari

Subhash Khot

Euiwoong Lee

Proceedings of the Approximation, 2019

2018

Boolean functions on high-dimensional expanders.

[BibT_eX]

[DOI]

CoRR, 2018

On the Probabilistic Degree of OR over the Reals.

[BibT_eX]

[DOI]

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

Boolean Function Analysis on High-Dimensional Expanders.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2018

2017

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

[BibT_eX]

[DOI]

Theory Comput., 2017

Agreement tests on graphs and hypergraphs.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

Low degree almost Boolean functions are sparse juntas.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2017

On polynomial approximations over ℤ/2kℤ.

[BibT_eX]

[DOI]

Abhishek Bhrushundi

Electron. Colloquium Comput. Complex., 2017

On Polynomial Approximations Over Z/2^kZ*.

[BibT_eX]

[DOI]

Abhishek Bhrushundi

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

Multiplayer Parallel Repetition for Expanding Games.

[BibT_eX]

[DOI]

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

2016

Locally Testable Codes.

[BibT_eX]

[DOI]

Encyclopedia of Algorithms, 2016

Multiplayer parallel repetition for expander games.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2016

Partition Bound Is Quadratically Tight for Product Distributions.

[BibT_eX]

[DOI]

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

Robust Multiplication-Based Tests for Reed-Muller Codes.

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

Amit Deshpande

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.

[BibT_eX]

[DOI]

Proceedings of the Approximation, 2016

2015

Relaxed partition bound is quadratically tight for product distributions.

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2015

Polynomially Low Error PCPs with polyloglogn Queries via Modular Composition.

[BibT_eX]

[DOI]

Guy Kindler

Electron. Colloquium Comput. Complex., 2015

Embedding approximately low-dimensional ℓ22 metrics into ℓ1.

[BibT_eX]

[DOI]

Amit Deshpande

Rakesh Venkat

CoRR, 2015

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

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

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

A Characterization of Hard-to-cover CSPs.

[BibT_eX]

[DOI]

Amey Bhangale

Girish Varma

Proceedings of the 30th Conference on Computational Complexity, 2015

2014

Bounding the Sensitivity of Polynomial Threshold Functions.

[BibT_eX]

[DOI]

Adam R. Klivans

Raghu Meka

Theory Comput., 2014

Super-polylogarithmic hypergraph coloring hardness via low-degree long codes.

[BibT_eX]

[DOI]

Proceedings of the Symposium on Theory of Computing, 2014

2013

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

[BibT_eX]

[DOI]

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

2011

Almost settling the hardness of noncommutative determinant.

[BibT_eX]

[DOI]

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

2010

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

[BibT_eX]

[DOI]

ACM Trans. Comput. Log., 2010

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

[BibT_eX]

[DOI]

CoRR, 2010

An invariance principle for polytopes.

[BibT_eX]

[DOI]

Adam R. Klivans

Raghu Meka

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

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

[BibT_eX]

[DOI]

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

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

[BibT_eX]

[DOI]

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

2009

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

[BibT_eX]

[DOI]

Proceedings of the 50th Annual IEEE Symposium on Foundations of Computer Science, 2009

2008

Complexity of Inference in Graphical Models.

[BibT_eX]

[DOI]

Venkat Chandrasekaran

Nathan Srebro

Proceedings of the UAI 2008, 2008

Minimizing average latency in oblivious routing.

[BibT_eX]

[DOI]

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

Sound 3-Query PCPPs Are Long.

[BibT_eX]

[DOI]

Proceedings of the Automata, Languages and Programming, 35th International Colloquium, 2008

2007

Communication vs. Computation.

[BibT_eX]

[DOI]

Comput. Complex., 2007

The Communication Complexity of Correlation.

[BibT_eX]

[DOI]

David A. McAllester

Proceedings of the 22nd Annual IEEE Conference on Computational Complexity (CCC 2007), 2007

2006

Communicating Distributed H systems with Simple Splicing Rules.

[BibT_eX]

Kamala Krithivasan

Muralidhar Talupur

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

2005

Short PCPs Verifiable in Polylogarithmic Time.

[BibT_eX]

[DOI]

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.

[BibT_eX]

[DOI]

PhD thesis, 2004

Robust pcps of proximity, shorter pcps and applications to coding.

[BibT_eX]

[DOI]

Proceedings of the 36th Annual ACM Symposium on Theory of Computing, 2004

Communication Versus Computation.

[BibT_eX]

[DOI]

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

2003

3CNF Properties are Hard to Test

[BibT_eX]

[DOI]

Sofya Raskhodnikova

Electron. Colloquium Comput. Complex., 2003

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

[BibT_eX]

[DOI]

Electron. Colloquium Comput. Complex., 2003

Some 3CNF properties are hard to test.

[BibT_eX]

[DOI]

Sofya Raskhodnikova

Proceedings of the 35th Annual ACM Symposium on Theory of Computing, 2003

2001

Small PCPs with Low Query Complexity.

[BibT_eX]

[DOI]

Madhu Sudan

Proceedings of the STACS 2001, 2001

1999

Distributed Processing in Automata.

[BibT_eX]

[DOI]

Kamala Krithivasan

M. Sakthi Balan