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 (with Amir Yehudayoff).
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: winter 2019, autumn 2015 (reviews)
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: autumn 2018 (reviews), spring 2016, spring 2013
foundations of computer science 2: winter 2018
algorithms: winter 2015, fall 2014 (reviews), winter 2013, winter 2011, winter 2010

current students:
Sivaramakrishnan Ramamoorthy

former students:
Makrand Sinha

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

publications and talks

economics (a detour)
A Theory of Market Efficiency
[arxiv 2017], Slides, [Code for Demo]
data structures
Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers
with Sivaramakrishnan Natarajan Ramamoorthy.
[CCC 2018]
boolean circuits
Lower Bounds on Balancing Sets and Depth-2 Threshhold Circuits
with Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy and Amir Yehudayoff.
On Expressing Majority as a Majority of Majorities
with Christian Engels, Mohit Garg and Kazuhisa Makino.
[ECCC 2017]
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
Anti-concentration in Most Directions
with Amir Yehudayoff.
[Manuscript 2019]
Tutorial on Coding for Interactive Communication
Simplified Separation of Information and Communication
with Makrand Sinha
[Theory of Computing 2017]
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.