Logical Approaches to Computational Barriers

DOI10.1007/11780342zbMath1145.68429OpenAlexW4255986326WikidataQ55968647 ScholiaQ55968647MaRDI QIDQ5898828

Sophie Laplante

Publication date: 30 April 2007

Published in: Lecture Notes in Computer Science (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/11780342

zbMATH Keywords

Kolmogorov complexitycircuit complexitycommunication complexityquery complexityLower bounds

Mathematics Subject Classification ID

Algorithmic information theory (Kolmogorov complexity, etc.) (68Q30) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

This page was built for publication: Logical Approaches to Computational Barriers