Agnostic Learning from Tolerant Natural Proofs

DOI10.4230/LIPICS.APPROX-RANDOM.2017.35MaRDI QIDQ5002638zbMATH OpenOpenAlexFDO

Authors Marco L. Carmosino, Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova

Publication date 28 July 2021

Full work available at URL https://dblp.uni-trier.de/db/conf/approx/approx2017.html#CarmosinoIKK17

zbMATH Keywords

agnostic learningcircuit lower boundsmeta-algorithmsnatural proofsNisan-Wigderson generator

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)

Recommendations

• Learning algorithms from natural proofs
• Reliable agnostic learning
• A Lower Bound for Agnostically Learning Disjunctions
• Learning probabilistic termination proofs
• Agnostically Learning Halfspaces
• Agnostic learning of disjunctions on symmetric distributions
• Agnostic active learning
• Approximate resilience, monotonicity, and the complexity of agnostic learning

Cites work

• A satisfiability algorithm for \(\mathrm{AC}^0\)
• A theory of the learnable
• Agnostically Learning Halfspaces
• An efficient pseudo-random generator provably as secure as syndrome decoding
• An Improved LPN Algorithm
• Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
• Constant depth circuits, Fourier transform, and learnability
• Cryptography from learning parity with noise
• Efficient agnostic learning of neural networks with bounded fan-in
• Hardness vs randomness
• scientific article; zbMATH DE number 1024063 (Why is no real title available?)
• scientific article; zbMATH DE number 2081058 (Why is no real title available?)
• scientific article; zbMATH DE number 1559537 (Why is no real title available?)
• scientific article; zbMATH DE number 5485565 (Why is no real title available?)
• Improving exhaustive search implies superpolynomial lower bounds
• Learning algorithms from natural proofs
• Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
• Mining circuit lower bound proofs for meta-algorithms
• Natural proofs
• Noise-tolerant learning, the parity problem, and the statistical query model
• On lattices, learning with errors, random linear codes, and cryptography
• On the power of membership queries in agnostic learning
• On the sample complexity of weak learning
• Some optimal inapproximability results
• Toward efficient agnostic learning
• Uniform-Distribution Learnability of Noisy Linear Threshold Functions with Restricted Focus of Attention

Cited in

(6)

• Proofs of Work from worst-case assumptions
• On the power of membership queries in agnostic learning
• Agnostic Learning in Permutation-Invariant Domains
• Learning algorithms from natural proofs
• On the complexity of compressing obfuscation
• SAT reduces to the minimum circuit size problem with a random oracle

This page was built for publication: Agnostic Learning from Tolerant Natural Proofs

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