2-Transitivity is Insufficient for Local Testability View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2012-12-18

AUTHORS

Elena Grigorescu, Tali Kaufman, Madhu Sudan

ABSTRACT

A basic goal in property testing is to identify a minimal set of features that make a property testable. For the case when the property to be tested is membership in a binary linear error-correcting code, Alon et al. (Trans Inf Theory, 51(11):4032–4039, 2005) had conjectured that the presence of a single low-weight codeword in the dual, and “2-transitivity” of the code (i.e., the code being invariant under a 2-transitive group of permutations on the coordinates of the code) suffice to get local testability. We refute this conjecture by giving a family of error-correcting codes where the coordinates of the codewords form a large field of characteristic two, and the code is invariant under affine transformations of the domain. This class of properties was introduced by Kaufman & Sudan (STOC, 2008) as a setting where many results in algebraic property testing generalize. Our result shows a complementary virtue: This family also can be useful in producing counterexamples to natural conjectures. More... »

PAGES

137-158

References to SciGraph publications

  • 1991-03. Non-deterministic exponential time has two-prover interactive protocols in COMPUTATIONAL COMPLEXITY
  • 2011. On Sums of Locally Testable Affine Invariant Properties in APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION. ALGORITHMS AND TECHNIQUES
  • 2009. Succinct Representation of Codes with Applications to Testing in APPROXIMATION, RANDOMIZATION, AND COMBINATORIAL OPTIMIZATION. ALGORITHMS AND TECHNIQUES
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00037-012-0055-3

    DOI

    http://dx.doi.org/10.1007/s00037-012-0055-3

    DIMENSIONS

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


    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/08", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Information and Computing Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/17", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Psychology and Cognitive Sciences", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0801", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Artificial Intelligence and Image Processing", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/0802", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Computation Theory and Mathematics", 
            "type": "DefinedTerm"
          }, 
          {
            "id": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/1702", 
            "inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/", 
            "name": "Cognitive Sciences", 
            "type": "DefinedTerm"
          }
        ], 
        "author": [
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, Purdue University, 47907, West Lafayette, IN, USA", 
              "id": "http://www.grid.ac/institutes/grid.411031.6", 
              "name": [
                "Department of Computer Science, Purdue University, 47907, West Lafayette, IN, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Grigorescu", 
            "givenName": "Elena", 
            "id": "sg:person.014612515147.15", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014612515147.15"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Computer Science, Bar-Ilan University, 52900, Ramat Gan, Israel", 
              "id": "http://www.grid.ac/institutes/grid.22098.31", 
              "name": [
                "Computer Science, Bar-Ilan University, 52900, Ramat Gan, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kaufman", 
            "givenName": "Tali", 
            "id": "sg:person.011723444630.05", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011723444630.05"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Microsoft Research New England, One Memorial Drive, 02142, Cambridge, MA, USA", 
              "id": "http://www.grid.ac/institutes/grid.419815.0", 
              "name": [
                "Microsoft Research New England, One Memorial Drive, 02142, Cambridge, MA, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Sudan", 
            "givenName": "Madhu", 
            "id": "sg:person.014663420265.17", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/978-3-642-22935-0_34", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049575323", 
              "https://doi.org/10.1007/978-3-642-22935-0_34"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-03685-9_40", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1043623804", 
              "https://doi.org/10.1007/978-3-642-03685-9_40"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf01200056", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036331166", 
              "https://doi.org/10.1007/bf01200056"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2012-12-18", 
        "datePublishedReg": "2012-12-18", 
        "description": "A basic goal in property testing is to identify a minimal set of features that make a property testable. For the case when the property to be tested is membership in a binary linear error-correcting code, Alon et\u00a0al. (Trans Inf Theory, 51(11):4032\u20134039, 2005) had conjectured that the presence of a single low-weight codeword in the dual, and \u201c2-transitivity\u201d of the code (i.e., the code being invariant under a 2-transitive group of permutations on the coordinates of the code) suffice to get local testability. We refute this conjecture by giving a family of error-correcting codes where the coordinates of the codewords form a large field of characteristic two, and the code is invariant under affine transformations of the domain. This class of properties was introduced by Kaufman & Sudan (STOC, 2008) as a setting where many results in algebraic property testing generalize. Our result shows a complementary virtue: This family also can be useful in producing counterexamples to natural conjectures.", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00037-012-0055-3", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136224", 
            "issn": [
              "1016-3328", 
              "1420-8954"
            ], 
            "name": "computational complexity", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "1", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "22"
          }
        ], 
        "keywords": [
          "basic goal", 
          "error-correcting codes", 
          "membership", 
          "family", 
          "Kaufman", 
          "goal", 
          "testing", 
          "domain", 
          "class of properties", 
          "setting", 
          "results", 
          "set", 
          "features", 
          "testable", 
          "low-weight codewords", 
          "virtue", 
          "minimal set", 
          "linear error-correcting codes", 
          "code", 
          "testability", 
          "large field", 
          "field", 
          "affine transformation", 
          "class", 
          "counterexamples", 
          "cases", 
          "properties", 
          "al", 
          "presence", 
          "conjecture", 
          "coordinates", 
          "transformation", 
          "algebraic property testing", 
          "natural conjecture", 
          "property testing", 
          "binary linear error-correcting code", 
          "Alon et", 
          "et", 
          "codewords", 
          "dual", 
          "local testability", 
          "complementary virtues", 
          "Sudan"
        ], 
        "name": "2-Transitivity is Insufficient for Local Testability", 
        "pagination": "137-158", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1004336738"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00037-012-0055-3"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00037-012-0055-3", 
          "https://app.dimensions.ai/details/publication/pub.1004336738"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-05-10T10:08", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220509/entities/gbq_results/article/article_583.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00037-012-0055-3"
      }
    ]
     

    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/s00037-012-0055-3'

    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/s00037-012-0055-3'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00037-012-0055-3'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00037-012-0055-3'


     

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

    145 TRIPLES      22 PREDICATES      74 URIs      60 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00037-012-0055-3 schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 anzsrc-for:0802
    4 anzsrc-for:17
    5 anzsrc-for:1702
    6 schema:author Ne6f61460f2e6497d846c11368ecc8328
    7 schema:citation sg:pub.10.1007/978-3-642-03685-9_40
    8 sg:pub.10.1007/978-3-642-22935-0_34
    9 sg:pub.10.1007/bf01200056
    10 schema:datePublished 2012-12-18
    11 schema:datePublishedReg 2012-12-18
    12 schema:description A basic goal in property testing is to identify a minimal set of features that make a property testable. For the case when the property to be tested is membership in a binary linear error-correcting code, Alon et al. (Trans Inf Theory, 51(11):4032–4039, 2005) had conjectured that the presence of a single low-weight codeword in the dual, and “2-transitivity” of the code (i.e., the code being invariant under a 2-transitive group of permutations on the coordinates of the code) suffice to get local testability. We refute this conjecture by giving a family of error-correcting codes where the coordinates of the codewords form a large field of characteristic two, and the code is invariant under affine transformations of the domain. This class of properties was introduced by Kaufman & Sudan (STOC, 2008) as a setting where many results in algebraic property testing generalize. Our result shows a complementary virtue: This family also can be useful in producing counterexamples to natural conjectures.
    13 schema:genre article
    14 schema:inLanguage en
    15 schema:isAccessibleForFree false
    16 schema:isPartOf N0ea774ecec644c38b1c062f78d85d96f
    17 N42958143e0d24bf2aa9af1bd3bd93b17
    18 sg:journal.1136224
    19 schema:keywords Alon et
    20 Kaufman
    21 Sudan
    22 affine transformation
    23 al
    24 algebraic property testing
    25 basic goal
    26 binary linear error-correcting code
    27 cases
    28 class
    29 class of properties
    30 code
    31 codewords
    32 complementary virtues
    33 conjecture
    34 coordinates
    35 counterexamples
    36 domain
    37 dual
    38 error-correcting codes
    39 et
    40 family
    41 features
    42 field
    43 goal
    44 large field
    45 linear error-correcting codes
    46 local testability
    47 low-weight codewords
    48 membership
    49 minimal set
    50 natural conjecture
    51 presence
    52 properties
    53 property testing
    54 results
    55 set
    56 setting
    57 testability
    58 testable
    59 testing
    60 transformation
    61 virtue
    62 schema:name 2-Transitivity is Insufficient for Local Testability
    63 schema:pagination 137-158
    64 schema:productId N42663cc7e5a347d1b452b169ebdafe98
    65 Nec2469eb2e2d4f9dbf7c85187ba42d21
    66 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004336738
    67 https://doi.org/10.1007/s00037-012-0055-3
    68 schema:sdDatePublished 2022-05-10T10:08
    69 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    70 schema:sdPublisher N00169825a17941d19a2e78964b3c58b6
    71 schema:url https://doi.org/10.1007/s00037-012-0055-3
    72 sgo:license sg:explorer/license/
    73 sgo:sdDataset articles
    74 rdf:type schema:ScholarlyArticle
    75 N00169825a17941d19a2e78964b3c58b6 schema:name Springer Nature - SN SciGraph project
    76 rdf:type schema:Organization
    77 N0ea774ecec644c38b1c062f78d85d96f schema:volumeNumber 22
    78 rdf:type schema:PublicationVolume
    79 N14b0761b5c954e89bad5241b1a32e766 rdf:first sg:person.014663420265.17
    80 rdf:rest rdf:nil
    81 N42663cc7e5a347d1b452b169ebdafe98 schema:name doi
    82 schema:value 10.1007/s00037-012-0055-3
    83 rdf:type schema:PropertyValue
    84 N42958143e0d24bf2aa9af1bd3bd93b17 schema:issueNumber 1
    85 rdf:type schema:PublicationIssue
    86 Ne6f61460f2e6497d846c11368ecc8328 rdf:first sg:person.014612515147.15
    87 rdf:rest Nf15d83b7456744c88a911fb437bc5e2e
    88 Nec2469eb2e2d4f9dbf7c85187ba42d21 schema:name dimensions_id
    89 schema:value pub.1004336738
    90 rdf:type schema:PropertyValue
    91 Nf15d83b7456744c88a911fb437bc5e2e rdf:first sg:person.011723444630.05
    92 rdf:rest N14b0761b5c954e89bad5241b1a32e766
    93 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    94 schema:name Information and Computing Sciences
    95 rdf:type schema:DefinedTerm
    96 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    97 schema:name Artificial Intelligence and Image Processing
    98 rdf:type schema:DefinedTerm
    99 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    100 schema:name Computation Theory and Mathematics
    101 rdf:type schema:DefinedTerm
    102 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
    103 schema:name Psychology and Cognitive Sciences
    104 rdf:type schema:DefinedTerm
    105 anzsrc-for:1702 schema:inDefinedTermSet anzsrc-for:
    106 schema:name Cognitive Sciences
    107 rdf:type schema:DefinedTerm
    108 sg:journal.1136224 schema:issn 1016-3328
    109 1420-8954
    110 schema:name computational complexity
    111 schema:publisher Springer Nature
    112 rdf:type schema:Periodical
    113 sg:person.011723444630.05 schema:affiliation grid-institutes:grid.22098.31
    114 schema:familyName Kaufman
    115 schema:givenName Tali
    116 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011723444630.05
    117 rdf:type schema:Person
    118 sg:person.014612515147.15 schema:affiliation grid-institutes:grid.411031.6
    119 schema:familyName Grigorescu
    120 schema:givenName Elena
    121 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014612515147.15
    122 rdf:type schema:Person
    123 sg:person.014663420265.17 schema:affiliation grid-institutes:grid.419815.0
    124 schema:familyName Sudan
    125 schema:givenName Madhu
    126 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
    127 rdf:type schema:Person
    128 sg:pub.10.1007/978-3-642-03685-9_40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043623804
    129 https://doi.org/10.1007/978-3-642-03685-9_40
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/978-3-642-22935-0_34 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049575323
    132 https://doi.org/10.1007/978-3-642-22935-0_34
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/bf01200056 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036331166
    135 https://doi.org/10.1007/bf01200056
    136 rdf:type schema:CreativeWork
    137 grid-institutes:grid.22098.31 schema:alternateName Computer Science, Bar-Ilan University, 52900, Ramat Gan, Israel
    138 schema:name Computer Science, Bar-Ilan University, 52900, Ramat Gan, Israel
    139 rdf:type schema:Organization
    140 grid-institutes:grid.411031.6 schema:alternateName Department of Computer Science, Purdue University, 47907, West Lafayette, IN, USA
    141 schema:name Department of Computer Science, Purdue University, 47907, West Lafayette, IN, USA
    142 rdf:type schema:Organization
    143 grid-institutes:grid.419815.0 schema:alternateName Microsoft Research New England, One Memorial Drive, 02142, Cambridge, MA, USA
    144 schema:name Microsoft Research New England, One Memorial Drive, 02142, Cambridge, MA, USA
    145 rdf:type schema:Organization
     




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


    ...