Anup Rao

Anup Rao
assistant professor
university of washington

I am interested in theoretical computer science* and am part of the theory group. For a taste, sit in on one of our seminars.

I was a researcher at princeton university, a member of the institute for advanced study, and a graduate student at the university of texas at austin under David Zuckerman.

publications and talks
cv:(pdf), research statement:(pdf)

funding:
NSF CCF-1016565, Sloan Research Fellowship (2011).

graduate classes:
computational complexity theory: winter 2012, spring 2010
combinatorics and complexity theory: fall 2011
information theory applications in computer science: autumn 2010

undergraduate classes:
complexity theory: spring 2013
design and analysis of algorithms: winter 2013, winter 2011, winter 2010

email: anuprao@cs.washington.edu or contact me anonymously
phone: 609-216-2704

physical mailing address:
department of computer science and engineering
box 352350
university of washington
seattle, WA 98195-2350

personal website

publications and talks
something else
Restriction Access with Zeev Dvir, Avi Wigderson and Amir Yehudayoff. [ITCS 2012]
Formulas Resilient to Short-Circuit Errors with Yael Tauman Kalai and Allison Lewko. [FOCS 2012]
communication complexity
Direct Products in Communication Complexity (also listed below) with Mark Braverman, Omri Weinstein, and Amir Yehudayoff. Manuscript (video)
Survey Talk on Direct Sums and Compression in Communication Complexity (video, 2009).
Towards Coding for Maximum Errors in Interactive Communication with Mark Braverman. [STOC 2011] (video)
Information Equals Amortized Communication with Mark Braverman. [FOCS 2011]
How to Compress Interactive Communication (also listed below) with Boaz Barak, Mark Braverman and Xi Chen. [STOC 2010] (video)
hardness amplification
Direct Products in Communication Complexity (also listed below) with Mark Braverman, Omri Weinstein, and Amir Yehudayoff. Manuscript (video)
How to Compress Interactive Communication (also listed above) with Boaz Barak, Mark Braverman and Xi Chen. [STOC 2010] (video)
A Strong Parallel Repetition Theorem for Free Projection Games with Boaz Barak, Ran Raz, Ricky Rosen and Ronen Shaltiel. [Random 2009]
Survey Talk on Recent Parallel Repetition Related Research (keynote format).
Rounding Parallel Repetitions of Unique Games with Boaz Barak, Moritz Hardt, Ishay Haviv, Oded Regev and David Steurer. [FOCS 2008]
Spherical Cubes and Rounding in High Dimensions with Guy Kindler, Ryan O'Donnell and Avi Wigderson. [FOCS 2008]
Parallel Repetition in Projection Games and a Concentration Bound [STOC 2008, SICOMP Special Issue for STOC08] (talk.keynote) (talk.pdf)
derandomization
Pseudorandom Generators for Regular Branching Programs with Mark Braverman, Ran Raz and Amir Yehudayoff. [FOCS 2010] (video)
2-Source Extractors Under Computational Assumptions and Cryptography with Defective Randomness with Yael Tauman Kalai and Xin Li. [FOCS 2009] (hi-res video) (low-res video)
Extractors for Low-Weight Affine Sources [CCC 2009]
Network Extractor Protocols with Yael Tauman Kalai, Xin Li and David Zuckerman. [FOCS 2008] (talk.pdf) (talk.keynote)
Extractors for Three Uneven-Length Sources with David Zuckerman. [Random 2008]
A 2-Source Almost-Extractor for Linear Entropy [Random 2008]
Randomness Extractors for Independent Sources and Applications (Ph.D. Thesis)
An Exposition of Bourgain's 2-Source Extractor [ECCC Technical Report 2007]
2-Source Dispersers for n^o(1) Entropy and Ramsey Graphs Beating the Frankl-Wilson Construction with Boaz Barak, Ronen Shaltiel and Avi Wigderson. [STOC 2006]
Deterministic Extractors for Small Space Sources with Jesse Kamp, Salil Vadhan and David Zuckerman. [STOC 2006, J. of Computer and System Sciences] (talk)
Extractors for a Constant Number of Polynomially Small Min-Entropy Independent Sources [STOC 2006, Volume 39, Issue 1, Siam Journal on Computing]. Co-Winner of the Best Student Paper Award. (video), (talk.ppt)
software engineering
A Technique for Dynamic Updating of Java Software with Alessandro Orso and Mary Jean Harrold. International Conference on Software Maintanence 2002, pp. 649--658.