Agnostic Learning from Tolerant Natural Proofs
From MaRDI portal
Publication:5002638
DOI10.4230/LIPIcs.APPROX-RANDOM.2017.35zbMath1467.68076OpenAlexW2753176613MaRDI QIDQ5002638
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
Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Networks and circuits as models of computation; circuit complexity (68Q06)
Related Items
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Lower bounds on the size of bounded depth circuits over a complete basis with logical addition
- Hardness vs randomness
- Toward efficient agnostic learning
- On the sample complexity of weak learning
- Mining circuit lower bound proofs for meta-algorithms
- Improving exhaustive search implies superpolynomial lower bounds
- An Efficient Pseudo-Random Generator Provably as Secure as Syndrome Decoding
- Cryptography from Learning Parity with Noise
- Constant depth circuits, Fourier transform, and learnability
- An Improved LPN Algorithm
- Agnostically Learning Halfspaces
- A theory of the learnable
- Efficient agnostic learning of neural networks with bounded fan-in
- Uniform-Distribution Learnability of Noisy Linear Threshold Functions with Restricted Focus of Attention
- Learning algorithms from natural proofs
- Some optimal inapproximability results
- Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques
- On lattices, learning with errors, random linear codes, and cryptography
- Noise-tolerant learning, the parity problem, and the statistical query model
- Natural proofs
