Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness
DOI10.4230/LIPICS.CCC.2017.18zbMATH Open1440.68083arXiv1611.01190MaRDI QIDQ5111148FDOQ5111148
Authors: Igor C. Oliveira, Rahul Santhanam 
Publication date: 26 May 2020
Full work available at URL: https://arxiv.org/abs/1611.01190
Recommendations
- On learning, lower bounds and (un)keeping promises
- Exact learning algorithms, betting games, and circuit lower bounds
- Efficient learning algorithms yield circuit lower bounds
- Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution
- scientific article; zbMATH DE number 2080214
Computational learning theory (68Q32) Probability in computer science (algorithm analysis, random structures, phase transitions, etc.) (68Q87) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15) Networks and circuits as models of computation; circuit complexity (68Q06)
Cited In (24)
- Pseudo-derandomizing learning and approximation
- Non-Black-Box Worst-Case to Average-Case Reductions Within \(\mathsf{NP}\)
- Deterministically counting satisfying assignments for constant-depth circuits with parity gates, with implications for lower bounds
- Randomness and intractability in Kolmogorov complexity
- Ker-I Ko and the Study of Resource-Bounded Kolmogorov Complexity
- Algorithms and lower bounds for De Morgan formulas of low-communication leaf gates
- Title not available (Why is that?)
- The power of natural properties as oracles
- Circuit lower bounds for MCSP from local pseudorandom generators
- Quantum hardness of learning shallow classical circuits
- Circuit lower bounds from learning-theoretic approaches
- On learning, lower bounds and (un)keeping promises
- Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
- Title not available (Why is that?)
- The non-hardness of approximating circuit size
- Title not available (Why is that?)
- Hardness magnification near state-of-the-art lower bounds
- On the structure of learnability beyond P/poly
- Exact learning algorithms, betting games, and circuit lower bounds
- Title not available (Why is that?)
- Title not available (Why is that?)
- Minimum circuit size, graph isomorphism, and related problems
- Minimum circuit size, graph isomorphism, and related problems
- Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
This page was built for publication: Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5111148)
