• Research Publications


• Interests: Several topics in Theoretical Computer Science, including the theory of error-correcting codes, approximation algorithms & non-approximability, pseudorandomness, probabilistically checkable proofs, algebraic algorithms.


• I am a member of the large & diverse theory group at CMU.
  I am also affiliated with CMU's unique ACO program.


• My two main research focuses are
  • Error-correcting codes
    • A survey appearing in CACM Mar'09 (in html format)
    • An NSF news article about our work on list decoding Reed-Solomon codes.
    • Article in Science Magazine on list (and local) decoding.
  • Approximate solutions to NP-hard problems
    • Slides from a tutorial on Approximability of CSPs.


• I gratefully acknowledge the support of
  • NSF CDI Grant (2008)
  • David and Lucile Packard Fellowship (2005)
  • Sloan Research Fellowship (2005)
  • NSF Career Award (2004)

• Current Ph.D.

  • Srivatsan Narayanan
  • Ali Kemal Sinop (co-advised with R. O'Donnell)
  • Yuan Zhou (co-advised with R. O'Donnell)

• Graduated Ph.D.

  • Atri Rudra, Ph.D., 2007.
    • Currently on the faculty at Univ. at Buffalo.
    • Atri's award winning dissertation.
  
  
  • Prasad Raghavendra, Ph.D., 2009.
    • Currently postdoc at MSR, New England;
      to join Georgia Tech's faculty in 2010
    • Prasad's defense of his award winning thesis.

Postdocs

• Current: Rishi Saket
• Parikshit Gopalan, Mar'07-Jun'08.
  • Currently at MSR Silicon Valley.

• Spring'10: Introduction to Coding Theory
• Spring'09: An Intensive Introduction to Computational Complexity Theory
• Spring'07: Discrete Structures
• Winter'07: Essential Complexity Theory
• Autumn'06: Error-Correcting Codes: Constructions and Algorithms
• Winter'06: Design and Analysis of Algorithms
• Fall'05: The PCP Theorem and Hardness of Approximation
• Spring'05: Introduction to Theory of Computation
• Winter'05: Formal Models in Computer Science
• Fall'04: Computability and Complexity
• Spring'04: Discrete Structures
• Fall'03: Computability and Complexity
• Spring'03: Formal Models in Computer Science
• Winter'03: Codes and Pseudorandom Objects
• Fall'02: Computability and Complexity

• Editor, SIAM Journal on Computing
• Editor, ACM Transactions on Computation Theory
• Scientific Board, Electronic Colloquium on Computational Complexity
• Area editor, Encyclopedia of Algorithms
• Guest co-editor:
  • SIAM Journal on Computing (STOC'08 special issue)
  • Computational Complexity (CCC'06 special issue)
  • J. Computer & System Sciences (FOCS'02 special issue)
• Conference Program Committees:
  • CCC 2010, Jun 9-12, 2010, Cambridge, MA.
  • SODA 2010, Jan 17-19, 2010, Austin.
  • FSTTCS 2008, Dec 9-11, 2008, Bangalore.
  • STOC 2008, May 17-20, 2008, Victoria.
  • ITW 2008, May 5-9, 2008, Porto.
  • LATIN 2008, April 7-11, 2008, in Brazil.
  • CATS 2008, January 22-25, 2008.
  • APPROX 2007, Aug 20-22, 2007, Princeton.
  • ISIT 2006, July 9-14, 2006, Seattle.
  • CCC 2006, July 16-20, 2006, Prague.
  • FSTTCS 2005, Dec 15-18, 2005, Hyderabad.
  • FOCS 2005, Oct 23-25, 2005, Pittsburgh.
  • FOCS 2002, Nov 16-19, 2002, Vancouver.