Publications of Prahladh Harsha

[ Papers | Surveys/Lecture Notes | Theses | Important Notes ]


In reverse chronological order.

  1. Mixing of 3-term progressions in Quasirandom Groupsnew
  2. Ideal-theoretic Explanation of Capacity-achieving codes
  3. Decoding Multivariate Multiplicity Codes on Product Sets
  4. City-Scale Agent-Based Simulators for the Study of Non-pharmaceutical Interventions in the Context of the COVID-19 Epidemic
  5. COVID-19 Epidemic in Mumbai: Projections, full economic opening, and containment zones versus contact tracing and testing: An Update
  6. Explicit SoS lower bounds from high-dimensional expanders
  7. COVID-19 Epidemic Study II: Phased Emergence from the Lockdown in Mumbai
  8. Locally testable codes via high-dimensional expanders
  9. Rigid Matrices from Rectangular PCPs or: Hard Claims Have Complex Proofs
  10. A note on the explicit constructions of tree codes over polylogarithmic-sized alphabet
  11. A note on the elementary HDX construction of Kaufman-Oppenheim
  12. Improved Hardness for 3LIN via Linear Label Cover
  13. From Local Testing to Robust Testing via Agreement Testing
  14. On the Probabilistic Degree of OR over the Reals
  15. List Decoding with Double Samplers
  16. On Multilinear Forms: Bias, Correlation, and Tensor Rank
  17. Boolean function analysis on high-dimensional expanders
  18. Agreement tests on graphs and hypergraphs
  19. Low degree almost Boolean functions are sparse juntas
  20. On polynomial approximations over Z/2^kZ
  21. Multiplayer parallel repetition for expander games
  22. Robust Multiplication-based Tests for Reed-Muller Codes
  23. Embedding Approximately Low Dimensional l2-squared metrics into l1
  24. On Polynomial Approximations to AC0
  25. Partition bound is quadratically tight for product distributions
  26. A Characterization of hard-to-cover CSPs
  27. Polynomially low error PCPs with polyloglog n queries via modular composition
  28. Derandomized Graph Product Results using the Low Degree Long Code
  29. Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
  30. A strong direct product theorem for the tribes function via the smooth-rectangle bound
  31. Almost settling the hardness of noncommutative determinant
  32. An invariance principle for polytopes
  33. Bounding the sensitivity of polynomial threshold functions
  34. Composition of low-error 2-query PCPs using decodable PCPs
  35. Complexity of Inference in Graphical Models
  36. Sound 3-query PCPPs are Long
  37. Minimizing Average Latency in Oblivious Routing
  38. The communication complexity of correlation.
  39. Short PCPs verifiable in polylogarithmic time.
  40. Communication vs. Computation.
  41. Robust PCPs of proximity, shorter PCPs and applications to coding.
  42. Some 3CNF properties are hard to test.
  43. Lower bounds for bounded depth Frege proofs via Buss-Pudlák games.
  44. Small PCPs with low query complexity.
  45. Distributed processing in automata.

Surveys/Lecture Notes

  1. DIMACS Tutorial on "Limits of approximation algorithms : PCPs and Unique Games".
  2. CS369E: Expanders in Computer Science (Stanford University, Spring 2005).


  1. Robust PCPs of Proximity and Shorter PCPs.
  2. Small PCPs with low query complexity.
  3. Distributed-Automata and Simple Test Tube Systems.

Important Notes:

Prahladh Harsha