Extractors for small zero-fixing sources

Kód výsledku v IS VaVaI

<a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F22%3A00561963" target="_blank" >RIV/67985840:_____/22:00561963 - isvavai.cz</a>

Výsledek na webu

<a href="https://doi.org/10.1007/s00493-020-4626-7" target="_blank" >https://doi.org/10.1007/s00493-020-4626-7</a>

DOI - Digital Object Identifier

<a href="http://dx.doi.org/10.1007/s00493-020-4626-7" target="_blank" >10.1007/s00493-020-4626-7</a>

Jazyk výsledku

angličtina

Název v původním jazyce

Extractors for small zero-fixing sources

Popis výsledku v původním jazyce

Let V ⊆ [n] be a k-element subset of [n]. The uniform distribution on the 2k strings from {0, 1}n that are set to zero outside of V is called an (n, k)-zero-fixing source. An ϵ-extractor for (n, k)-zero-fixing sources is a mapping F: {0, 1}n → {0, 1}m, for some m, such that F(X) is ϵ-close in statistical distance to the uniform distribution on {0, 1}m for every (n, k)-zero-fixing source X. Zero-fixing sources were introduced by Cohen and Shinkar in [7] in connection with the previously studied extractors for bit-fixing sources. They constructed, for every μ > 0, an efficiently computable extractor that extracts a positive fraction of entropy, i.e., Ω(k) bits, from (n, k)-zero-fixing sources where k ≥ (log log n)2+μ. In this paper we present two different constructions of extractors for zero-fixing sources that are able to extract a positive fraction of entropy for k substantially smaller than log log n. The first extractor works for k ≥ C log log log n, for some constant C. The second extractor extracts a positive fraction of entropy for k ≥ log(i)n for any fixed i ∈ ℕ, where log(i) denotes i-times iterated logarithm. The fraction of extracted entropy decreases with i. The first extractor is a function computable in polynomial time in n, the second one is computable in polynomial time in n when k ≤ α log log n/log log log n, where α is a positive constant. Our results can also be viewed as lower bounds on some Ramsey-type properties. The main difference between the problems about extractors studied here and the standard Ramsey theory is that we study colorings of all subsets of size up to k while in Ramsey theory the sizes are fixed to k. However it is easy to derive results also for coloring of subsets of sizes equal to k. In Corollary 3.1 of Theorem 5.1 we show that for every l ∈ ℕ there exists β < 1 such that for every k and n, n ≤ expl (k), there exists a 2-coloring of k-tuples of elements of [n], ψ:([n]k)→{−1,1} such that for every V ⊆ [n], |V| = 2k, we have |∑X⊆V,|X|=kψ(X)|≤βk(2kk) (Corollary 3.1 is more general — the number of colors may be more than 2).

Název v anglickém jazyce

Extractors for small zero-fixing sources

Popis výsledku anglicky

Let V ⊆ [n] be a k-element subset of [n]. The uniform distribution on the 2k strings from {0, 1}n that are set to zero outside of V is called an (n, k)-zero-fixing source. An ϵ-extractor for (n, k)-zero-fixing sources is a mapping F: {0, 1}n → {0, 1}m, for some m, such that F(X) is ϵ-close in statistical distance to the uniform distribution on {0, 1}m for every (n, k)-zero-fixing source X. Zero-fixing sources were introduced by Cohen and Shinkar in [7] in connection with the previously studied extractors for bit-fixing sources. They constructed, for every μ > 0, an efficiently computable extractor that extracts a positive fraction of entropy, i.e., Ω(k) bits, from (n, k)-zero-fixing sources where k ≥ (log log n)2+μ. In this paper we present two different constructions of extractors for zero-fixing sources that are able to extract a positive fraction of entropy for k substantially smaller than log log n. The first extractor works for k ≥ C log log log n, for some constant C. The second extractor extracts a positive fraction of entropy for k ≥ log(i)n for any fixed i ∈ ℕ, where log(i) denotes i-times iterated logarithm. The fraction of extracted entropy decreases with i. The first extractor is a function computable in polynomial time in n, the second one is computable in polynomial time in n when k ≤ α log log n/log log log n, where α is a positive constant. Our results can also be viewed as lower bounds on some Ramsey-type properties. The main difference between the problems about extractors studied here and the standard Ramsey theory is that we study colorings of all subsets of size up to k while in Ramsey theory the sizes are fixed to k. However it is easy to derive results also for coloring of subsets of sizes equal to k. In Corollary 3.1 of Theorem 5.1 we show that for every l ∈ ℕ there exists β < 1 such that for every k and n, n ≤ expl (k), there exists a 2-coloring of k-tuples of elements of [n], ψ:([n]k)→{−1,1} such that for every V ⊆ [n], |V| = 2k, we have |∑X⊆V,|X|=kψ(X)|≤βk(2kk) (Corollary 3.1 is more general — the number of colors may be more than 2).

Druh

J_imp - Článek v periodiku v databázi Web of Science

CEP obor

—

OECD FORD obor

10101 - Pure mathematics

Projekt

<a href="/cs/project/GX19-27871X" target="_blank" >GX19-27871X: Efektivní aproximační algoritmy a obvodová složitost</a><br>

Návaznosti

I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Rok uplatnění

2022

Kód důvěrnosti údajů

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

Název periodika

Combinatorica

ISSN

0209-9683

e-ISSN

1439-6912

Svazek periodika

42

Číslo periodika v rámci svazku

4

Stát vydavatele periodika

HU - Maďarsko

Počet stran výsledku

30

Strana od-do

587-616

Kód UT WoS článku

000780265300007

EID výsledku v databázi Scopus

2-s2.0-85126236132