Extractors for Small Zero-Fixing Sources View Full Text


Ontology type: schema:ScholarlyArticle      Open Access: True


Article Info

DATE

2022-03-14

AUTHORS

Pavel Pudlák, Vojtĕch Rödl

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
  • 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: JSON-LD Playground Google SDTT

    [
      {
        "@context": "https://springernature.github.io/scigraph/jsonld/sgcontext.json", 
        "about": [
          {
            "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", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "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"
      }
    ]
     

    Download the RDF metadata as:  json-ld nt turtle xml License info

    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'

    Turtle is a human-readable linked data format.

    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
    1 sg:pub.10.1007/s00493-020-4626-7 schema:about anzsrc-for:01
    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
    81 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    82 schema:sdPublisher Nc641a6cfe5854e25b5e21c5a09f0d70a
    83 schema:url https://doi.org/10.1007/s00493-020-4626-7
    84 sgo:license sg:explorer/license/
    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
     




    Preview window. Press ESC to close (or click here)


    ...