Publications of Prahladh Harsha

[ Research Papers | Theses | Other Publications | Important Notes ]

Research Papers

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

Theses

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

Other Publications (Surveys/Lecture Notes/Blogposts)

  1. The Blooming of the c3 LTC Flowers [blogpost]
  2. Sampling Spanning Trees using HDXs [exposition]
  3. Research Vignette: The Many Dimensions of High-Dimensional Expanders [blogpost]
  4. Locally testable codes [encyclopedia entry]
  5. DIMACS Tutorial on "Limits of approximation algorithms : PCPs and Unique Games" [lecture notes]
  6. CS369E: Expanders in Computer Science (Stanford University, Spring 2005) [lecture notes]

Important Notes:

Prahladh Harsha