Anup Rao


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: Siddharth Iyer
Oscar Sprumont
former students: Makrand Sinha (Phd 2018)
Sivaramakrishnan Ramamoorthy (Phd 2020)
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 the way a mathematician might do it:
Elastic Cash
[arxiv 2023]
A Theory of Market Efficiency
[arxiv 2017], Slides, [Code for Demo]
computation, communication, combinatorics
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.