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
  • 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/None", 
              "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/bf01200056", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1036331166", 
              "https://doi.org/10.1007/bf01200056"
            ], 
            "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"
          }
        ], 
        "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": [
          "error-correcting codes", 
          "binary linear error-correcting code", 
          "linear error-correcting codes", 
          "algebraic property testing", 
          "class of properties", 
          "affine transformation", 
          "Alon et", 
          "low-weight codewords", 
          "minimal set", 
          "code", 
          "codewords", 
          "basic goal", 
          "property testing", 
          "testability", 
          "large field", 
          "complementary virtues", 
          "set", 
          "goal", 
          "features", 
          "local testability", 
          "domain", 
          "counterexamples", 
          "natural conjecture", 
          "testing", 
          "coordinates", 
          "class", 
          "results", 
          "testable", 
          "membership", 
          "family", 
          "field", 
          "transformation", 
          "conjecture", 
          "Kaufman", 
          "setting", 
          "cases", 
          "properties", 
          "dual", 
          "virtue", 
          "ET", 
          "al", 
          "presence", 
          "Sudan", 
          "property testable", 
          "single low-weight codeword"
        ], 
        "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-01-01T18:25", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220101/entities/gbq_results/article/article_559.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.

    143 TRIPLES      22 PREDICATES      75 URIs      62 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 N382b4e6353204227917365f14486d83b
    7 schema:citation sg:pub.10.1007/978-3-642-03685-9_40
    8 sg:pub.10.1007/bf01200056
    9 schema:datePublished 2012-12-18
    10 schema:datePublishedReg 2012-12-18
    11 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.
    12 schema:genre article
    13 schema:inLanguage en
    14 schema:isAccessibleForFree false
    15 schema:isPartOf N2a8c21f6b62e4819b39d480e04392839
    16 N30c036dad71a487d809f0c92911345b3
    17 sg:journal.1136224
    18 schema:keywords Alon et
    19 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 family
    40 features
    41 field
    42 goal
    43 large field
    44 linear error-correcting codes
    45 local testability
    46 low-weight codewords
    47 membership
    48 minimal set
    49 natural conjecture
    50 presence
    51 properties
    52 property testable
    53 property testing
    54 results
    55 set
    56 setting
    57 single low-weight codeword
    58 testability
    59 testable
    60 testing
    61 transformation
    62 virtue
    63 schema:name 2-Transitivity is Insufficient for Local Testability
    64 schema:pagination 137-158
    65 schema:productId Nd4be6103543945fd977f257f15411ec2
    66 Ndd4b74b80f9442029743baf0080b9006
    67 schema:sameAs https://app.dimensions.ai/details/publication/pub.1004336738
    68 https://doi.org/10.1007/s00037-012-0055-3
    69 schema:sdDatePublished 2022-01-01T18:25
    70 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    71 schema:sdPublisher Nd5034696d45b4775a80c599abd28e3bd
    72 schema:url https://doi.org/10.1007/s00037-012-0055-3
    73 sgo:license sg:explorer/license/
    74 sgo:sdDataset articles
    75 rdf:type schema:ScholarlyArticle
    76 N012ee24319d549c09859817b2b71f059 rdf:first sg:person.014663420265.17
    77 rdf:rest rdf:nil
    78 N2a8c21f6b62e4819b39d480e04392839 schema:issueNumber 1
    79 rdf:type schema:PublicationIssue
    80 N30c036dad71a487d809f0c92911345b3 schema:volumeNumber 22
    81 rdf:type schema:PublicationVolume
    82 N382b4e6353204227917365f14486d83b rdf:first sg:person.014612515147.15
    83 rdf:rest Nbaf22bf4b99d4a64b58913d9cce20e7e
    84 Nbaf22bf4b99d4a64b58913d9cce20e7e rdf:first sg:person.011723444630.05
    85 rdf:rest N012ee24319d549c09859817b2b71f059
    86 Nd4be6103543945fd977f257f15411ec2 schema:name doi
    87 schema:value 10.1007/s00037-012-0055-3
    88 rdf:type schema:PropertyValue
    89 Nd5034696d45b4775a80c599abd28e3bd schema:name Springer Nature - SN SciGraph project
    90 rdf:type schema:Organization
    91 Ndd4b74b80f9442029743baf0080b9006 schema:name dimensions_id
    92 schema:value pub.1004336738
    93 rdf:type schema:PropertyValue
    94 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    95 schema:name Information and Computing Sciences
    96 rdf:type schema:DefinedTerm
    97 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    98 schema:name Artificial Intelligence and Image Processing
    99 rdf:type schema:DefinedTerm
    100 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    101 schema:name Computation Theory and Mathematics
    102 rdf:type schema:DefinedTerm
    103 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
    104 schema:name Psychology and Cognitive Sciences
    105 rdf:type schema:DefinedTerm
    106 anzsrc-for:1702 schema:inDefinedTermSet anzsrc-for:
    107 schema:name Cognitive Sciences
    108 rdf:type schema:DefinedTerm
    109 sg:journal.1136224 schema:issn 1016-3328
    110 1420-8954
    111 schema:name computational complexity
    112 schema:publisher Springer Nature
    113 rdf:type schema:Periodical
    114 sg:person.011723444630.05 schema:affiliation grid-institutes:grid.22098.31
    115 schema:familyName Kaufman
    116 schema:givenName Tali
    117 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.011723444630.05
    118 rdf:type schema:Person
    119 sg:person.014612515147.15 schema:affiliation grid-institutes:grid.411031.6
    120 schema:familyName Grigorescu
    121 schema:givenName Elena
    122 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014612515147.15
    123 rdf:type schema:Person
    124 sg:person.014663420265.17 schema:affiliation grid-institutes:None
    125 schema:familyName Sudan
    126 schema:givenName Madhu
    127 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014663420265.17
    128 rdf:type schema:Person
    129 sg:pub.10.1007/978-3-642-03685-9_40 schema:sameAs https://app.dimensions.ai/details/publication/pub.1043623804
    130 https://doi.org/10.1007/978-3-642-03685-9_40
    131 rdf:type schema:CreativeWork
    132 sg:pub.10.1007/bf01200056 schema:sameAs https://app.dimensions.ai/details/publication/pub.1036331166
    133 https://doi.org/10.1007/bf01200056
    134 rdf:type schema:CreativeWork
    135 grid-institutes:None schema:alternateName Microsoft Research New England, One Memorial Drive, 02142, Cambridge, MA, USA
    136 schema:name Microsoft Research New England, One Memorial Drive, 02142, Cambridge, MA, USA
    137 rdf:type schema:Organization
    138 grid-institutes:grid.22098.31 schema:alternateName Computer Science, Bar-Ilan University, 52900, Ramat Gan, Israel
    139 schema:name Computer Science, Bar-Ilan University, 52900, Ramat Gan, Israel
    140 rdf:type schema:Organization
    141 grid-institutes:grid.411031.6 schema:alternateName Department of Computer Science, Purdue University, 47907, West Lafayette, IN, USA
    142 schema:name Department of Computer Science, Purdue University, 47907, West Lafayette, IN, USA
    143 rdf:type schema:Organization
     




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


    ...