Efficient learning algorithms yield circuit lower bounds

DOI10.1016/J.JCSS.2008.07.006MaRDI QIDQ2517822zbMATH OpenOpenAlexFDO

Authors Adam R. Klivans, Lance Fortnow

Publication date 9 January 2009

Published in Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/j.jcss.2008.07.006

zbMATH Keywords

circuit lower boundscomputational complexitycomputational learning theoryexact learninghardness of learningPAC learning

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05) Nonnumerical algorithms (68W05)

Recommendations

• Efficient Learning Algorithms Yield Circuit Lower Bounds
• Exact learning algorithms, betting games, and circuit lower bounds
• Circuit lower bounds from learning-theoretic approaches
• Learning algorithms from natural proofs
• On learning, lower bounds and (un)keeping promises

Cites work

• BPP has subexponential time simulations unless EXPTIME has publishable proofs
• A theory of the learnable
• Circuit lower bounds for Merlin-Arthur classes
• Circuit-size lower bounds and non-reducibility to sparse sets
• Complexity of automaton identification from given data
• Computational limitations on learning from examples
• Computing and Combinatorics
• Constant depth circuits, Fourier transform, and learnability
• Cryptographic hardness for learning intersections of halfspaces
• Cryptographic hardness of distribution-specific learning
• Cryptographic limitations on learning Boolean formulae and finite automata
• Derandomizing polynomial identity tests means proving circuit lower bounds
• scientific article; zbMATH DE number 4191094 (Why is no real title available?)
• scientific article; zbMATH DE number 4213418 (Why is no real title available?)
• scientific article; zbMATH DE number 1318518 (Why is no real title available?)
• scientific article; zbMATH DE number 1335875 (Why is no real title available?)
• scientific article; zbMATH DE number 1405686 (Why is no real title available?)
• scientific article; zbMATH DE number 5485587 (Why is no real title available?)
• Learning arithmetic circuits via partial derivatives.
• Learning Arithmetic Read-Once Formulas
• On interpolating arithmetic read-once formulas with exponentiation
• On learning width two branching programs
• On pseudorandomness and resource-bounded measure
• On the Computational Complexity of Algorithms
• Online Learning and Resource‐Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets
• PP is as Hard as the Polynomial-Time Hierarchy
• Queries and concept learning
• Randomness vs time: Derandomization under a uniform assumption
• Resource-bounded measure and learnability
• Structural analysis of polynomial-time query learnability
• The complexity of computing the permanent

Cited in

(21)

• \(\mathrm{AC}^{0}\circ \mathrm{MOD}_{2}\) lower bounds for the Boolean inner product
• PAC-learning gains of Turing machines over circuits and neural networks
• Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
• A lower bound on the competitivity of memoryless algorithms for a generalization of the CNN problem
• Circuit lower bounds from learning-theoretic approaches
• scientific article; zbMATH DE number 5899249 (Why is no real title available?)
• Towards hardness of approximation for polynomial time problems
• Conspiracies between learning algorithms, circuit lower bounds, and pseudorandomness
• scientific article; zbMATH DE number 7250147 (Why is no real title available?)
• Amplification and Derandomization without Slowdown
• Circuit lower bounds for nondeterministic quasi-polytime from a new easy witness lemma
• On learning, lower bounds and (un)keeping promises
• Efficient Learning Algorithms Yield Circuit Lower Bounds
• Learning algorithms from natural proofs
• Learning a circuit by injecting values
• Exact learning algorithms, betting games, and circuit lower bounds
• Exact learning algorithms, betting games, and circuit lower bounds
• The power of natural properties as oracles
• Reconstruction of depth-4 multilinear circuits
• On the structure of learnability beyond \textsf{P/poly}
• On exponential-time hypotheses, derandomization, and circuit lower bounds

This page was built for publication: Efficient learning algorithms yield circuit lower bounds

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