7 citations · 17 across the 8 of their papers we have counts for
9 papers
Evolution of locally dependent random graphs
Joshua Brody, Pat Devlin, Aditi Dudeja +1
In this paper we study -dependent random graphs -- introduced by Brody and Sanchez -- which are the family of random graph distributions where each edge is present with probabil…
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…
Adapt or Die: Polynomial Lower Bounds for Non-Adaptive Dynamic Data Structures
Joshua Brody, Kasper Green Larsen
In this paper, we study the role non-adaptivity plays in maintaining dynamic data structures. Roughly speaking, a data structure is non-adaptive if the memory locations it reads an…