Circuit lower bounds à la Kolmogorov

DOI10.1006/INCO.1995.1161MaRDI QIDQ2508341zbMATH OpenOpenAlexFDO

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

Mathematics Subject Classification ID

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

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

Cited in

(4)

• Reductions in circuit complexity: An isomorphism theorem and a gap theorem
• Circuit complexity before the dawn of the new millennium
• 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)