Learning algorithms from natural proofs

DOI10.4230/LIPICS.CCC.2016.10zbMATH Open1380.68242OpenAlexW2465968014MaRDI QIDQ5368744FDOQ5368744

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

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

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)

Cited In (42)

• Title not available (Why is that?)
• Expander-Based Cryptography Meets Natural Proofs
• Learning \(\mathrm{AC}^0\) under \(k\)-dependent distributions
• Title not available (Why is that?)
• 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
• Learning Large-Alphabet and Analog Circuits with Value Injection Queries
• Title not available (Why is that?)
• Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\)
• 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
• The power of natural properties as oracles
• Learning and lower bounds for AC\(^{0}\) with threshold gates
• One-tape Turing machine and branching program lower bounds for MCSP
• Title not available (Why is that?)
• 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
• A direct PRF construction from Kolmogorov complexity
• Proofs of Work from worst-case assumptions
• Circuit lower bounds from learning-theoretic approaches
• Vaughan Jones, Kolmogorov Complexity, and the New Complexity Landscape around Circuit Minimization
• Title not available (Why is that?)
• Constant depth formula and partial function versions of MCSP are hard
• What circuit classes can be learned with non-trivial savings?
• Title not available (Why is that?)
• Hardness magnification near state-of-the-art lower bounds
• PAC learning depth-3 \(\mathrm{AC}^0\) circuits of bounded top fanin
• Title not available (Why is that?)
• Efficient learning algorithms yield circuit lower bounds
• Title not available (Why is that?)
• 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)