7 citations · 17 across the 8 of their papers we have counts for
7 papers · 1 filter
A Strong XOR Lemma for Randomized Query Complexity
Joshua Brody, Jae Tak Kim, Peem Lerdputtipongporn +1
We give a strong direct sum theorem for computing . Specifically, we show that for every function g and every , the randomized query complexity of computing t…
Optimal Separation and Strong Direct Sum for Randomized Query Complexity
Eric Blais, Joshua Brody
We establish two results regarding the query complexity of bounded-error randomized algorithms. * Bounded-error separation theorem. There exists a total function $f : \{0,1\}^n \to…
Dependent Random Graphs and Multiparty Pointer Jumping
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 grap…
Distance-Sensitive Property Testing Lower Bounds
Joshua Brody, Pooya Hatami
In this paper, we consider several property testing problems and ask how the query complexity depends on the distance parameter $\eps$. We achieve new lower bounds in this setting…
Better Gap-Hamming Lower Bounds via Better Round Elimination
Joshua Brody, Amit Chakrabarti, Oded Regev +2
Gap Hamming Distance is a well-studied problem in communication complexity, in which Alice and Bob have to decide whether the Hamming distance between their respective n-bit inputs…
A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences
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 de…