Publications of Prahladh Harsha

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


In reverse chronological order.

  1. From Local Testing to Robust Testing via Agreement Testingnew
  2. On the Probabilistic Degree of OR over the Realsnew
  3. List Decoding with Double Samplersnew
  4. On Multilinear Forms: Bias, Correlation, and Tensor Rank
  5. Boolean function analysis on high-dimensional expanders
  6. Agreement tests on graphs and hypergraphs
  7. Low degree almost Boolean functions are sparse juntas
  8. On polynomial approximations over Z/2^kZ
  9. Multiplayer parallel repetition for expander games
  10. Robust Multiplication-based Tests for Reed-Muller Codes
  11. Embedding Approximately Low Dimensional l2-squared metrics into l1
  12. On Polynomial Approximations to AC0
  13. Partition bound is quadratically tight for product distributions
  14. A Characterization of hard-to-cover CSPs
  15. Polynomially low error PCPs with polyloglog n queries via modular composition
  16. Derandomized Graph Product Results using the Low Degree Long Code
  17. Super-polylogarithmic hypergraph coloring hardness via low-degree long codes
  18. A strong direct product theorem for the tribes function via the smooth-rectangle bound
  19. Almost settling the hardness of noncommutative determinant
  20. An invariance principle for polytopes
  21. Bounding the sensitivity of polynomial threshold functions
  22. Composition of low-error 2-query PCPs using decodable PCPs
  23. Complexity of Inference in Graphical Models
  24. Sound 3-query PCPPs are Long
  25. Minimizing Average Latency in Oblivious Routing
  26. The communication complexity of correlation.
  27. Short PCPs verifiable in polylogarithmic time.
  28. Communication vs. Computation.
  29. Robust PCPs of proximity, shorter PCPs and applications to coding.
  30. Some 3CNF properties are hard to test.
  31. Lower bounds for bounded depth Frege proofs via Buss-Pudlák games.
  32. Small PCPs with low query complexity.
  33. 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
Valid HTML 4.01!