Localizability of the approximation method

DOI10.1007/S00037-024-00257-0MaRDI QIDQ6624428zbMATH OpenFDO

Authors Ján Pich

Publication date 25 October 2024

Published in Computational Complexity (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.1007/S00037-024-00257-0

zbMATH Keywords

approximation methodlocality barrier

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06)

Cites work

• \(\Sigma_ 1^ 1\)-formulae on finite structures
• Beyond Natural Proofs: Hardness Magnification and Locality
• Circuits with medium fan-in
• Computational Complexity
• Feasibly constructive proofs of succinct weak circuit lower bounds
• scientific article; zbMATH DE number 4008289 (Why is no real title available?)
• scientific article; zbMATH DE number 4059391 (Why is no real title available?)
• scientific article; zbMATH DE number 524142 (Why is no real title available?)
• Learning algorithms from natural proofs
• Lower bounds on monotone complexity of the logical permanent
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Natural proofs
• Simple strategies for large zero-sum games with applications to complexity theory
• Superlinear lower bounds for bounded-width branching programs
• The exact complexity of pseudorandom functions and the black-box natural proof barrier for bootstrapping results in computational complexity

This page was built for publication: Localizability of the approximation method

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