2019/07/08 by Dmytro Gavinsky, Pavel Pudlák, Gavinsky, Dmytro +1
Computer Science · #Adversarial Robustness in Machine Learning #Computational Complexity (cs.CC) #Domain Adaptation and Few-Shot Learning #FOS: Computer and information sciences #Machine Learning and Algorithms
paper · pdf · doi:10.48550/arxiv.1907.04640
openalex publication_date 2019/07/08 · openalex created_date 2022/07/28 · openalex updated_date 2026/07/28
The notion of semi-random sources, also known as Santha-Vazirani (SV)\nsources, stands for a sequence of n bits, where the dependence of the i'th bit\non the previous i-1 bits is limited for every i\∈[n]. If the dependence of\nthe i'th bit on the remaining n-1 bits is limited, then this is a strong\nSV-source. Even the strong SV-sources are known not to admit (universal)\ndeterministic extractors, but they have seeded extractors, as their min-entropy\nis \Ω(n). It is intuitively obvious that strong SV-sources are more than\njust high-min-entropy sources, and this work explores the intuition.\nDeterministic condensers are known not to exist for general high-min-entropy\nsources, and we construct for any constants \ε, \δ \∈ (0,1) a\ndeterministic condenser that maps n bits coming from a strong SV-source with\nbias at most \δ to \Ω(n) bits of min-entropy rate at least\n1-\ε. In conclusion we observe that deterministic condensers are\nclosely related to very strong extractors - a proposed strengthening of the\nnotion of strong (seeded) extractors: in particular, our constructions can be\nviewed as very strong extractors for the family of strong Santha-Vazirani\ndistributions. The notion of very strong extractors requires that the output\nremains unpredictable even to someone who knows not only the seed value (as in\nthe case of strong extractors), but also the extractor's outputs corresponding\nto the same input value with each of the preceding seed values (say, under the\nlexicographic ordering). Very strong extractors closely resemble the original\nnotion of SV-sources, except that the bits must satisfy the unpredictability\nrequirement only on average.\n