All reports by Author Joshua Brody:

__
TR20-124
| 3rd August 2020
__

Joshua Brody, JaeTak Kim, Peem Lerdputtipongporn, Hariharan Srinivasulu#### A Strong XOR Lemma for Randomized Query Complexity

__
TR17-050
| 15th March 2017
__

Joe Boninger, Joshua Brody, Owen Kephart#### Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search

__
TR15-091
| 3rd June 2015
__

Joshua Brody, Mario Sanchez#### Dependent Random Graphs and Multiparty Pointer Jumping

__
TR12-179
| 13th December 2012
__

Joshua Brody, Harry Buhrman, Michal Koucky, Bruno Loff, Florian Speelman#### Towards a Reverse Newman's Theorem in Interactive Information Complexity

Revisions: 2

__
TR12-153
| 9th November 2012
__

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally#### Certifying Equality With Limited Interaction

Revisions: 1

__
TR11-045
| 1st April 2011
__

Eric Blais, Joshua Brody, Kevin Matulef#### Property Testing Lower Bounds via Communication Complexity

Revisions: 1

__
TR09-017
| 20th February 2009
__

Joshua Brody#### The Maximum Communication Complexity of Multi-party Pointer Jumping.

__
TR09-015
| 19th February 2009
__

Joshua Brody, Amit Chakrabarti#### A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences

Joshua Brody, JaeTak Kim, Peem Lerdputtipongporn, Hariharan Srinivasulu

We give a strong direct sum theorem for computing $XOR \circ g$. Specifically, we show that the randomized query complexity of computing the XOR of $k$ instances of $g$ satisfies $\bar{R}_\varepsilon(XOR \circ g)=\Theta(\bar{R}_{\varepsilon/k}(g))$. This matches the naive success amplification bound and answers a question of Blais and Brody.

As a ... more >>>

Joe Boninger, Joshua Brody, Owen Kephart

In this work, we continue the examination of the role non-adaptivity} plays in maintaining dynamic data structures, initiated by Brody and Larsen [BL15].. We consider nonadaptive data structures for predecessor search in the w-bit cell probe model. Predecessor search is one of the most well-studied data structure problems. For this ... more >>>

Joshua Brody, Mario Sanchez

We initiate a study of a relaxed version of the standard Erdos-Renyi random graph model, where each edge may depend on a few other edges. We call such graphs dependent random graphs. Our main result in this direction is a thorough understanding of the clique number of dependent random graphs. ... more >>>

Joshua Brody, Harry Buhrman, Michal Koucky, Bruno Loff, Florian Speelman

Newmanâ€™s theorem states that we can take any public-coin communication protocol and convert it into one that uses only private randomness with only a little increase in communication complexity. We consider a reversed scenario in the context of information complexity: can we take a protocol that uses private randomness and ... more >>>

Joshua Brody, Amit Chakrabarti, Ranganath Kondapally

The \textsc{equality} problem is usually one's first encounter with

communication complexity and is one of the most fundamental problems in the

field. Although its deterministic and randomized communication complexity

were settled decades ago, we find several new things to say about the

problem by focusing on two subtle aspects. The ...
more >>>

Eric Blais, Joshua Brody, Kevin Matulef

We develop a new technique for proving lower bounds in property testing, by showing a strong connection between testing and communication complexity. We give a simple scheme for reducing communication problems to testing problems, thus allowing us to use known lower bounds in communication complexity to prove lower bounds in ... more >>>

Joshua Brody

We study the one-way number-on-the-forhead (NOF) communication

complexity of the k-layer pointer jumping problem. Strong lower

bounds for this problem would have important implications in circuit

complexity. All of our results apply to myopic protocols (where

players see only one layer ahead, but can still ...
more >>>

Joshua Brody, Amit Chakrabarti

The Gap-Hamming-Distance problem arose in the context of proving space

lower bounds for a number of key problems in the data stream model. In

this problem, Alice and Bob have to decide whether the Hamming distance

between their $n$-bit input strings is large (i.e., at least $n/2 +

\sqrt n$) ...
more >>>