Publications of Prahladh Harsha

Important Notes

In reverse chronological order.

1. Complexity of Inference in Graphical Models
   • Authors: , , and .
   • In Proc. 24th Conference on Uncertainty in Artificial Intelligence, Helsinki, Finland, 9-12 July 2008.
   • [ ps | pdf ]
2. Sound 3-query PCPPs are Long
   • Authors: , , , and .
   • In Proc. 35th International Colloquium of Automata, Language and Programming (ICALP), Part I, volume 5125 of Lecture Notes in Computer Science, pages 686-697, Reykjavik, Iceland, 6-13 July 2008. Springer Verlag. (BibTEX Entry)
   • Technical Report TR07-127, Electronic Colloquium on Computational Complexity, 2007.
   • [ ps | pdf ]
3. Minimizing Average Latency in Oblivious Routing
   • Authors: , , , , and .
   • In Proc. 19th ACM-SIAM Symposium on Discrete Algorithms, pages 200-207, San Francisco, California, 20-22 January 2008. (BibTEX Entry)
   • [ ps | pdf ]
4. The communication complexity of correlation.
   • Authors: , , , and .
   • In Proc. 22nd IEEE Conference on Computational Complexity, pages 10-23, San Diego, California, 13-16 June 2007. (BibTEX Entry)
   • Technical Report TR06-151, Electronic Colloquium on Computational Complexity, 2006.
   • [ ps | pdf | slides ]
5. Short PCPs verifiable in polylogarithmic time.
   • Authors: , , , , and
   • In Proc. 20th IEEE Conference on Computational Complexity, pages 120-134, San Jose, California, 12-15 June 2005. (BibTEX Entry)
   • [ ps | pdf | slides ]
6. Communication vs. Computation.
   • Authors: , , , , and .
   • In Proc. 31st International Colloquium of Automata, Languages and Programming, volume 3142 of Lecture Notes in Computer Science, pages 745-756, Turku, Finland, 12-16 July 2004. Springer-Verlag. (BibTEX Entry)
   • Computational Complexity, 16(1):1-33, 2007. (BibTEX Entry)
     
   • [ ps | pdf | slides ]
7. Robust PCPs of proximity, shorter PCPs and applications to coding.
   • Authors: , , , , and .
   • In Proc. 36th ACM Symp. on Theory of Computing, pages 1-10, Chicago, Illinois, 13-15 June 2004. (BibTEX Entry)
     
   • SIAM Journal on Computing (special issue for Randomness and Computation), 36(4):889-974, 2006. (BibTEX Entry)
     
   • [ ps | pdf | slides ]
8. Some 3CNF properties are hard to test.
   • Authors: , , and .
   • In Proc. 35th ACM Symp. on Theory of Computing, pages 345-354, San Diego, California, 9-11 June 2003. (BibTEX Entry)
   • SIAM Journal on Computing, 35(1):1-21, 2005. (BibTEX Entry)
   • [ ps | pdf | slides ]
9. Lower bounds for bounded depth Frege proofs via Buss-Pudlák games.
   • Authors: , and .
   • Technical Report TR03-004, Electronic Colloquium on Computational Complexity, 2003. (BibTEX Entry)
   • [ ps | pdf ]
10. Small PCPs with low query complexity.
    • Authors: , and .
    • In Proc. 18th Annual Symposium on Theoretical Aspects of Computer Science, volume 2010 of Lecture Notes in Computer Science, pages 327-338, Dresden, Germany, 15-17 February 2001. Springer-Verlag. (BibTEX Entry)
    • Computational Complexity, 9(3-4):157-201, December 2000. (BibTEX Entry)
    • [ ps | pdf | slides ]
11. Distributed processing in automata.
    • Authors: , , and .
    • International Journal of Foundations of Computer Science, 10(4):443-463, December 1999. (BibTEX Entry)
    • [ ps | pdf ]

Theses

1. Robust PCPs of Proximity and Shorter PCPs.
   • Doctoral Thesis. Massachusetts Institute of Technology, Cambridge, MA. Sep 2004.
   • Advisor: Prof. Madhu Sudan.
   • [ html ]
2. Small PCPs with low query complexity.
   • Master's Thesis. Massachusetts Institute of Technology, Cambridge, MA. May 2000.
   • Advisor: Prof. Madhu Sudan.
   • [ ps | pdf ]
3. Distributed-Automata and Simple Test Tube Systems.
   • Undergraduate Thesis. Indian Institute of Technology, Madras (Chennai), May 1998.
   • Advisor: Prof. Kamala Krithivasan

Important Notes:

• Posted Editions: In almost all cases, I will post the most recent manuscript. These might (slightly) differ from the actual journal or conference proceedings version. To obtain the journal or conference version, click on the appropriate journal or conference title and you will be redirected to the location of the paper on the journal/conference-proceedings web-page..
• Copyright notice: The copyrights for journal and conference proceedings papers, prior to March 2008, generally belong to the publisher of the journal or proceedings. Papers published after March 2008 are subject to the MIT copyright amendment. For more information, visit the MIT libraries page on scholarly publications. To create a copyright amendment for your publications, use the MIT copyright amendment tool.
• Free gsview and ghostview viewers for postscript.
• Free Adobe PDF Reader
• If you have trouble downloading these papers, send me email.

Prahladh Harsha