Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > JOSHUA BRODY:
All reports by Author Joshua Brody:

TR17-050 | 15th March 2017
Joe Boninger, Joshua Brody, Owen Kephart

Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search

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 >>>


TR15-091 | 3rd June 2015
Joshua Brody, Mario Sanchez

Dependent Random Graphs and Multiparty Pointer Jumping

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 >>>


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

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 >>>


TR12-153 | 9th November 2012
Joshua Brody, Amit Chakrabarti, Ranganath Kondapally

Certifying Equality With Limited Interaction

Revisions: 1

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 >>>


TR11-045 | 1st April 2011
Eric Blais, Joshua Brody, Kevin Matulef

Property Testing Lower Bounds via Communication Complexity

Revisions: 1

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 >>>


TR09-017 | 20th February 2009
Joshua Brody

The Maximum Communication Complexity of Multi-party Pointer Jumping.

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 >>>


TR09-015 | 19th February 2009
Joshua Brody, Amit Chakrabarti

A Multi-Round Communication Lower Bound for Gap Hamming and Some Consequences

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 >>>




ISSN 1433-8092 | Imprint