Santha-Vazirani sources, deterministic condensers and very strong extractors

Result code in IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F20%3A00531290" target="_blank" >RIV/67985840:_____/20:00531290 - isvavai.cz</a>

Result on the web

<a href="https://doi.org/10.1007/s00224-020-09975-8" target="_blank" >https://doi.org/10.1007/s00224-020-09975-8</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00224-020-09975-8" target="_blank" >10.1007/s00224-020-09975-8</a>

Result language

angličtina

Original language name

Santha-Vazirani sources, deterministic condensers and very strong extractors

Original language description

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.

Czech name

—

Czech description

—

Type

J_imp - Article in a specialist periodical, which is included in the Web of Science database

CEP classification

—

OECD FORD branch

10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Project

<a href="/en/project/GX19-27871X" target="_blank" >GX19-27871X: Efficient approximation algorithms and circuit complexity</a><br>

Continuities

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Publication year

2020

Confidentiality

S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Name of the periodical

Theory of Computing Systems

ISSN

1432-4350

e-ISSN

—

Volume of the periodical

64

Issue of the periodical within the volume

6

Country of publishing house

US - UNITED STATES

Number of pages

15

Pages from-to

1140-1154

UT code for WoS article

000528283000001

EID of the result in the Scopus database

2-s2.0-85084149923