Anup Rao
professor
university of washington
anuprao@cs.washington.edu
609-216-2704
publications and talks
graduate classes:
modern coding theory:
fall 2019
communication complexity:
winter 2019
autumn 2015
reviews
algorithms: spring 2014
computational complexity theory:
autumn 2023
spring 2022
winter 2022
spring 2020
winter 2012
spring 2010
combinatorics and complexity theory:
fall 2011
information theory applications in computer science:
autumn 2010
undergraduate classes:
complexity theory:
winter 2023
spring 2021
autumn 2018
reviews
),
spring 2016
spring 2013
foundations of computer science 2:
spring 2019
winter 2018
algorithms:
autumn 2021
autumn 2020
reviews
),
winter 2020
winter 2015
, fall 2014 (
reviews
),
winter 2013
, winter 2011,
winter 2010
book:
current students:
Oscar Sprumont
former students:
Siddharth Iyer
(Phd 2025)
Sivaramakrishnan Ramamoorthy
(Phd 2020)
Makrand Sinha
(Phd 2018)
former postdoc:
Pavel Hrubes
past funding:
NSF Career Award
NSF CCF-1420268
NSF CCF-1524251
BSF 2010089
NSF CCF-1016565
Sloan Research Fellowship
program committees:
STOC 2009
CCC 2011
STOC 2015
RANDOM 2015 (chair)
ITCS 2016
CCC 2016
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.
videos
My
youtube channel
features videos about some topics that I like:
surveys
Communication Complexity
Interactive Coding
technical talks
publications and talks
economics and finance
These papers represent my attempts to do econ and finance:
Six Solutions to the Money Supply Problem
Research Works
2025], [
SSRN
2025]
Decentralized Money Supply: a New Paradigm for Reserve Currencies
Research Works
2025,
SSRN
2025]
Elastic Cash
arxiv
2023]
A Theory of Market Efficiency
arxiv
2017],
Slides
, [
Code for Demo
computation, communication, combinatorics
The Story of Sunflowers
Journal of the London Mathematical Society
, 2025]
An XOR Lemma for Deterministic Communication Complexity
with Siddharth Iyer.
[FOCS 2024]
XOR Lemmas for Communication via Marginal Information
with Siddharth Iyer.
[STOC 2024]
A Criterion for Decoding on the BSC
with Oscar Sprumont.
[Advances in Mathematics of Communication 2024]
Sunflowers: from soil to oil
[Bulletin of the AMS, 2023] [
video
Tight Bounds on the Fourier Growth of Bounded Functions on the Hypercube
with
Siddharth Iyer
Victor Reis
Thomas Rothvoss
and
Amir Yehudayoff
[Manuscript 2021]
Anti-concentration and the Exact Gap-Hamming Problem
with
Amir Yehudayoff
[Siam Journal on Discrete Mathematics 2022], [
video
Coding for Sunflowers
[Discrete Analysis 2020], [
video
Lower Bounds on Balancing Sets and Depth-2 Threshhold Circuits
with Pavel Hrubes, Sivaramakrishnan Natarajan Ramamoorthy and Amir Yehudayoff.
[ICALP 2019]
On Expressing Majority as a Majority of Majorities
with Christian Engels, Mohit Garg and Kazuhisa Makino.
[Siam Journal on Discrete Mathematics 2019]
Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers
with Sivaramakrishnan Natarajan Ramamoorthy.
[CCC 2018]
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]
Forbidden Subgraph Bounds for Parallel Repetition and the Density Hales-Jewett Theorem
with Jan Hazla and Thomas Holenstein.
[Manuscript 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]
Circuits with Medium Fan-In
with Pavel Hrubes.
[CCC 2015]
Direct Products in Communication Complexity
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]
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]
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
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]
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.