# Extractors for Small Zero-Fixing Sources

Ontology type: schema:ScholarlyArticle      Open Access: True

### Article Info

DATE

2022-03-14

AUTHORS ABSTRACT

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}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\psi :\left({\matrix{{[n]} \cr k \cr}} \right) \to \left\{{- 1,1} \right\}$$\end{document} such that for every V ⊆ [n], |V| = 2k, we have |∑X⊆V,|X|=kψ(X)|≤βk(2kk)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left| {\sum\nolimits_{X \subseteq V,\left| X \right| = k} {\psi (X)}} \right| \le {\beta ^k}\left({\matrix{{2k} \cr k \cr}} \right)$$\end{document} (Corollary 3.1 is more general — the number of colors may be more than 2). More... »

PAGES

1-30

### References to SciGraph publications

• 1965-03. Partition relations for cardinal numbers in ACTA MATHEMATICA HUNGARICA
• 1986. How to Reduce your Enemy’s Information (extended abstract) in ADVANCES IN CRYPTOLOGY — CRYPTO ’85 PROCEEDINGS
• 2015-06-20. Zero-Fixing Extractors for Sub-Logarithmic Entropy in AUTOMATA, LANGUAGES, AND PROGRAMMING
• ### Journal

TITLE

Combinatorica

ISSUE

N/A

VOLUME

N/A

### Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/s00493-020-4626-7

DOI

http://dx.doi.org/10.1007/s00493-020-4626-7

DIMENSIONS

https://app.dimensions.ai/details/publication/pub.1146254929

Indexing Status Check whether this publication has been indexed by Scopus and Web Of Science using the SN Indexing Status Tool
Incoming Citations Browse incoming citations for this publication using opencitations.net

JSON-LD is the canonical representation for SciGraph data.

TIP: You can open this SciGraph record using an external JSON-LD service:

[
{
"@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json",
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/01",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Mathematical Sciences",
"type": "DefinedTerm"
},
{
"id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0101",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Pure Mathematics",
"type": "DefinedTerm"
}
],
"author": [
{
"affiliation": {
"alternateName": "Institute of Mathematics, Czech Academy of Sciences, 11567, Prague, Czech Republic",
"id": "http://www.grid.ac/institutes/grid.425493.d",
"name": [
"Institute of Mathematics, Czech Academy of Sciences, 11567, Prague, Czech Republic"
],
"type": "Organization"
},
"familyName": "Pudl\u00e1k",
"givenName": "Pavel",
"id": "sg:person.076030521.23",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.076030521.23"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Department of Mathematics, Emory University, 30322, Atlanta, GA, USA",
"id": "http://www.grid.ac/institutes/grid.189967.8",
"name": [
"Department of Mathematics, Emory University, 30322, Atlanta, GA, USA"
],
"type": "Organization"
},
"familyName": "R\u00f6dl",
"givenName": "Vojt\u0115ch",
"id": "sg:person.014524603716.37",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014524603716.37"
],
"type": "Person"
}
],
"citation": [
{
"id": "sg:pub.10.1007/3-540-39799-x_37",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1032828359",
"https://doi.org/10.1007/3-540-39799-x_37"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/978-3-662-47672-7_28",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1012464194",
"https://doi.org/10.1007/978-3-662-47672-7_28"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01886396",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1037431161",
"https://doi.org/10.1007/bf01886396"
],
"type": "CreativeWork"
}
],
"datePublished": "2022-03-14",
"datePublishedReg": "2022-03-14",
"description": "Let V \u2286 [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 \u03f5-extractor for (n, k)-zero-fixing sources is a mapping F: {0, 1}n \u2192 {0, 1}m, for some m, such that F(X) is \u03f5-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 \u03bc > 0, an efficiently computable extractor that extracts a positive fraction of entropy, i.e., \u03a9(k) bits, from (n, k)-zero-fixing sources where k \u2265 (log log n)2+\u03bc.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 \u2265 C log log log n, for some constant C. The second extractor extracts a positive fraction of entropy for k \u2265 log(i)n for any fixed i \u2208 \u2115, 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 \u2264 \u03b1 log log n/log log log n, where \u03b1 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 \u2208 \u2115 there exists \u03b2 < 1 such that for every k and n, n \u2264 expl (k), there exists a 2-coloring of k-tuples of elements of [n], \u03c8:([n]k)\u2192{\u22121,1}\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\psi :\\left({\\matrix{{[n]} \\cr k \\cr}} \\right) \\to \\left\\{{- 1,1} \\right\\}$$\\end{document} such that for every V \u2286 [n], |V| = 2k, we have |\u2211X\u2286V,|X|=k\u03c8(X)|\u2264\u03b2k(2kk)\\documentclass[12pt]{minimal}\n\t\t\t\t\\usepackage{amsmath}\n\t\t\t\t\\usepackage{wasysym}\n\t\t\t\t\\usepackage{amsfonts}\n\t\t\t\t\\usepackage{amssymb}\n\t\t\t\t\\usepackage{amsbsy}\n\t\t\t\t\\usepackage{mathrsfs}\n\t\t\t\t\\usepackage{upgreek}\n\t\t\t\t\\setlength{\\oddsidemargin}{-69pt}\n\t\t\t\t\\begin{document}$$\\left| {\\sum\\nolimits_{X \\subseteq V,\\left| X \\right| = k} {\\psi (X)}} \\right| \\le {\\beta ^k}\\left({\\matrix{{2k} \\cr k \\cr}} \\right)$$\\end{document} (Corollary 3.1 is more general \u2014 the number of colors may be more than 2).",
"genre": "article",
"id": "sg:pub.10.1007/s00493-020-4626-7",
"isAccessibleForFree": true,
"isPartOf": [
{
"id": "sg:journal.1136493",
"issn": [
"0209-9683",
"1439-6912"
],
"name": "Combinatorica",
"publisher": "Springer Nature",
"type": "Periodical"
}
],
"keywords": [
"Ramsey theory",
"subset of size",
"log log n",
"polynomial time",
"Ramsey-type property",
"log n",
"statistical distance",
"\u03f5-close",
"Theorem 5.1",
"lower bounds",
"bit-fixing sources",
"Corollary 3.1",
"positive constant",
"mapping f",
"log log n.",
"log n.",
"entropy decrease",
"k-tuples",
"entropy",
"log log",
"k-element subsets",
"uniform distribution",
"zeros",
"positive fraction",
"second extractor",
"I time",
"theory",
"second one",
"bounds",
"different constructions",
"small zeros",
"Shinkar",
"coloring",
"distribution",
"main difference",
"string",
"problem",
"logarithm",
"subset",
"n.",
"properties",
"constants",
"size",
"function",
"results",
"connection",
"one",
"distance",
"Cohen",
"construction",
"time",
"source",
"bits",
"extractor",
"elements",
"fraction",
"logs",
"differences",
"decrease",
"paper",
"EXPL"
],
"name": "Extractors for Small Zero-Fixing Sources",
"pagination": "1-30",
"productId": [
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1146254929"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/s00493-020-4626-7"
]
}
],
"sameAs": [
"https://doi.org/10.1007/s00493-020-4626-7",
"https://app.dimensions.ai/details/publication/pub.1146254929"
],
"sdDataset": "articles",
"sdDatePublished": "2022-09-02T16:07",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-springernature-scigraph/baseset/20220902/entities/gbq_results/article/article_925.jsonl",
"type": "ScholarlyArticle",
"url": "https://doi.org/10.1007/s00493-020-4626-7"
}
]

HOW TO GET THIS DATA PROGRAMMATICALLY:

JSON-LD is a popular format for linked data which is fully compatible with JSON.

curl -H 'Accept: application/ld+json' 'https://scigraph.springernature.com/pub.10.1007/s00493-020-4626-7'

N-Triples is a line-based linked data format ideal for batch operations.

curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/pub.10.1007/s00493-020-4626-7'

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00493-020-4626-7'

RDF/XML is a standard XML format for linked data.

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00493-020-4626-7'

This table displays all metadata directly associated to this object as RDF triples.

134 TRIPLES      21 PREDICATES      86 URIs      75 LITERALS      4 BLANK NODES

Subject Predicate Object
2 anzsrc-for:0101
3 schema:author Nb6298f009555410cbf4b5c66ae0ffd37
4 schema:citation sg:pub.10.1007/3-540-39799-x_37
5 sg:pub.10.1007/978-3-662-47672-7_28
6 sg:pub.10.1007/bf01886396
7 schema:datePublished 2022-03-14
8 schema:datePublishedReg 2022-03-14
9 schema: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}\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\psi :\left({\matrix{{[n]} \cr k \cr}} \right) \to \left\{{- 1,1} \right\}$$\end{document} such that for every V ⊆ [n], |V| = 2k, we have |∑X⊆V,|X|=kψ(X)|≤βk(2kk)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\left| {\sum\nolimits_{X \subseteq V,\left| X \right| = k} {\psi (X)}} \right| \le {\beta ^k}\left({\matrix{{2k} \cr k \cr}} \right)$$\end{document} (Corollary 3.1 is more general — the number of colors may be more than 2).
10 schema:genre article
11 schema:isAccessibleForFree true
12 schema:isPartOf sg:journal.1136493
13 schema:keywords Cohen
14 Corollary 3.1
15 EXPL
16 I time
17 Ramsey theory
18 Ramsey-type property
19 Shinkar
20 Theorem 5.1
21 bit-fixing sources
22 bits
23 bounds
24 coloring
25 connection
26 constants
27 construction
28 decrease
29 differences
30 different constructions
31 distance
32 distribution
33 elements
34 entropy
35 entropy decrease
36 extractor
37 fraction
38 function
39 k-element subsets
40 k-tuples
41 log log
42 log log n
43 log log n.
44 log n
45 log n.
46 logarithm
47 logs
48 lower bounds
49 main difference
50 mapping f
51 n.
52 one
53 paper
54 polynomial time
55 positive constant
56 positive fraction
57 problem
58 properties
59 results
60 second extractor
61 second one
62 size
63 small zeros
64 source
65 statistical distance
66 string
67 subset
68 subset of size
69 theory
70 time
71 uniform distribution
72 zeros
73 ϵ-close
74 schema:name Extractors for Small Zero-Fixing Sources
75 schema:pagination 1-30
76 schema:productId Nb29e76b2f50f4cacbbf1b818f5fed780
77 Nf7c0434db5ff4648a40d047bcd97b712
78 schema:sameAs https://app.dimensions.ai/details/publication/pub.1146254929
79 https://doi.org/10.1007/s00493-020-4626-7
80 schema:sdDatePublished 2022-09-02T16:07
82 schema:sdPublisher Nc641a6cfe5854e25b5e21c5a09f0d70a
83 schema:url https://doi.org/10.1007/s00493-020-4626-7
85 sgo:sdDataset articles
86 rdf:type schema:ScholarlyArticle
87 N1d93954eaa6945b595a6179597cf92c4 rdf:first sg:person.014524603716.37
88 rdf:rest rdf:nil
89 Nb29e76b2f50f4cacbbf1b818f5fed780 schema:name doi
90 schema:value 10.1007/s00493-020-4626-7
91 rdf:type schema:PropertyValue
92 Nb6298f009555410cbf4b5c66ae0ffd37 rdf:first sg:person.076030521.23
93 rdf:rest N1d93954eaa6945b595a6179597cf92c4
94 Nc641a6cfe5854e25b5e21c5a09f0d70a schema:name Springer Nature - SN SciGraph project
95 rdf:type schema:Organization
96 Nf7c0434db5ff4648a40d047bcd97b712 schema:name dimensions_id
97 schema:value pub.1146254929
98 rdf:type schema:PropertyValue
99 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
100 schema:name Mathematical Sciences
101 rdf:type schema:DefinedTerm
102 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
103 schema:name Pure Mathematics
104 rdf:type schema:DefinedTerm
105 sg:journal.1136493 schema:issn 0209-9683
106 1439-6912
107 schema:name Combinatorica
108 schema:publisher Springer Nature
109 rdf:type schema:Periodical
110 sg:person.014524603716.37 schema:affiliation grid-institutes:grid.189967.8
111 schema:familyName Rödl
112 schema:givenName Vojtĕch
113 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014524603716.37
114 rdf:type schema:Person
115 sg:person.076030521.23 schema:affiliation grid-institutes:grid.425493.d
116 schema:familyName Pudlák
117 schema:givenName Pavel
118 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.076030521.23
119 rdf:type schema:Person
120 sg:pub.10.1007/3-540-39799-x_37 schema:sameAs https://app.dimensions.ai/details/publication/pub.1032828359
121 https://doi.org/10.1007/3-540-39799-x_37
122 rdf:type schema:CreativeWork
123 sg:pub.10.1007/978-3-662-47672-7_28 schema:sameAs https://app.dimensions.ai/details/publication/pub.1012464194
124 https://doi.org/10.1007/978-3-662-47672-7_28
125 rdf:type schema:CreativeWork
126 sg:pub.10.1007/bf01886396 schema:sameAs https://app.dimensions.ai/details/publication/pub.1037431161
127 https://doi.org/10.1007/bf01886396
128 rdf:type schema:CreativeWork
129 grid-institutes:grid.189967.8 schema:alternateName Department of Mathematics, Emory University, 30322, Atlanta, GA, USA
130 schema:name Department of Mathematics, Emory University, 30322, Atlanta, GA, USA
131 rdf:type schema:Organization
132 grid-institutes:grid.425493.d schema:alternateName Institute of Mathematics, Czech Academy of Sciences, 11567, Prague, Czech Republic
133 schema:name Institute of Mathematics, Czech Academy of Sciences, 11567, Prague, Czech Republic
134 rdf:type schema:Organization