Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Santha-Vazirani Sources:
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 >>>

TR17-136 | 10th September 2017
Salman Beigi, Andrej Bogdanov, Omid Etesami, Siyao Guo

Complete Classi fication of Generalized Santha-Vazirani Sources

Let $\mathcal{F}$ be a finite alphabet and $\mathcal{D}$ be a finite set of distributions over $\mathcal{F}$. A Generalized Santha-Vazirani (GSV) source of type $(\mathcal{F}, \mathcal{D})$, introduced by Beigi, Etesami and Gohari (ICALP 2015, SICOMP 2017), is a random sequence $(F_1, \dots, F_n)$ in $\mathcal{F}^n$, where $F_i$ is a sample from ... more >>>

TR22-103 | 15th July 2022
Dean Doron, Dana Moshkovitz, Justin Oh, David Zuckerman

Almost Chor--Goldreich Sources and Adversarial Random Walks

A Chor--Goldreich (CG) source [CG88] is a sequence of random variables $X = X_1 \circ \ldots \circ X_t$, each $X_i \sim \{0,1 \{^d$, such that each $X_i$ has $\delta d$ min-entropy for some constant $\delta > 0$, even conditioned on any fixing of $X_1 \circ \ldots \circ X_{i-1}$. We typically ... more >>>

ISSN 1433-8092 | Imprint