Skip to main content

computational complexity OnlineFirst articles


Query-to-Communication Lifting for PNP

We prove that the PNP-type query complexity (alternatively, decision list width) of any Boolean function f is quadratically related to the PNP-type communication complexity of a lifted version of f. As an application, we show that a certain …


Approximate Nonnegative Rank is Equivalent to the Smooth Rectangle Bound

We consider two known lower bounds on randomized communication complexity: the smooth rectangle bound and the logarithm of the approximate nonnegative rank. Our main result is that they are the same up to a multiplicative constant and a small …


Interactive proofs and a Shamir-like result for real number computations

We introduce and study interactive proofs in the framework of real number computations as introduced by Blum, Shub, and Smale. Ivanov and de Rougemont started this line of research showing that an analogue of Shamir’s result holds in the real …


Lower Bounds and PIT for Non-commutative Arithmetic Circuits with Restricted Parse Trees

We investigate the power of Non-commutative Arithmetic Circuits, which compute polynomials over the free non-commutative polynomial ring $${\mathbb{F}\langle{x_1,\ldots,x_N\rangle}}$$ F ⟨ x 1 , … , x N ⟩ , where variables do not commute. We …


Asymptotic tensor rank of graph tensors: beyond matrix multiplication

We present an upper bound on the exponent of the asymptotic behaviour of the tensor rank of a family of tensors defined by the complete graph on k vertices. For $${k \geq 4}$$ k ≥ 4 , we show that the exponent per edge is at most 0.77 …

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

BranchenIndex Online

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



Best Practices für die Mitarbeiter-Partizipation in der Produktentwicklung

Unternehmen haben das Innovationspotenzial der eigenen Mitarbeiter auch außerhalb der F&E-Abteilung erkannt. Viele Initiativen zur Partizipation scheitern in der Praxis jedoch häufig. Lesen Sie hier  - basierend auf einer qualitativ-explorativen Expertenstudie - mehr über die wesentlichen Problemfelder der mitarbeiterzentrierten Produktentwicklung und profitieren Sie von konkreten Handlungsempfehlungen aus der Praxis.
Jetzt gratis downloaden!