On the Limit of Some Algorithmic Approach to Circuit Lower Bounds

DOI10.1007/978-3-319-13350-8_29zbMath1323.68323OpenAlexW307845499MaRDI QIDQ2944904

Osamu Watanabe

Publication date: 8 September 2015

Published in: Computing with New Resources (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/978-3-319-13350-8_29

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Cites Work

• Turing machines that take advice
• Oracles and queries that are sufficient for exact learning
• Circuit-size lower bounds and non-reducibility to sparse sets
• Relativizations of the $\mathcal{P} = ?\mathcal{NP}$ Question
• New Collapse Consequences of NP Having Small Circuits
• On Proving Circuit Lower Bounds against the Polynomial-Time Hierarchy

This page was built for publication: On the Limit of Some Algorithmic Approach to Circuit Lower Bounds