Anup Rao


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

A proof of the Prime Number Theorem


Reed-Muller Codes achieve capacity on the Erasure Channel


Must every large set have an arithmetic progression?


Pisier's Inequality for Normed Spaces


The Union-Closed Conjecture


The MM-polar estimate from Convex Geometry


Complexity of Boolean Functions


John's Theorem from Convex Geometry


Using Chebyshev Polynomials to prove Markov's Theorem
surveys
Communication Complexity





Interactive Coding

technical talks

publications and talks

economics
This was my attempt to do econ the way a mathematician might do it:
A Theory of Market Efficiency
[arxiv 2017], Slides, [Code for Demo]
computation, communication, combinatorics
Sunflowers: from soil to oil (survey article)
[2022]
On List-Decoding Transitive Codes from Random Errors
with Oscar Sprumont.
[Manuscript 2022]
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.