computational complexity View Homepage


Ontology type: schema:Periodical     


Journal Info

START YEAR

N/A

PUBLISHER

Springer International Publishing

LANGUAGE

en

HOMEPAGE

https://link.springer.com/journal/37

Recent publications latest 20 shown

  • 2022-03-16 Expander-Based Cryptography Meets Natural Proofs
  • 2022-02-05 Amplification with One NP Oracle Query
  • 2022-02-03 The complexity of approximating the complex-valued Potts model
  • 2021-12-18 Rank and border rank of Kronecker powers of tensors and Strassen's laser method
  • 2021-11-17 Correction to: Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs
  • 2021-10-15 Factorization of Polynomials Given by Arithmetic Branching Programs
  • 2021-10-08 Lower Bounds for Arithmetic Circuits via the Hankel Matrix
  • 2021-08-27 Near-Optimal Lower Bounds on Regular Resolution Refutations of Tseitin Formulas for All Constant-Degree Graphs
  • 2021-08-18 An Exponential Separation Between MA and AM Proofs of Proximity
  • 2021-08-03 The hardest halfspace
  • 2021-07-02 Nondeterministic and Randomized Boolean Hierarchies in Communication Complexity
  • 2021-06-10 Blackbox identity testing for sum of special ROABPs and its border class
  • 2021-06-10 Correction to: Smooth and Strong PCPs
  • 2021-05-01 Reversible Pebble Games and the Relation Between Tree-Like and General Resolution Space
  • 2021-04-02 Lower Bounds for Matrix Factorization
  • 2021-03-02 Subquadratic-Time Algorithms for Normal Bases
  • 2021-02-12 Nullstellensatz Size-Degree Trade-offs from Reversible Pebbling
  • 2021-01-20 Explicit List-Decodable Codes with Optimal Rate for Computationally Bounded Channels
  • 2021-01-08 Resolution with Counting: Dag-Like Lower Bounds and Different Moduli
  • 2021-01-06 Smooth and Strong PCPs
  • 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", 
        "contentRating": [
          {
            "author": "snip", 
            "ratingValue": "1.4170000553131104", 
            "type": "Rating"
          }, 
          {
            "author": "sjr", 
            "ratingValue": "0.9729999899864197", 
            "type": "Rating"
          }
        ], 
        "description": "

    computational complexity presents outstanding research in computational complexity. Its subject is at the interface between mathematics and theoretical computer science, with a clear mathematical profile and strictly mathematical format.

    \n\n

    The central topics are:

    \n\n

    Models of computation, complexity bounds (with particular emphasis on lower bounds), complexity classes, trade-off results

    \n\n
      \n\t
    • for sequential and parallel computation
    • \n\t
    • for "general" (Boolean) and "structured" computation (e.g. decision trees, arithmetic circuits)
    • \n\t
    • for deterministic, probabilistic, and nondeterministic computation
    • \n\t
    • worst case and average case
    • \n
    \n\n


    \nSpecific areas of concentration include:

    \n\n
      \n\t
    • Structure of complexity classes (reductions, relativization questions, degrees, derandomization)
    • \n\t
    • Algebraic complexity (bilinear complexity, computations for polynomials, groups, algebras, and representations)
    • \n\t
    • Interactive proofs, pseudorandom generation, and randomness extraction
    • \n
    \n\n


    \nComplexity issues in:

    \n\n
      \n\t
    • cryptography
    • \n\t
    • learning theory
    • \n\t
    • number theory
    • \n\t
    • logic (complexity of logical theories, cost of decision procedures)
    • \n\t
    • combinatorial optimization and approximate solutions
    • \n\t
    • distributed computing
    • \n\t
    • property testing
    • \n
    \n\n


    \nBibliographic Data
    \ncomput. complex.
    \nFirst published in 1991
    \n1 volume per year, 2 issues per volume
    \napprox. 500 pages per volume
    \nFormat: 15.5 x 23.5 cm
    \nISSN 1016-3328 (print)
    \nISSN 1420-8954 (electronic)

    \n\n

    AMS Mathematical Citation Quotient (MCQ): 0.54 (2020)

    \n", "editor": [ { "familyName": "B\u00fcrgisser", "givenName": "Peter", "type": "Person" } ], "id": "sg:journal.1136224", "inLanguage": [ "en" ], "isAccessibleForFree": false, "issn": [ "1016-3328", "1420-8954" ], "license": "Hybrid", "name": "computational complexity", "productId": [ { "name": "dimensions_id", "type": "PropertyValue", "value": [ "136224" ] }, { "name": "nsd_ids_id", "type": "PropertyValue", "value": [ "439369" ] }, { "name": "era_ids_id", "type": "PropertyValue", "value": [ "30736" ] } ], "publisher": { "name": "Springer International Publishing", "type": "Organization" }, "publisherImprint": "Birkh\u00e4user", "sameAs": [ "https://app.dimensions.ai/discover/publication?and_facet_source_title=jour.1136224" ], "sdDataset": "journals", "sdDatePublished": "2022-05-10T11:01", "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/journal/journal_0.jsonl", "type": "Periodical", "url": "https://link.springer.com/journal/37" } ]
     

    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/journal.1136224'

    N-Triples is a line-based linked data format ideal for batch operations.

    curl -H 'Accept: application/n-triples' 'https://scigraph.springernature.com/journal.1136224'

    Turtle is a human-readable linked data format.

    curl -H 'Accept: text/turtle' 'https://scigraph.springernature.com/journal.1136224'

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

    curl -H 'Accept: application/rdf+xml' 'https://scigraph.springernature.com/journal.1136224'


     

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

    51 TRIPLES      19 PREDICATES      24 URIs      20 LITERALS      8 BLANK NODES

    Subject Predicate Object
    1 sg:journal.1136224 schema:contentRating N90ed5123ef6a419e800e12ed4585b22c
    2 Ne9cd7074954e48fda5e982d11b4f463c
    3 schema:description <p><em>computational complexity&nbsp;</em>presents outstanding research in computational complexity. Its subject is at the interface between mathematics and theoretical computer science, with a clear mathematical profile and strictly mathematical format.</p> <p>The central topics are:</p> <p>Models of computation, complexity bounds (with particular emphasis on lower bounds), complexity classes, trade-off results</p> <ul> <li>for sequential and parallel computation</li> <li>for &quot;general&quot; (Boolean) and &quot;structured&quot; computation (e.g. decision trees, arithmetic circuits)</li> <li>for deterministic, probabilistic, and nondeterministic computation</li> <li>worst case and average case</li> </ul> <p><br /> Specific areas of concentration include:</p> <ul> <li>Structure of complexity classes (reductions, relativization questions, degrees, derandomization)</li> <li>Algebraic complexity (bilinear complexity, computations for polynomials, groups, algebras, and representations)</li> <li>Interactive proofs, pseudorandom generation, and randomness extraction</li> </ul> <p><br /> Complexity issues in:</p> <ul> <li>cryptography</li> <li>learning theory</li> <li>number theory</li> <li>logic (complexity of logical theories, cost of decision procedures)</li> <li>combinatorial optimization and approximate solutions</li> <li>distributed computing</li> <li>property testing</li> </ul> <p><br /> <strong>Bibliographic Data</strong><br /> comput. complex.<br /> First published in 1991<br /> 1 volume per year,&nbsp;2 issues per volume<br /> approx. 500 pages per volume<br /> Format: 15.5 x 23.5 cm<br /> ISSN 1016-3328 (print)<br /> ISSN 1420-8954 (electronic)</p> <p><strong>AMS Mathematical Citation Quotient (MCQ):</strong> 0.54 (2020)</p>
    4 schema:editor Nd6303567e1934f4a93c91fe0a0ddc962
    5 schema:inLanguage en
    6 schema:isAccessibleForFree false
    7 schema:issn 1016-3328
    8 1420-8954
    9 schema:license Hybrid
    10 schema:name computational complexity
    11 schema:productId Na89f0d78bf0c4bbdb15889b0ac279ab8
    12 Nb4dc6e6232f04d5bb2c20e794d584883
    13 Nb9cc94ad30764065bb44531c44305199
    14 schema:publisher Nb9d000b7120144019ca011ca67f448d3
    15 schema:publisherImprint Birkhäuser
    16 schema:sameAs https://app.dimensions.ai/discover/publication?and_facet_source_title=jour.1136224
    17 schema:sdDatePublished 2022-05-10T11:01
    18 schema:sdLicense https://scigraph.springernature.com/explorer/license/
    19 schema:sdPublisher N8e2fe0dc8a5b4318b16eccb2c3ce2abd
    20 schema:url https://link.springer.com/journal/37
    21 sgo:license sg:explorer/license/
    22 sgo:sdDataset journals
    23 rdf:type schema:Periodical
    24 N6f3418a4459f4737a2f6def244b002e0 rdf:first snip
    25 rdf:rest rdf:nil
    26 N8e2fe0dc8a5b4318b16eccb2c3ce2abd schema:name Springer Nature - SN SciGraph project
    27 rdf:type schema:Organization
    28 N90ed5123ef6a419e800e12ed4585b22c schema:author N6f3418a4459f4737a2f6def244b002e0
    29 schema:ratingValue 1.4170000553131104
    30 rdf:type schema:Rating
    31 Na678b99c341a4b4f83198bf03f9a16ff schema:familyName Bürgisser
    32 schema:givenName Peter
    33 rdf:type schema:Person
    34 Na89f0d78bf0c4bbdb15889b0ac279ab8 schema:name era_ids_id
    35 schema:value 30736
    36 rdf:type schema:PropertyValue
    37 Nb4dc6e6232f04d5bb2c20e794d584883 schema:name nsd_ids_id
    38 schema:value 439369
    39 rdf:type schema:PropertyValue
    40 Nb9085a998a2d49f99a77691d371f1f2c rdf:first sjr
    41 rdf:rest rdf:nil
    42 Nb9cc94ad30764065bb44531c44305199 schema:name dimensions_id
    43 schema:value 136224
    44 rdf:type schema:PropertyValue
    45 Nb9d000b7120144019ca011ca67f448d3 schema:name Springer International Publishing
    46 rdf:type schema:Organization
    47 Nd6303567e1934f4a93c91fe0a0ddc962 rdf:first Na678b99c341a4b4f83198bf03f9a16ff
    48 rdf:rest rdf:nil
    49 Ne9cd7074954e48fda5e982d11b4f463c schema:author Nb9085a998a2d49f99a77691d371f1f2c
    50 schema:ratingValue 0.9729999899864197
    51 rdf:type schema:Rating
     




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


    ...