Equivalence of Polynomial Identity Testing and Polynomial Factorization View Full Text


Ontology type: schema:ScholarlyArticle     


Article Info

DATE

2015-04-17

AUTHORS

Swastik Kopparty, Shubhangi Saraf, Amir Shpilka

ABSTRACT

In this paper, we show that the problem of deterministically factoring multivariate polynomials reduces to the problem of deterministic polynomial identity testing. Specifically, we show that given an arithmetic circuit (either explicitly or via black-box access) that computes a multivariate polynomial f, the task of computing arithmetic circuits for the factors of f can be solved deterministically, given a deterministic algorithm for the polynomial identity testing problem (we require either a white-box or a black-box algorithm, depending on the representation of f).Together with the easy observation that deterministic factoring implies a deterministic algorithm for polynomial identity testing, this establishes an equivalence between these two central derandomization problems of arithmetic complexity.Previously, such an equivalence was known only for multilinear circuits (Shpilka & Volkovich, 2010). More... »

PAGES

295-331

References to SciGraph publications

  • 2010. On the Relation between Polynomial Identity Testing and Finding Variable Disjoint Factors in AUTOMATA, LANGUAGES AND PROGRAMMING
  • 1979. Probabilistic algorithms for sparse polynomials in SYMBOLIC AND ALGEBRAIC COMPUTATION
  • 1987-03. Matching is as easy as matrix inversion in COMBINATORICA
  • 1992. Polynomial factorization 1987–1991 in LATIN '92
  • 1982-12. Factoring polynomials with rational coefficients in MATHEMATISCHE ANNALEN
  • 2004-12. Derandomizing Polynomial Identity Tests Means Proving Circuit Lower Bounds in COMPUTATIONAL COMPLEXITY
  • 2005. Proving Lower Bounds Via Pseudo-random Generators in FSTTCS 2005: FOUNDATIONS OF SOFTWARE TECHNOLOGY AND THEORETICAL COMPUTER SCIENCE
  • Identifiers

    URI

    http://scigraph.springernature.com/pub.10.1007/s00037-015-0102-y

    DOI

    http://dx.doi.org/10.1007/s00037-015-0102-y

    DIMENSIONS

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


    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 Mathematics & Department of Computer Science, Rutgers University, New Brunswick, NJ, USA", 
              "id": "http://www.grid.ac/institutes/grid.430387.b", 
              "name": [
                "Department of Mathematics & Department of Computer Science, Rutgers University, New Brunswick, NJ, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Kopparty", 
            "givenName": "Swastik", 
            "id": "sg:person.014276170447.16", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014276170447.16"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Mathematics & Department of Computer Science, Rutgers University, New Brunswick, NJ, USA", 
              "id": "http://www.grid.ac/institutes/grid.430387.b", 
              "name": [
                "Department of Mathematics & Department of Computer Science, Rutgers University, New Brunswick, NJ, USA"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Saraf", 
            "givenName": "Shubhangi", 
            "id": "sg:person.015177766032.20", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015177766032.20"
            ], 
            "type": "Person"
          }, 
          {
            "affiliation": {
              "alternateName": "Department of Computer Science, Tel Aviv University, Tel Aviv, Israel", 
              "id": "http://www.grid.ac/institutes/grid.12136.37", 
              "name": [
                "Department of Computer Science, Tel Aviv University, Tel Aviv, Israel"
              ], 
              "type": "Organization"
            }, 
            "familyName": "Shpilka", 
            "givenName": "Amir", 
            "id": "sg:person.010556352637.70", 
            "sameAs": [
              "https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010556352637.70"
            ], 
            "type": "Person"
          }
        ], 
        "citation": [
          {
            "id": "sg:pub.10.1007/bf01457454", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1048792211", 
              "https://doi.org/10.1007/bf01457454"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/3-540-09519-5_73", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1030416919", 
              "https://doi.org/10.1007/3-540-09519-5_73"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/978-3-642-14165-2_35", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1038651763", 
              "https://doi.org/10.1007/978-3-642-14165-2_35"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bfb0023837", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1049472987", 
              "https://doi.org/10.1007/bfb0023837"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/11590156_6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1026283866", 
              "https://doi.org/10.1007/11590156_6"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/bf02579206", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1029834600", 
              "https://doi.org/10.1007/bf02579206"
            ], 
            "type": "CreativeWork"
          }, 
          {
            "id": "sg:pub.10.1007/s00037-004-0182-6", 
            "sameAs": [
              "https://app.dimensions.ai/details/publication/pub.1021223969", 
              "https://doi.org/10.1007/s00037-004-0182-6"
            ], 
            "type": "CreativeWork"
          }
        ], 
        "datePublished": "2015-04-17", 
        "datePublishedReg": "2015-04-17", 
        "description": "In this paper, we show that the problem of deterministically factoring multivariate polynomials reduces to the problem of deterministic polynomial identity testing. Specifically, we show that given an arithmetic circuit (either explicitly or via black-box access) that computes a multivariate polynomial f, the task of computing arithmetic circuits for the factors of f can be solved deterministically, given a deterministic algorithm for the polynomial identity testing problem (we require either a white-box or a black-box algorithm, depending on the representation of f).Together with the easy observation that deterministic factoring implies a deterministic algorithm for polynomial identity testing, this establishes an equivalence between these two central derandomization problems of arithmetic complexity.Previously, such an equivalence was known only for multilinear circuits (Shpilka & Volkovich, 2010).", 
        "genre": "article", 
        "id": "sg:pub.10.1007/s00037-015-0102-y", 
        "inLanguage": "en", 
        "isAccessibleForFree": false, 
        "isPartOf": [
          {
            "id": "sg:journal.1136224", 
            "issn": [
              "1016-3328", 
              "1420-8954"
            ], 
            "name": "computational complexity", 
            "publisher": "Springer Nature", 
            "type": "Periodical"
          }, 
          {
            "issueNumber": "2", 
            "type": "PublicationIssue"
          }, 
          {
            "type": "PublicationVolume", 
            "volumeNumber": "24"
          }
        ], 
        "keywords": [
          "deterministic algorithm", 
          "paper", 
          "problem", 
          "multivariate polynomials", 
          "polynomials", 
          "polynomial identity testing", 
          "identity testing", 
          "testing", 
          "arithmetic circuits", 
          "circuit", 
          "multivariate polynomial f", 
          "polynomial f", 
          "task", 
          "factors", 
          "algorithm", 
          "polynomial identity testing problem", 
          "identity testing problem", 
          "testing problem", 
          "easy observation", 
          "observations", 
          "factoring", 
          "equivalence", 
          "arithmetic complexity", 
          "complexity", 
          "polynomial factorization", 
          "factorization", 
          "multilinear circuits"
        ], 
        "name": "Equivalence of Polynomial Identity Testing and Polynomial Factorization", 
        "pagination": "295-331", 
        "productId": [
          {
            "name": "dimensions_id", 
            "type": "PropertyValue", 
            "value": [
              "pub.1046608018"
            ]
          }, 
          {
            "name": "doi", 
            "type": "PropertyValue", 
            "value": [
              "10.1007/s00037-015-0102-y"
            ]
          }
        ], 
        "sameAs": [
          "https://doi.org/10.1007/s00037-015-0102-y", 
          "https://app.dimensions.ai/details/publication/pub.1046608018"
        ], 
        "sdDataset": "articles", 
        "sdDatePublished": "2022-06-01T22:15", 
        "sdLicense": "https://scigraph.springernature.com/explorer/license/", 
        "sdPublisher": {
          "name": "Springer Nature - SN SciGraph project", 
          "type": "Organization"
        }, 
        "sdSource": "s3://com-springernature-scigraph/baseset/20220601/entities/gbq_results/article/article_665.jsonl", 
        "type": "ScholarlyArticle", 
        "url": "https://doi.org/10.1007/s00037-015-0102-y"
      }
    ]
     

    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-015-0102-y'

    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-015-0102-y'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/s00037-015-0102-y'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/s00037-015-0102-y'


     

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

    142 TRIPLES      22 PREDICATES      62 URIs      44 LITERALS      6 BLANK NODES

    Subject Predicate Object
    1 sg:pub.10.1007/s00037-015-0102-y schema:about anzsrc-for:08
    2 anzsrc-for:0801
    3 anzsrc-for:0802
    4 anzsrc-for:17
    5 anzsrc-for:1702
    6 schema:author N056f0067208342df8f00be13a7e9d148
    7 schema:citation sg:pub.10.1007/11590156_6
    8 sg:pub.10.1007/3-540-09519-5_73
    9 sg:pub.10.1007/978-3-642-14165-2_35
    10 sg:pub.10.1007/bf01457454
    11 sg:pub.10.1007/bf02579206
    12 sg:pub.10.1007/bfb0023837
    13 sg:pub.10.1007/s00037-004-0182-6
    14 schema:datePublished 2015-04-17
    15 schema:datePublishedReg 2015-04-17
    16 schema:description In this paper, we show that the problem of deterministically factoring multivariate polynomials reduces to the problem of deterministic polynomial identity testing. Specifically, we show that given an arithmetic circuit (either explicitly or via black-box access) that computes a multivariate polynomial f, the task of computing arithmetic circuits for the factors of f can be solved deterministically, given a deterministic algorithm for the polynomial identity testing problem (we require either a white-box or a black-box algorithm, depending on the representation of f).Together with the easy observation that deterministic factoring implies a deterministic algorithm for polynomial identity testing, this establishes an equivalence between these two central derandomization problems of arithmetic complexity.Previously, such an equivalence was known only for multilinear circuits (Shpilka & Volkovich, 2010).
    17 schema:genre article
    18 schema:inLanguage en
    19 schema:isAccessibleForFree false
    20 schema:isPartOf N417abaf0a8ed47bc8ea9f406009d28a0
    21 N50fdd98a83e54dca8e0fdeb7ce3d3bc9
    22 sg:journal.1136224
    23 schema:keywords algorithm
    24 arithmetic circuits
    25 arithmetic complexity
    26 circuit
    27 complexity
    28 deterministic algorithm
    29 easy observation
    30 equivalence
    31 factoring
    32 factorization
    33 factors
    34 identity testing
    35 identity testing problem
    36 multilinear circuits
    37 multivariate polynomial f
    38 multivariate polynomials
    39 observations
    40 paper
    41 polynomial f
    42 polynomial factorization
    43 polynomial identity testing
    44 polynomial identity testing problem
    45 polynomials
    46 problem
    47 task
    48 testing
    49 testing problem
    50 schema:name Equivalence of Polynomial Identity Testing and Polynomial Factorization
    51 schema:pagination 295-331
    52 schema:productId N0cf67a9ad27446f2918a3e4e47add790
    53 N9000a0eb613b462689c69bfd88ad41f0
    54 schema:sameAs https://app.dimensions.ai/details/publication/pub.1046608018
    55 https://doi.org/10.1007/s00037-015-0102-y
    56 schema:sdDatePublished 2022-06-01T22:15
    57 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    58 schema:sdPublisher N4b6d0e9eda5a427ca72edc023a6ab6c7
    59 schema:url https://doi.org/10.1007/s00037-015-0102-y
    60 sgo:license sg:explorer/license/
    61 sgo:sdDataset articles
    62 rdf:type schema:ScholarlyArticle
    63 N056f0067208342df8f00be13a7e9d148 rdf:first sg:person.014276170447.16
    64 rdf:rest N5bf4fc2296f04c37894c57769fe2d95b
    65 N0cf67a9ad27446f2918a3e4e47add790 schema:name doi
    66 schema:value 10.1007/s00037-015-0102-y
    67 rdf:type schema:PropertyValue
    68 N417abaf0a8ed47bc8ea9f406009d28a0 schema:issueNumber 2
    69 rdf:type schema:PublicationIssue
    70 N4b6d0e9eda5a427ca72edc023a6ab6c7 schema:name Springer Nature - SN SciGraph project
    71 rdf:type schema:Organization
    72 N50fdd98a83e54dca8e0fdeb7ce3d3bc9 schema:volumeNumber 24
    73 rdf:type schema:PublicationVolume
    74 N5bf4fc2296f04c37894c57769fe2d95b rdf:first sg:person.015177766032.20
    75 rdf:rest Nb216f128a6eb4b3c9ad6f49c5d340329
    76 N9000a0eb613b462689c69bfd88ad41f0 schema:name dimensions_id
    77 schema:value pub.1046608018
    78 rdf:type schema:PropertyValue
    79 Nb216f128a6eb4b3c9ad6f49c5d340329 rdf:first sg:person.010556352637.70
    80 rdf:rest rdf:nil
    81 anzsrc-for:08 schema:inDefinedTermSet anzsrc-for:
    82 schema:name Information and Computing Sciences
    83 rdf:type schema:DefinedTerm
    84 anzsrc-for:0801 schema:inDefinedTermSet anzsrc-for:
    85 schema:name Artificial Intelligence and Image Processing
    86 rdf:type schema:DefinedTerm
    87 anzsrc-for:0802 schema:inDefinedTermSet anzsrc-for:
    88 schema:name Computation Theory and Mathematics
    89 rdf:type schema:DefinedTerm
    90 anzsrc-for:17 schema:inDefinedTermSet anzsrc-for:
    91 schema:name Psychology and Cognitive Sciences
    92 rdf:type schema:DefinedTerm
    93 anzsrc-for:1702 schema:inDefinedTermSet anzsrc-for:
    94 schema:name Cognitive Sciences
    95 rdf:type schema:DefinedTerm
    96 sg:journal.1136224 schema:issn 1016-3328
    97 1420-8954
    98 schema:name computational complexity
    99 schema:publisher Springer Nature
    100 rdf:type schema:Periodical
    101 sg:person.010556352637.70 schema:affiliation grid-institutes:grid.12136.37
    102 schema:familyName Shpilka
    103 schema:givenName Amir
    104 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.010556352637.70
    105 rdf:type schema:Person
    106 sg:person.014276170447.16 schema:affiliation grid-institutes:grid.430387.b
    107 schema:familyName Kopparty
    108 schema:givenName Swastik
    109 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.014276170447.16
    110 rdf:type schema:Person
    111 sg:person.015177766032.20 schema:affiliation grid-institutes:grid.430387.b
    112 schema:familyName Saraf
    113 schema:givenName Shubhangi
    114 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.015177766032.20
    115 rdf:type schema:Person
    116 sg:pub.10.1007/11590156_6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1026283866
    117 https://doi.org/10.1007/11590156_6
    118 rdf:type schema:CreativeWork
    119 sg:pub.10.1007/3-540-09519-5_73 schema:sameAs https://app.dimensions.ai/details/publication/pub.1030416919
    120 https://doi.org/10.1007/3-540-09519-5_73
    121 rdf:type schema:CreativeWork
    122 sg:pub.10.1007/978-3-642-14165-2_35 schema:sameAs https://app.dimensions.ai/details/publication/pub.1038651763
    123 https://doi.org/10.1007/978-3-642-14165-2_35
    124 rdf:type schema:CreativeWork
    125 sg:pub.10.1007/bf01457454 schema:sameAs https://app.dimensions.ai/details/publication/pub.1048792211
    126 https://doi.org/10.1007/bf01457454
    127 rdf:type schema:CreativeWork
    128 sg:pub.10.1007/bf02579206 schema:sameAs https://app.dimensions.ai/details/publication/pub.1029834600
    129 https://doi.org/10.1007/bf02579206
    130 rdf:type schema:CreativeWork
    131 sg:pub.10.1007/bfb0023837 schema:sameAs https://app.dimensions.ai/details/publication/pub.1049472987
    132 https://doi.org/10.1007/bfb0023837
    133 rdf:type schema:CreativeWork
    134 sg:pub.10.1007/s00037-004-0182-6 schema:sameAs https://app.dimensions.ai/details/publication/pub.1021223969
    135 https://doi.org/10.1007/s00037-004-0182-6
    136 rdf:type schema:CreativeWork
    137 grid-institutes:grid.12136.37 schema:alternateName Department of Computer Science, Tel Aviv University, Tel Aviv, Israel
    138 schema:name Department of Computer Science, Tel Aviv University, Tel Aviv, Israel
    139 rdf:type schema:Organization
    140 grid-institutes:grid.430387.b schema:alternateName Department of Mathematics & Department of Computer Science, Rutgers University, New Brunswick, NJ, USA
    141 schema:name Department of Mathematics & Department of Computer Science, Rutgers University, New Brunswick, NJ, USA
    142 rdf:type schema:Organization
     




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


    ...