Research Summary

My main research area is theoretical computer science. I am particularly interested in Communication Complexity, and in how communication complexity lower bounds imply lower bounds in all sorts of areas of computer science, including streaming algorithms, data structures, and property testing. My Erdős number is 2.

Prospective Students

Are you interested in theoretical or algorithmic topics in computer science? Do you think math is fun? Are you interested in research? Please come by my office.


Publications


(Swarthmore students highlighted in red)

Manuscripts

  • Graph Containment Properties in Dependent Random Graphs
    (with Mario Sanchez '16), 2016.

  • Distance-Sensitive Property Testing Lower Bounds.
    (with Pooya Hatami), 2014.

Journal Publications

Conference Publications


Collaborators


I have been fortunate to collaborate with the following researchers: Chrisil Arackaparambil Eric Blais Sergey Bratus Harry Buhrman Amit Chakrabarti Shiteng Chen Sune Jakobsen Ranganath Kondapally Michal Koucký David Kotz Kasper Green Larsen Hongyu Liang Bruno Loff Kevin Matulef Periklis Papakonstantinou Oded Regev Anna Shubina Hao Song Florian Speelman Xiaoming Sun Elad Verbin Nikolay Vereshchagin Thomas Vidick Peter Winkler Ronald de Wolf David Woodruff Chenggang Wu Grigory Yaroslavtsev