Localizability of the approximation method
From MaRDI portal
Publication:6624428
DOI10.1007/s00037-024-00257-0MaRDI QIDQ6624428
Publication date: 25 October 2024
Published in: Computational Complexity (Search for Journal in Brave)
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- \(\Sigma_ 1^ 1\)-formulae on finite structures
- 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
- Superlinear lower bounds for bounded-width branching programs
- Feasibly constructive proofs of succinct weak circuit lower bounds
- Simple strategies for large zero-sum games with applications to complexity theory
- Computational Complexity
- Learning algorithms from natural proofs
- Beyond Natural Proofs: Hardness Magnification and Locality
- Natural proofs
- 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
