Circuit lower bounds à la Kolmogorov

DOI10.1006/INCO.1995.1161zbMATH Open1096.68632OpenAlexW2351207523MaRDI QIDQ2508341FDOQ2508341

Authors: Sophie Laplante, Lance Fortnow 

Publication date: 10 October 2006

Published in: Information and Computation (Search for Journal in Brave)

Full work available at URL: https://semanticscholar.org/paper/604c1d5ca86c26ac2ced62ab876626d0d1add4ce

Recommendations

• Natural proofs
• Natural proofs
• A Kolmogorov complexity proof of the Lovász local lemma for satisfiability
• On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy
• Logical Approaches to Computational Barriers

Mathematics Subject Classification ID

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

Cited In (4)

• Circuit complexity before the dawn of the new millennium
• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• On some recent projection switching lemmas for small depth circuits
• A semantic view of the switching lemma

This page was built for publication: Circuit lower bounds à la Kolmogorov

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2508341)