Cryptographic limitations on learning Boolean formulae and finite automata
From MaRDI portal
Publication:4299296
DOI10.1145/174644.174647zbMATH Open0807.68073DBLPjournals/jacm/KearnsV94OpenAlexW2142399242WikidataQ90312317 ScholiaQ90312317MaRDI QIDQ4299296FDOQ4299296
Authors: Michael Kearns, Leslie G. Valiant 
Publication date: 1 March 1995
Published in: Journal of the ACM (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1145/174644.174647
Recommendations
Learning and adaptive systems in artificial intelligence (68T05) Data encryption (aspects in computer science) (68P25)
Cited In (81)
- Optimal quantum sample complexity of learning algorithms
- Learning fallible deterministic finite automata
- Approximate learning of limit-average automata
- Learnability of quantified formulas.
- Hybrid classification algorithms based on boosting and support vector machines
- Structural results about exact learning with unspecified attribute values
- The learnability of description logics with equality constraints
- Arcing classifiers. (With discussion)
- A time-series modeling method based on the boosting gradient-descent theory
- Learning a circuit by injecting values
- Learning a Random DFA from Uniform Strings and State Information
- Submodular functions: learnability, structure, and optimization
- Learning infinite-word automata with loop-index queries
- Classic learning
- Optimally learning social networks with activations and suppressions
- Learning large-alphabet and analog circuits with value injection queries
- Testing \(k\)-monotonicity
- Theoretical foundations and experimental results for a hierarchical classifier with overlapping clusters
- The unbounded-error communication complexity of symmetric functions
- Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution
- Order-revealing encryption and the hardness of private learning
- Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\)
- Partial Occam's Razor and its applications
- A complete characterization of statistical query learning with applications to evolvability
- Learning invariant features using inertial priors
- On the complexity of small description and related topics
- Probabilistic learnability of context-free grammars with basic distributional properties from positive examples
- Regular inference as vertex coloring
- Learning weighted automata
- Boosting in the presence of noise
- Learning commutative deterministic finite state automata in polynomial time
- On the boosting ability of top-down decision tree learning algorithms
- Learning with unreliable boundary queries
- Toward efficient agnostic learning
- A \(\mathbb R\)eal generalization of discrete AdaBoost
- Cryptographic hardness of random local functions. Survey
- Some connections between learning and optimization
- Cryptographic limitations on polynomial-time posteriori query learning
- Optimal cryptographic hardness of learning monotone functions
- Learning deterministic context free grammars: the Omphalos competition
- Structural analysis of polynomial-time query learnability
- Hardness results for neural network approximation problems
- The query complexity of learning DFA
- Quantum machine learning: a classical perspective
- Synthesizers and their application to the parallel construction of pseudo-random functions
- A multi-parameter analysis of hard problems on deterministic finite automata
- Minimizing nfa's and regular expressions
- Title not available (Why is that?)
- Diameter and stationary distribution of random \(r\)-out digraphs
- The complexity of properly learning simple concept classes
- Boosting algorithms: regularization, prediction and model fitting
- Explaining AI decisions using efficient methods for learning sparse Boolean formulae
- On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
- Learnability of solutions to conjunctive queries
- Efficient learning algorithms yield circuit lower bounds
- On the difficulty of approximately maximizing agreements.
- Simple learning algorithms using divide and conquer
- Neural networks and complexity theory
- Pac-learning non-recursive Prolog clauses
- Efficient learning of typical finite automata from random walks
- Weighted automata are compact and actively learnable
- Theory revision with queries: Horn, read-once, and parity formulas
- The complexity of learning concept classes with polynomial general dimension
- Computational sample complexity and attribute-efficient learning
- Cryptographic hardness for learning intersections of halfspaces
- PCPs and the hardness of generating synthetic data
- On the influence of the variable ordering for algorithmic learning using OBDDs
- Prediction-hardness of acyclic conjunctive queries
- Learning theory and epistemology
- Restricted distribution automatizability in PAC-semantics
- Interactive clustering of linear classes and cryptographic lower bounds
- Title not available (Why is that?)
- Modelling additive extremile regression by iteratively penalized least asymmetric weighted squares and gradient descent boosting
- Quantum hardness of learning shallow classical circuits
- CORES: fusion of supervised and unsupervised training methods for a multi-class classification problem
- The power of random counterexamples
- A moment-matching approach to testable learning and a new characterization of Rademacher complexity
- An algorithm for learning representations of models with scarce data
- Optimal Cryptographic Hardness of Learning Monotone Functions
- Exact learning algorithms, betting games, and circuit lower bounds
- Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions
This page was built for publication: Cryptographic limitations on learning Boolean formulae and finite automata
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4299296)
