Learning algorithms from natural proofs

DOI10.4230/LIPICS.CCC.2016.10MaRDI QIDQ5368744zbMATH OpenOpenAlexFDO

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

Publication date 10 October 2017

Full work available at URL https://doi.org/10.4230/lipics.ccc.2016.10

zbMATH Keywords

learninglower boundscompressioncircuit complexitynatural proofs

Mathematics Subject Classification ID

Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Complexity classes (hierarchies, relations among complexity classes, etc.) (68Q15)

Recommendations

• Agnostic Learning from Tolerant Natural Proofs
• Efficient learning algorithms yield circuit lower bounds
• Efficient Learning Algorithms Yield Circuit Lower Bounds
• Pseudorandom generators and learning algorithms for \(\mathrm{AC}^ 0\)
• Exact learning algorithms, betting games, and circuit lower bounds

Cited in

(42)

• scientific article; zbMATH DE number 7250147 (Why is no real title available?)
• Expander-Based Cryptography Meets Natural Proofs
• Learning \(\mathrm{AC}^0\) under \(k\)-dependent distributions
• scientific article; zbMATH DE number 7561759 (Why is no real title available?)
• 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
• Feasibly constructive proofs of succinct weak circuit lower bounds
• Expander-based cryptography meets natural proofs
• Learning large-alphabet and analog circuits with value injection queries
• Exploring crypto dark matter: new simple PRF candidates and their applications
• Agnostic Learning from Tolerant Natural Proofs
• Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\)
• scientific article; zbMATH DE number 7561748 (Why is no real title available?)
• Learning Large-Alphabet and Analog Circuits with Value Injection Queries
• Certifying polynomials for \(\mathsf{AC}^0[\oplus]\) circuits, with applications to lower bounds and circuit compression
• On nonadaptive reductions to the set of random strings and its dense subsets
• On the complexity of compressing obfuscation
• Learning and lower bounds for AC\(^{0}\) with threshold gates
• The power of natural properties as oracles
• scientific article; zbMATH DE number 7758317 (Why is no real title available?)
• One-tape Turing machine and branching program lower bounds for MCSP
• Localizability of the approximation method
• Pseudorandom functions: three decades later
• Hardness magnification near state-of-the-art lower bounds
• Average-case linear matrix factorization and reconstruction of low width algebraic branching programs
• Proofs of Work from worst-case assumptions
• A direct PRF construction from Kolmogorov complexity
• Circuit lower bounds from learning-theoretic approaches
• Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
• scientific article; zbMATH DE number 7561750 (Why is no real title available?)
• Constant depth formula and partial function versions of MCSP are hard
• What circuit classes can be learned with non-trivial savings?
• scientific article; zbMATH DE number 7561559 (Why is no real title available?)
• Hardness magnification near state-of-the-art lower bounds
• PAC learning depth-3 \(\mathrm{AC}^0\) circuits of bounded top fanin
• scientific article; zbMATH DE number 7009617 (Why is no real title available?)
• Efficient learning algorithms yield circuit lower bounds
• scientific article; zbMATH DE number 7250145 (Why is no real title available?)
• Minimum circuit size, graph isomorphism, and related problems
• Minimum circuit size, graph isomorphism, and related problems
• Bounded depth circuits with weighted symmetric gates: satisfiability, lower bounds and compression

This page was built for publication: Learning algorithms from natural proofs

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