Skip to main content

computational complexity OnlineFirst articles


On semiring complexity of Schur polynomials

Semiring complexity is the version of arithmetic circuit complexity that allows only two operations: addition and multiplication. We show that semiring complexity of a Schur polynomial $${s_\lambda(x_1,\dots,x_k)}$$ s λ ( x 1 , ⋯ , x k ) labeled …


An adaptivity hierarchy theorem for property testing

Adaptivity is known to play a crucial role in property testing. In particular, there exist properties for which there is an exponential gap between the power of adaptive testing algorithms, wherein each query may be determined by the answers …


Algebraic independence over positive characteristic: New criterion and applications to locally low-algebraic-rank circuits

The motivation for this work (Pandey et al. 2016) comes from two problems: testing algebraic independence of arithmetic circuits over a field of small characteristic and generalizing the structural property of algebraic dependence used by Kumar …


Tensor surgery and tensor rank

We introduce a method for transforming low-order tensors into higher-order tensors and apply it to tensors defined by graphs and hypergraphs. The transformation proceeds according to a surgery-like procedure that splits vertices, creates and …


Constructive non-commutative rank computation is in deterministic polynomial time

We extend the techniques developed in Ivanyos et al. (Comput Complex 26(3):717–763, 2017) to obtain a deterministic polynomial-time algorithm for computing the non-commutative rank of linear spaces of matrices over any field. The key new idea that …

Aktuelle Ausgaben

Über diese Zeitschrift

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.

The central topics are:

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

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

Specific areas of concentration include:

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

Complexity issues in:

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

Bibliographic Data
comput. complex.
First published in 1991
1 volume per year, 4 issues per volume
approx. 800 pages per volume
Format: 15.5 x 23.5 cm
ISSN 1016-3328 (print)
ISSN 1420-8954 (electronic)

AMS Mathematical Citation Quotient (MCQ): 0.30 (2015)

Weitere Informationen

Premium Partner

Neuer Inhalt

BranchenIndex Online

Die B2B-Firmensuche für Industrie und Wirtschaft: Kostenfrei in Firmenprofilen nach Lieferanten, Herstellern, Dienstleistern und Händlern recherchieren.



Product Lifecycle Management im Konzernumfeld – Herausforderungen, Lösungsansätze und Handlungsempfehlungen

Für produzierende Unternehmen hat sich Product Lifecycle Management in den letzten Jahrzehnten in wachsendem Maße zu einem strategisch wichtigen Ansatz entwickelt. Forciert durch steigende Effektivitäts- und Effizienzanforderungen stellen viele Unternehmen ihre Product Lifecycle Management-Prozesse und -Informationssysteme auf den Prüfstand. Der vorliegende Beitrag beschreibt entlang eines etablierten Analyseframeworks Herausforderungen und Lösungsansätze im Product Lifecycle Management im Konzernumfeld.
Jetzt gratis downloaden!