Learning algorithms from circuit lower bounds

DOI10.1007/S00037-024-00261-4MaRDI QIDQ6998468zbMATH OpenFDO

Authors Ján Pich

Publication date 11 April 2025

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-00261-4

zbMATH Keywords

circuit lower boundslearning algorithms

Mathematics Subject Classification ID

Networks and circuits as models of computation; circuit complexity (68Q06) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Computational learning theory (68Q32)

Cites work

• Beyond natural proofs: hardness magnification and locality
• Bootstrapping results for threshold circuits ``just beyond known lower bounds
• Bounded arithmetic and the polynomial hierarchy
• Circuit lower bounds in bounded arithmetics
• Constant depth circuits, Fourier transform, and learnability
• Cryptography from sublinear-time average-case hardness of time-bounded Kolmogorov complexity
• Dual weak pigeonhole principle, pseudo-surjective functions, and provability of circuit lower bounds
• Hardness magnification for all sparse NP languages
• Hardness magnification for natural problems
• Hardness vs randomness
• scientific article; zbMATH DE number 5845490 (Why is no real title available?)
• scientific article; zbMATH DE number 819737 (Why is no real title available?)
• scientific article; zbMATH DE number 7561748 (Why is no real title available?)
• scientific article; zbMATH DE number 7561750 (Why is no real title available?)
• scientific article; zbMATH DE number 7650416 (Why is no real title available?)
• Learning in Pessiland via inductive inference
• Natural proofs
• Nisan-Wigderson generators in proof systems with forms of interpolation
• Non-black-box worst-case to average-case reductions within NP
• On sparse approximations to randomized strategies and convex combinations
• On the computational complexity of finding hard tautologies
• ON THE PROOF COMPLEXITY OF THE NISAN–WIGDERSON GENERATOR BASED ON A HARD NP ∩ coNP FUNCTION
• Private vs. common random bits in communication complexity
• Proof Complexity
• Pseudo-finite hard instances for a student-teacher game with a Nisan-Wigderson generator
• Pseudorandom generators hard for \(k\)-DNF resolution and polynomial calculus resolution
• Sharp threshold results for computational complexity
• Simple strategies for large zero-sum games with applications to complexity theory
• Strong co-nondeterministic lower bounds for NP cannot be proved feasibly
• Unprovability of lower bounds on circuit size in certain fragments of bounded arithmetic
• Weak lower bounds on resource-bounded compression imply strong separations of complexity classes

This page was built for publication: Learning algorithms from circuit lower bounds

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