Reviewing bounds on the circuit size of the hardest functions

DOI10.1016/j.ipl.2005.03.009zbMath1185.68358OpenAlexW2017637046MaRDI QIDQ1041784

Peter Bro Miltersen, Gudmund Skovbjerg Frandsen

Publication date: 4 December 2009

Published in: Information Processing Letters (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.ipl.2005.03.009

zbMATH Keywords

computational complexity

Mathematics Subject Classification ID

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

Related Items (3)

Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ Minimum Circuit Size, Graph Isomorphism, and Related Problems ⋮ PAC-learning gains of Turing machines over circuits and neural networks

Cites Work

• Almost everywhere high nonuniform complexity
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Reviewing bounds on the circuit size of the hardest functions