Logical Approaches to Computational Barriers

DOI10.1007/11780342zbMath1145.68429WikidataQ55968647 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 complexity; circuit complexity; communication complexity; query complexity; Lower bounds

Mathematics Subject Classification ID

68Q30: Algorithmic information theory (Kolmogorov complexity, etc.)

68Q17: Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.)