Efficient construction of a small hitting set for combinatorial rectangles in high dimension View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

1997-06

AUTHORS

Nathan Linial, Michael Luby, Michael Saks, David Zuckerman

ABSTRACT

We describe a deterministic algorithm which, on input integersd, m and real number ∈∃ (0,1), produces a subset S of [m]d={1,2,3,...,m}d that hits every combinatorial rectangle in [m]d of volume at least ∈, i.e., every subset of [m]d the formR1×R2×...×Rd of size at least ∈md. The cardinality of S is polynomial inm(logd)/∈, and the time to construct it is polynomial inmd/∈. The construction of such sets has applications in derandomization methods based on small sample spaces for general multivalued random variables. More... »

PAGES

215-234

References to SciGraph publications

Identifiers

URI

http://scigraph.springernature.com/pub.10.1007/bf01200907

DOI

http://dx.doi.org/10.1007/bf01200907

DIMENSIONS

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


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": "Computer Science Department, Hebrew University, Jerusalem, Israel", 
          "id": "http://www.grid.ac/institutes/grid.9619.7", 
          "name": [
            "Computer Science Department, Hebrew University, Jerusalem, Israel"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Linial", 
        "givenName": "Nathan", 
        "id": "sg:person.015760032537.47", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015760032537.47"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "DEC/SRC, 130 Lytton Avenue, 94301, Palo Alto, California", 
          "id": "http://www.grid.ac/institutes/None", 
          "name": [
            "DEC/SRC, 130 Lytton Avenue, 94301, Palo Alto, California"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Luby", 
        "givenName": "Michael", 
        "id": "sg:person.012003400773.68", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012003400773.68"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Mathematics, Rutgers University, 08854, New Brunswick, NJ, USA", 
          "id": "http://www.grid.ac/institutes/grid.430387.b", 
          "name": [
            "Department of Mathematics, Rutgers University, 08854, New Brunswick, NJ, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Saks", 
        "givenName": "Michael", 
        "id": "sg:person.011520224512.05", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05"
        ], 
        "type": "Person"
      }, 
      {
        "affiliation": {
          "alternateName": "Department of Computer Sciences, The University of Texas at Austin, 78713, Austin, Texas, USA", 
          "id": "http://www.grid.ac/institutes/grid.89336.37", 
          "name": [
            "Department of Computer Sciences, The University of Texas at Austin, 78713, Austin, Texas, USA"
          ], 
          "type": "Organization"
        }, 
        "familyName": "Zuckerman", 
        "givenName": "David", 
        "id": "sg:person.01101524740.75", 
        "sameAs": [
          "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01101524740.75"
        ], 
        "type": "Person"
      }
    ], 
    "citation": [
      {
        "id": "sg:pub.10.1007/bf01271266", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1021385362", 
          "https://doi.org/10.1007/bf01271266"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01940873", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1001000053", 
          "https://doi.org/10.1007/bf01940873"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01940870", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1041202529", 
          "https://doi.org/10.1007/bf01940870"
        ], 
        "type": "CreativeWork"
      }, 
      {
        "id": "sg:pub.10.1007/bf01305237", 
        "sameAs": [
          "https://app.dimensions.ai/details/publication/pub.1019048384", 
          "https://doi.org/10.1007/bf01305237"
        ], 
        "type": "CreativeWork"
      }
    ], 
    "datePublished": "1997-06", 
    "datePublishedReg": "1997-06-01", 
    "description": "We describe a deterministic algorithm which, on input integersd, m and real number \u2208\u2203 (0,1), produces a subset S of [m]d={1,2,3,...,m}d that hits every combinatorial rectangle in [m]d of volume at least \u2208, i.e., every subset of [m]d the formR1\u00d7R2\u00d7...\u00d7Rd of size at least \u2208md. The cardinality of S is polynomial inm(logd)/\u2208, and the time to construct it is polynomial inmd/\u2208. The construction of such sets has applications in derandomization methods based on small sample spaces for general multivalued random variables.", 
    "genre": "article", 
    "id": "sg:pub.10.1007/bf01200907", 
    "isAccessibleForFree": false, 
    "isPartOf": [
      {
        "id": "sg:journal.1136493", 
        "issn": [
          "0209-9683", 
          "1439-6912"
        ], 
        "name": "Combinatorica", 
        "publisher": "Springer Nature", 
        "type": "Periodical"
      }, 
      {
        "issueNumber": "2", 
        "type": "PublicationIssue"
      }, 
      {
        "type": "PublicationVolume", 
        "volumeNumber": "17"
      }
    ], 
    "keywords": [
      "small sample space", 
      "combinatorial rectangles", 
      "random variables", 
      "derandomization method", 
      "higher dimensions", 
      "sample space", 
      "real numbers", 
      "deterministic algorithm", 
      "hitting sets", 
      "subset S", 
      "such sets", 
      "rectangle", 
      "efficient construction", 
      "set", 
      "cardinality", 
      "algorithm", 
      "space", 
      "construction", 
      "dimensions", 
      "variables", 
      "applications", 
      "number", 
      "subset", 
      "size", 
      "time", 
      "volume", 
      "method"
    ], 
    "name": "Efficient construction of a small hitting set for combinatorial rectangles in high dimension", 
    "pagination": "215-234", 
    "productId": [
      {
        "name": "dimensions_id", 
        "type": "PropertyValue", 
        "value": [
          "pub.1019819433"
        ]
      }, 
      {
        "name": "doi", 
        "type": "PropertyValue", 
        "value": [
          "10.1007/bf01200907"
        ]
      }
    ], 
    "sameAs": [
      "https://doi.org/10.1007/bf01200907", 
      "https://app.dimensions.ai/details/publication/pub.1019819433"
    ], 
    "sdDataset": "articles", 
    "sdDatePublished": "2022-09-02T15:49", 
    "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_291.jsonl", 
    "type": "ScholarlyArticle", 
    "url": "https://doi.org/10.1007/bf01200907"
  }
]
 

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/bf01200907'

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/bf01200907'

Turtle is a human-readable linked data format.

curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01200907'

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

curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01200907'


 

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

130 TRIPLES      21 PREDICATES      56 URIs      44 LITERALS      6 BLANK NODES

Subject Predicate Object
1 sg:pub.10.1007/bf01200907 schema:about anzsrc-for:01
2 anzsrc-for:0101
3 schema:author Nc6f981bde85f4d1ebf4483d1a887050c
4 schema:citation sg:pub.10.1007/bf01271266
5 sg:pub.10.1007/bf01305237
6 sg:pub.10.1007/bf01940870
7 sg:pub.10.1007/bf01940873
8 schema:datePublished 1997-06
9 schema:datePublishedReg 1997-06-01
10 schema:description We describe a deterministic algorithm which, on input integersd, m and real number ∈∃ (0,1), produces a subset S of [m]d={1,2,3,...,m}d that hits every combinatorial rectangle in [m]d of volume at least ∈, i.e., every subset of [m]d the formR1×R2×...×Rd of size at least ∈md. The cardinality of S is polynomial inm(logd)/∈, and the time to construct it is polynomial inmd/∈. The construction of such sets has applications in derandomization methods based on small sample spaces for general multivalued random variables.
11 schema:genre article
12 schema:isAccessibleForFree false
13 schema:isPartOf N0d125799225e48d1b118a72de0dbacb4
14 N2d3585bb9a714b23b4f12a3f7a6548ae
15 sg:journal.1136493
16 schema:keywords algorithm
17 applications
18 cardinality
19 combinatorial rectangles
20 construction
21 derandomization method
22 deterministic algorithm
23 dimensions
24 efficient construction
25 higher dimensions
26 hitting sets
27 method
28 number
29 random variables
30 real numbers
31 rectangle
32 sample space
33 set
34 size
35 small sample space
36 space
37 subset
38 subset S
39 such sets
40 time
41 variables
42 volume
43 schema:name Efficient construction of a small hitting set for combinatorial rectangles in high dimension
44 schema:pagination 215-234
45 schema:productId N39e4092105364c2da81e70e24bf451d0
46 N4673c3fccc8c4d1382fba0d62dcebf64
47 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019819433
48 https://doi.org/10.1007/bf01200907
49 schema:sdDatePublished 2022-09-02T15:49
50 schema:sdLicense https://scigraph.springernature.com/explorer/license/
51 schema:sdPublisher N4a7fbfe0de2e4f438d229d88bc99eadc
52 schema:url https://doi.org/10.1007/bf01200907
53 sgo:license sg:explorer/license/
54 sgo:sdDataset articles
55 rdf:type schema:ScholarlyArticle
56 N0d125799225e48d1b118a72de0dbacb4 schema:volumeNumber 17
57 rdf:type schema:PublicationVolume
58 N2d3585bb9a714b23b4f12a3f7a6548ae schema:issueNumber 2
59 rdf:type schema:PublicationIssue
60 N2f7bf26909a44523904d1cfe1155fe11 rdf:first sg:person.012003400773.68
61 rdf:rest Nd6c4c516f24b4f03a778c77623f23db9
62 N39e4092105364c2da81e70e24bf451d0 schema:name dimensions_id
63 schema:value pub.1019819433
64 rdf:type schema:PropertyValue
65 N4673c3fccc8c4d1382fba0d62dcebf64 schema:name doi
66 schema:value 10.1007/bf01200907
67 rdf:type schema:PropertyValue
68 N4a7fbfe0de2e4f438d229d88bc99eadc schema:name Springer Nature - SN SciGraph project
69 rdf:type schema:Organization
70 Nbb6b303598324e2bbc4975bea69e9ac2 rdf:first sg:person.01101524740.75
71 rdf:rest rdf:nil
72 Nc6f981bde85f4d1ebf4483d1a887050c rdf:first sg:person.015760032537.47
73 rdf:rest N2f7bf26909a44523904d1cfe1155fe11
74 Nd6c4c516f24b4f03a778c77623f23db9 rdf:first sg:person.011520224512.05
75 rdf:rest Nbb6b303598324e2bbc4975bea69e9ac2
76 anzsrc-for:01 schema:inDefinedTermSet anzsrc-for:
77 schema:name Mathematical Sciences
78 rdf:type schema:DefinedTerm
79 anzsrc-for:0101 schema:inDefinedTermSet anzsrc-for:
80 schema:name Pure Mathematics
81 rdf:type schema:DefinedTerm
82 sg:journal.1136493 schema:issn 0209-9683
83 1439-6912
84 schema:name Combinatorica
85 schema:publisher Springer Nature
86 rdf:type schema:Periodical
87 sg:person.01101524740.75 schema:affiliation grid-institutes:grid.89336.37
88 schema:familyName Zuckerman
89 schema:givenName David
90 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01101524740.75
91 rdf:type schema:Person
92 sg:person.011520224512.05 schema:affiliation grid-institutes:grid.430387.b
93 schema:familyName Saks
94 schema:givenName Michael
95 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011520224512.05
96 rdf:type schema:Person
97 sg:person.012003400773.68 schema:affiliation grid-institutes:None
98 schema:familyName Luby
99 schema:givenName Michael
100 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.012003400773.68
101 rdf:type schema:Person
102 sg:person.015760032537.47 schema:affiliation grid-institutes:grid.9619.7
103 schema:familyName Linial
104 schema:givenName Nathan
105 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015760032537.47
106 rdf:type schema:Person
107 sg:pub.10.1007/bf01271266 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021385362
108 https://doi.org/10.1007/bf01271266
109 rdf:type schema:CreativeWork
110 sg:pub.10.1007/bf01305237 schema:sameAs https://app.dimensions.ai/details/publication/pub.1019048384
111 https://doi.org/10.1007/bf01305237
112 rdf:type schema:CreativeWork
113 sg:pub.10.1007/bf01940870 schema:sameAs https://app.dimensions.ai/details/publication/pub.1041202529
114 https://doi.org/10.1007/bf01940870
115 rdf:type schema:CreativeWork
116 sg:pub.10.1007/bf01940873 schema:sameAs https://app.dimensions.ai/details/publication/pub.1001000053
117 https://doi.org/10.1007/bf01940873
118 rdf:type schema:CreativeWork
119 grid-institutes:None schema:alternateName DEC/SRC, 130 Lytton Avenue, 94301, Palo Alto, California
120 schema:name DEC/SRC, 130 Lytton Avenue, 94301, Palo Alto, California
121 rdf:type schema:Organization
122 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics, Rutgers University, 08854, New Brunswick, NJ, USA
123 schema:name Department of Mathematics, Rutgers University, 08854, New Brunswick, NJ, USA
124 rdf:type schema:Organization
125 grid-institutes:grid.89336.37 schema:alternateName Department of Computer Sciences, The University of Texas at Austin, 78713, Austin, Texas, USA
126 schema:name Department of Computer Sciences, The University of Texas at Austin, 78713, Austin, Texas, USA
127 rdf:type schema:Organization
128 grid-institutes:grid.9619.7 schema:alternateName Computer Science Department, Hebrew University, Jerusalem, Israel
129 schema:name Computer Science Department, Hebrew University, Jerusalem, Israel
130 rdf:type schema:Organization
 




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


...