Ontology type: schema:ScholarlyArticle
2015-04-17
AUTHORSSwastik Kopparty, Shubhangi Saraf, Amir Shpilka
ABSTRACTIn 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... »
PAGES295-331
http://scigraph.springernature.com/pub.10.1007/s00037-015-0102-y
DOIhttp://dx.doi.org/10.1007/s00037-015-0102-y
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1046608018
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
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