Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > KEYWORD > COMMON RANDOMNESS:
Reports tagged with Common Randomness:
TR14-179 | 20th December 2014
Salman Beigi, Omid Etesami, Amin Gohari

#### Deterministic Randomness Extraction from Generalized and Distributed Santha-Vazirani Sources

A Santha-Vazirani (SV) source is a sequence of random bits where the conditional distribution of each bit, given the previous bits, can be partially controlled by an adversary. Santha and Vazirani show that deterministic randomness extraction from these sources is impossible.
In this paper, we study the generalization of SV ... more >>>

TR16-033 | 10th March 2016

#### Tight bounds for communication assisted agreement distillation

Suppose Alice holds a uniformly random string $X \in \{0,1\}^N$ and Bob holds a noisy version $Y$ of $X$ where each bit of $X$ is flipped independently with probability $\epsilon \in [0,1/2]$. Alice and Bob would like to extract a common random string of min-entropy at least $k$. In this ... more >>>

TR17-119 | 25th July 2017