Joshua Brody

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)

Journal Publications

A Strong XOR Lemma for Randomized Query Complexity
(with Jae Tak Kim, Peem Lerdputtipongporn, Hariharan Srinivasulu),
Theory of Computing 2023.
pdf
Certifying Equality With Limited Interaction
(with Amit Chakrabart, Ranganath Kondapally, David P. Woodruff, and Grigory Yaroslavtsev)
pdf
Algorithmica 2016, pp 1-60.
Invited article for the Special Issue on Information Complexity and Applications.
This article merges results from conference papers "Certifying Equality with Limited Interaction" and "Beyond Set Disjointness: The Communication Complexity of Finding the Intersection", listed below.
Towards a Revese Newman's Theorem in Interactive Information Complexity
(with Harry Buhrman, Michal Koucky, Bruno Loff, Florian Speelman, and Nikolay Vereshchagin)
Algorithmica 2016, pp 1-33.
Invited article for the Special Issue on Information Complexity and Applications. (see CCC13 paper below)
Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures
(with Kasper Green Larsen)
Theory of Computing, volume 11, number 19, pp 471-489.
pdf
Property Testing Lower Bounds via Communication Complexity
(with Eric Blais and Kevin Matulef)
pdf
Computational Complexity volume 21, number 2.
Special Issue devoted to select papers from CCC 2011 (see below)
Some slides from a survey talk I've given a couple of times on this technique.

Note: Oded Goldreich recently reformulated our technique. His notation is general and hopefully easier to use than our notation.

Conference Publications

Optimal Separation and Strong Direct Sum for Randomized Query Complexity
(with Eric Blais)
CCC 2019.
pdf
Non-Adaptive Data Structures for Predecessor Search
(with Joseph Boninger '16 and Owen Kephart '18)
FSTTCS 2017.
pdf
Position-Based Cryptography and Multiparty Communication
(with Stefan Dziembowski, Krzysztof Pietrzak, and Sebastian Faust)
TCC 2017.
pdf
Dependent Random Graphs and Multi-Party Pointer Jumping
(with Mario Sanchez '16)
pdf
RANDOM 2015
Certifying Equality with Limited Interaction
(with Amit Chakrabarti, Ranganath Kondapally, David Woodruff, and Grigory Yaroslavtsev)
pdf
RANDOM 2014
The Information Complexity of Hamming Distance
(with Eric Blais and Badih Ghazi)
pdf
RANDOM 2014
Beyond Set Disjointness: The Communication Complexity of Finding the Intersection
(with Amit Chakrabarti, Ranganath Kondapally, David Woodruff, and Grigory Yaroslavtsev)
pdf
PODC 2014
Cryptogenography
(with Sune K. Jakobsen, Dominik Scheder, and Peter Winkler)
pdf
ITCS 2014
Towards a Reverse Newman's Theorem in Interactive Information Complexity
(with Harry Buhrman, Michal Koucký, Bruno Loff, Florian Speelman, and Nikolay Vereshchagin)
pdf
CCC 2013
Space-Bounded Communication Complexity
(with Shiteng Chen, Periklis A. Papakonstantinou, Hao Song, and Xiaoming Sun)
pdf
ITCS 2013
Space Efficient Approximation Scheme for Circular Earth Mover Distance
(with Hongyu Liang and Xiaoming Sun)
pdf
LATIN 2012
Streaming Algorithms with One-Sided Estimation
(with David Woodruff)
pdf
RANDOM 2011
Lower Bounds for Testing Computability by Small Width OBDDs
(with Kevin Matulef and Chenggang Wu)
pdf
TAMC 2011
Property Testing Lower Bounds via Communication Complexity
(with Eric Blais and Kevin Matulef)
pdf
CCC 2011
The Coin Problem, and Pseudorandomness for Branching Programs
(with Elad Verbin)
pdf, full
FOCS 2010
Better Gap-Hamming Lower Bounds via Better Round Elimination
(with Amit Chakrabarti, Oded Regev, Thomas Vidick, and Ronald de Wolf)
pdf
RANDOM 2010
Distributed Monitoring of Conditional Entropy for Anomaly Detection in Streams
(with Chrisil Arackaparambil, Sergey Bratus, and Anna Shubina)
pdf
IPDPSW 2010
A Multi-Round Communication Lower bound for Gap Hamming and Some Consequences
(with Amit Chakrabarti)
pdf slides
CCC 2009
The Maximum Communication Complexity of Multiparty Pointer Jumping
pdf slides
CCC 2009
Functional Monitoring Without Monotonicity
(with Chrisil Arackaparambil and Amit Chakrabarti)
pdf
Preliminary version available as Dartmouth College Technical Report TR2008-639
ICALP 2009
Information-Theoretic Metrics for Anomaly Detection (Extended Abstract)
(with Sergey Bratus, David Kotz, and Anna Shubina)
extended abstract poster
RAID 2008
Sublinear Communication Protocols for Multi-Party Pointer Jumping and a Related Lower Bound
(with Amit Chakrabarti)
pdf slides
STACS 2008

Manuscripts

Graph Containment Properties in Dependent Random Graphs
(with Mario Sanchez '16), 2016.
Distance-Sensitive Property Testing Lower Bounds.
(with Pooya Hatami), 2014.

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