Abstract
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 showed that deterministic randomness extraction from these sources is impossible. Recently, Beigi, Etesami and Gohari (ICALP 2015) studied the generalization of SV sources for non-binary sequences and showed that unlike the binary case, deterministic randomness extraction in the generalized case is sometimes possible. Beigi, Etesami and Gohari presented a necessary condition and a sufficient condition for the possibility of deterministic randomness extraction. These two conditions coincide in ?non-degenerate? cases and completely characterize the randomness extraction problem for non-degenerate cases. In this work, we continue the study of deterministic randomness extraction from non-binary SV sources and obtain following results. 1) We completely characterize the randomness extraction problem for both non-degenerate and degenerate cases by providing a necessary and sufficient condition for the possibility of randomness extraction from SV sources. This condition reduces to the condition of Beigi, Etesami and Gohari when the SV source is non-degenerate and fills the gap in the degenerate case. 2) We further improve both the output length and the error of the extractor of Beigi, Etesami and Gohari from a single bit with inverse polynomial error to linear number of bits with exponential error. As a corollary, in the non-degenerate case, a linear number of bits can be extracted and with exponentially small error when randomness extraction is possible. 3) We show that for any extractable SV source one can always extract a random bit with inverse polynomial error. And we show the error cannot be improved beyond inverse polynomial for a specific degenerate source. Joint work with Salman Beigi, Andrej Bogdanov, Omid Etesami.