Počet záznamů: 1
Santha-Vazirani sources, deterministic condensers and very strong extractors
- 1.
SYSNO ASEP 0531290 Druh ASEP J - Článek v odborném periodiku Zařazení RIV J - Článek v odborném periodiku Poddruh J Článek ve WOS Název Santha-Vazirani sources, deterministic condensers and very strong extractors Tvůrce(i) Gavinsky, Dmitry (MU-W) RID, SAI, ORCID
Pudlák, Pavel (MU-W) RID, SAIZdroj.dok. Theory of Computing Systems. - : Springer - ISSN 1432-4350
Roč. 64, č. 6 (2020), s. 1140-1154Poč.str. 15 s. Jazyk dok. eng - angličtina Země vyd. US - Spojené státy americké Klíč. slova deterministic condensers ; extractors ; randomness ; Santha-Vazirani sources Vědní obor RIV IN - Informatika Obor OECD Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8) CEP GX19-27871X GA ČR - Grantová agentura ČR Způsob publikování Omezený přístup Institucionální podpora MU-W - RVO:67985840 UT WOS 000528283000001 EID SCOPUS 85084149923 DOI 10.1007/s00224-020-09975-8 Anotace 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. Pracoviště Matematický ústav Kontakt Jarmila Štruncová, struncova@math.cas.cz, library@math.cas.cz, Tel.: 222 090 757 Rok sběru 2021 Elektronická adresa https://doi.org/10.1007/s00224-020-09975-8
Počet záznamů: 1