Extractors for small zero-fixing sources

Result code in 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>

Result on the web

<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>

Result language

angličtina

Original language name

Extractors for small zero-fixing sources

Original language description

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).

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

10101 - Pure mathematics

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

2022

Confidentiality

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

Name of the periodical

Combinatorica

ISSN

0209-9683

e-ISSN

1439-6912

Volume of the periodical

42

Issue of the periodical within the volume

4

Country of publishing house

HU - HUNGARY

Number of pages

30

Pages from-to

587-616

UT code for WoS article

000780265300007

EID of the result in the Scopus database

2-s2.0-85126236132