Anup Rao
Anup Rao
associate 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.

Resources for learning about Communication Complexity:
Draft of a textbook: Communication Complexity.
Introductory lectures: 1, 2, 3, 4.
Tutorial on applications: 1, 2.

publications and talks

funding: NSF Career Award, NSF CCF-1420268, NSF CCF-1524251, BSF 2010089 (with Amir Yehudayoff).
past funding: NSF CCF-1016565, Sloan Research Fellowship (2011).

graduate classes:
communication complexity: autumn 2015
algorithms: spring 2014
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 2016, spring 2013
algorithms: winter 2015, fall 2014, winter 2013, winter 2011, winter 2010

current students:
Makrand Sinha
Sivaramakrishnan Ramamoorthy

former postdocs:
Pavel Hrubes

program committees:
STOC 2009, CCC 2011, STOC 2015, RANDOM 2015 (chair), ITCS 2016, CCC 2016

organized workshops/events:
Communication complexity and applications (BIRS 2014)
Communication complexity session at ITA (ITA 2015)
Trimester on Nexus of Information and Computation at IHP, 1/2016 - 4/2016.

email: 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

A Theory of Market Efficiency
data structures
Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers
with Sivaramakrishnan Natarajan Ramamoorthy.
New Randomized Data Structure Lowerbounds for Dynamic Graph Connectivity
with Sivaramakrishnan Natarajan Ramamoorthy.
boolean circuits
Circuits with Medium Fan-In
with Pavel Hrubes.
[CCC 2015]
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 and applications
Tutorial on Coding for Interactive Communication
Simplified Separation of Information and Communication
with Makrand Sinha
A Direct Sum Theorem for Read-Once Branching Programs
with Makrand Sinha
[Random 2016]
How to Compress Asymmetric Communication
with Sivaramakrishnan Ramamoorthy.
[CCC 2015]
Simplified Lower Bounds on the Multiparty Communication Complexity of Disjointness
with Amir Yehudayoff.
[CCC 2015]
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
Forbidden Subgraph Bounds for Parallel Repetition and the Density Hales-Jewett Theorem
with Jan Hazla and Thomas Holenstein.
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)
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.