All reports by Author Ziv Bar-Yossef:

__
TR04-036
| 27th March 2004
__

Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis#### Exponential Separation of Quantum and Classical One-Way Communication Complexity

__
TR03-037
| 30th April 2003
__

Ziv Bar-Yossef#### Sampling Lower Bounds via Information Theory

__
TR98-072
| 14th December 1998
__

Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson#### Deterministic Amplification of Space Bounded Probabilistic Algorithms.

__
TR97-008
| 16th March 1997
__

Noam Nisan, Ziv Bar-Yossef#### Pointer Jumping Requires Concurrent Read

Ziv Bar-Yossef, T.S. Jayram, Iordanis Kerenidis

We give the first exponential separation between quantum and bounded-error randomized one-way communication complexity. Specifically, we define the Hidden Matching Problem HM_n: Alice gets as input a string x in {0,1}^n and Bob gets a perfect matching M on the n coordinates. Bob's goal is to output a tuple (i,j,b) ... more >>>

Ziv Bar-Yossef

We present a novel technique, based on the Jensen-Shannon divergence

from information theory, to prove lower bounds on the query complexity

of sampling algorithms that approximate functions over arbitrary

domain and range. Unlike previous methods, our technique does not

use a reduction from a binary decision problem, but rather ...
more >>>

Ziv Bar-Yossef, Oded Goldreich, Avi Wigderson

This paper initiates the study of deterministic amplification of space

bounded probabilistic algorithms. The straightforward implementations of

known amplification methods cannot be used for such algorithms, since they

consume too much space. We present a new implementation of the

Ajtai-Koml\'{o}s-Szemer\'{e}di method, that enables to amplify an $S$ ...
more >>>

Noam Nisan, Ziv Bar-Yossef

We consider the well known problem of determining the k'th

vertex reached by chasing pointers in a directed graph of

out-degree 1. The famous "pointer doubling" technique

provides an O(log k) parallel time algorithm on a

Concurrent-Read Exclusive-Write (CREW) PRAM. We prove that ...
more >>>