Abstract
The notion of semi-random sources, also known as Santha-Vazirani (SV) sources, stands for a sequence of n bits, where the dependence of the i’th bit on the previousi − 1 bits is limited for every i ∈ [n]. If the dependence of the i’th bit on the remainingn − 1 bits is limited, then this is a strongSV-source. Even the strong SV -sources are known not to admit (universal) deterministic extractors, but they have seeded extractors, as their min-entropy is Ω n. It is intuitively obvious that strong SV -sources are more than just high-min-entropy sources, and this work explores the intuition. Deterministic condensers are known not to exist for general high-min-entropy sources, and we construct for any constants ε, δ ∈ (0,1) a deterministic condenser that maps n bits coming from a strong SV -source with bias at most δ to Ω n bits of min-entropy rate at least 1 − ε. In conclusion we observe that deterministic condensers are closely related to very strong extractors – a proposed strengthening of the notion of strong (seeded) extractors: in particular, our constructions can be viewed as very strong extractors for the family of strong Santha-Vazirani distributions. The notion of very strong extractors requires that the output remains unpredictable even to someone who knows not only the seed value (as in the case of strong extractors), but also the extractor’s outputs corresponding to the same input value with each of the preceding seed values (say, under the lexicographic ordering). Very strong extractors closely resemble the original notion of SV -sources, except that the bits must satisfy the unpredictability requirement only on average.
Similar content being viewed by others
Notes
Throughout the work we will assume, unless stated otherwise, δ ∈Ω(1) in the context of SV-sources.
The reverse transformation is almost possible: the resulting mapping can only guarantee high entropy rate of the output (see Section 5).
References
Hamming, R.W.: Error detecting and error correcting codes. Bell Syst. Techn. J. 29, 147–160 (1950)
MacWilliams, F.J., Sloane, N.J.A.: The theory of Error-Correcting codes. Elsevier-North-Holland (1977)
Pinsker, M.S.: The information stability of Gaussian random variables and processes. Dokl. Akad. Nauk SSSR 133(1), 28–30 (1960)
Reingold, O., Vadhan, S., Wigderson, A.: A note on extracting randomness from Santha-Vazirani sources. Unpublished (2004)
Santha, M., Vazirani, U.V.: Generating Quasi-Random sequences from Slightly-Random sources. J. Comput. Syst. Sci. 33(1), 75–87 (1986)
Acknowledgments
We are grateful to anonymous reviewers for a number of very useful suggestions.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Partially funded by the grant 19-27871X of GA ČR.
Part of this work was done while visiting the Centre for Quantum Technologies at the National University of Singapore, and was partially supported by the Singapore National Research Foundation, the Prime Minister’s Office and the Ministry of Education under the Research Centres of Excellence programme under grant R710-000-012-135.
Rights and permissions
About this article
Cite this article
Gavinsky, D., Pudlák, P. Santha-Vazirani sources, deterministic condensers and very strong extractors. Theory Comput Syst 64, 1140–1154 (2020). https://doi.org/10.1007/s00224-020-09975-8
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00224-020-09975-8