Ontology type: schema:ScholarlyArticle
1984-12
AUTHORSMerrick Furst, James B. Saxe, Michael Sipser
ABSTRACTA super-polynomial lower bound is given for the size of circuits of fixed depth computing the parity function. Introducing the notion of polynomial-size, constant-depth reduction, similar results are shown for the majority, multiplication, and transitive closure functions. Connections are given to the theory of programmable logic arrays and to the relativization of the polynomial-time hierarchy. More... »
PAGES13-27
http://scigraph.springernature.com/pub.10.1007/bf01744431
DOIhttp://dx.doi.org/10.1007/bf01744431
DIMENSIONShttps://app.dimensions.ai/details/publication/pub.1011469743
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/0101",
"inDefinedTermSet": "http://purl.org/au-research/vocabulary/anzsrc-for/2008/",
"name": "Pure Mathematics",
"type": "DefinedTerm"
},
{
"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"
}
],
"author": [
{
"affiliation": {
"alternateName": "Carnegie Mellon University",
"id": "https://www.grid.ac/institutes/grid.147455.6",
"name": [
"Department of Computer Science, Carnegie-Mellon University, 15213, Pittsburgh, Pa., USA"
],
"type": "Organization"
},
"familyName": "Furst",
"givenName": "Merrick",
"id": "sg:person.0621550627.92",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.0621550627.92"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Carnegie Mellon University",
"id": "https://www.grid.ac/institutes/grid.147455.6",
"name": [
"Department of Computer Science, Carnegie-Mellon University, 15213, Pittsburgh, Pa., USA"
],
"type": "Organization"
},
"familyName": "Saxe",
"givenName": "James B.",
"id": "sg:person.016640143533.89",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.016640143533.89"
],
"type": "Person"
},
{
"affiliation": {
"alternateName": "Massachusetts Institute of Technology",
"id": "https://www.grid.ac/institutes/grid.116068.8",
"name": [
"Department of Mathematics, Massachusetts Institute of Technology, 02139, Boston, Mass., USA"
],
"type": "Organization"
},
"familyName": "Sipser",
"givenName": "Michael",
"id": "sg:person.01352114470.64",
"sameAs": [
"https://app.dimensions.ai/discover/publication?and_facet_researcher=ur.01352114470.64"
],
"type": "Person"
}
],
"citation": [
{
"id": "https://doi.org/10.1016/0304-3975(80)90027-4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1006781257"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0304-3975(80)90074-2",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1015773555"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1145/322234.322243",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1021206590"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0304-3975(79)90043-4",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1028600948"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01683260",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039984490",
"https://doi.org/10.1007/bf01683260"
],
"type": "CreativeWork"
},
{
"id": "sg:pub.10.1007/bf01683260",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1039984490",
"https://doi.org/10.1007/bf01683260"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1016/0304-3975(76)90061-x",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1048647089"
],
"type": "CreativeWork"
},
{
"id": "https://doi.org/10.1137/0204037",
"sameAs": [
"https://app.dimensions.ai/details/publication/pub.1062841277"
],
"type": "CreativeWork"
}
],
"datePublished": "1984-12",
"datePublishedReg": "1984-12-01",
"description": "A super-polynomial lower bound is given for the size of circuits of fixed depth computing the parity function. Introducing the notion of polynomial-size, constant-depth reduction, similar results are shown for the majority, multiplication, and transitive closure functions. Connections are given to the theory of programmable logic arrays and to the relativization of the polynomial-time hierarchy.",
"genre": "research_article",
"id": "sg:pub.10.1007/bf01744431",
"inLanguage": [
"en"
],
"isAccessibleForFree": false,
"isPartOf": [
{
"id": "sg:journal.1317508",
"issn": [
"0025-5661"
],
"name": "Mathematical Systems Theory",
"type": "Periodical"
},
{
"issueNumber": "1",
"type": "PublicationIssue"
},
{
"type": "PublicationVolume",
"volumeNumber": "17"
}
],
"name": "Parity, circuits, and the polynomial-time hierarchy",
"pagination": "13-27",
"productId": [
{
"name": "readcube_id",
"type": "PropertyValue",
"value": [
"36a5512624762aad0c75d321d2ecfe05bc4e6aad070e821f6d019cd083178d05"
]
},
{
"name": "doi",
"type": "PropertyValue",
"value": [
"10.1007/bf01744431"
]
},
{
"name": "dimensions_id",
"type": "PropertyValue",
"value": [
"pub.1011469743"
]
}
],
"sameAs": [
"https://doi.org/10.1007/bf01744431",
"https://app.dimensions.ai/details/publication/pub.1011469743"
],
"sdDataset": "articles",
"sdDatePublished": "2019-04-11T10:02",
"sdLicense": "https://scigraph.springernature.com/explorer/license/",
"sdPublisher": {
"name": "Springer Nature - SN SciGraph project",
"type": "Organization"
},
"sdSource": "s3://com-uberresearch-data-dimensions-target-20181106-alternative/cleanup/v134/2549eaecd7973599484d7c17b260dba0a4ecb94b/merge/v9/a6c9fde33151104705d4d7ff012ea9563521a3ce/jats-lookup/v90/0000000347_0000000347/records_89822_00000000.jsonl",
"type": "ScholarlyArticle",
"url": "http://link.springer.com/10.1007/BF01744431"
}
]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/bf01744431'
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/bf01744431'
Turtle is a human-readable linked data format.
curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/pub.10.1007/bf01744431'
RDF/XML is a standard XML format for linked data.
curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/pub.10.1007/bf01744431'
This table displays all metadata directly associated to this object as RDF triples.
99 TRIPLES
21 PREDICATES
34 URIs
19 LITERALS
7 BLANK NODES