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

current students:
Makrand Sinha
Sivaramakrishnan Ramamoorthy
Mert Saglam


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

boolean circuits
Circuits with Medium Fan-In
with Pavel Hrubes.
[Manuscript]
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.
[FOCS 2013] (video)
Direct Products via Round-Preserving Compression
with Mark Braverman, Omri Weinstein, and Amir Yehudayoff.
[ICALP 2013]
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.
[FOCS 2013] (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.