|
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
|
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.
|
