Cryptographic limitations on learning Boolean formulae and finite automata
From MaRDI portal
Publication:4299296
DOI10.1145/174644.174647zbMath0807.68073OpenAlexW2142399242WikidataQ90312317 ScholiaQ90312317MaRDI QIDQ4299296
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
Learning and adaptive systems in artificial intelligence (68T05) Data encryption (aspects in computer science) (68P25)
Related Items
Learning infinite-word automata with loop-index queries, The query complexity of learning DFA, Some connections between learning and optimization, Toward efficient agnostic learning, The learnability of description logics with equality constraints, Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2\)], Simple learning algorithms using divide and conquer, Learning deterministic context free grammars: the Omphalos competition, Learning fallible deterministic finite automata, Minimizing nfa's and regular expressions, Cryptographic hardness of random local functions. Survey, Quantum machine learning: a classical perspective, Submodular Functions: Learnability, Structure, and Optimization, Efficient learning of typical finite automata from random walks, Learning invariant features using inertial priors, Structural analysis of polynomial-time query learnability, Partial Occam's Razor and its applications, Learning Weighted Automata, Neural networks and complexity theory, On the complexity of small description and related topics, A time-series modeling method based on the boosting gradient-descent theory, On the difficulty of approximately maximizing agreements., Unnamed Item, The unbounded-error communication complexity of symmetric functions, Learning Theory and Epistemology, A complete characterization of statistical query learning with applications to evolvability, PCPs and the hardness of generating synthetic data, Boosting algorithms: regularization, prediction and model fitting, Learnability of quantified formulas., Regular inference as vertex coloring, The complexity of properly learning simple concept classes, Classic learning, A multi-parameter analysis of hard problems on deterministic finite automata, Optimally learning social networks with activations and suppressions, Unnamed Item, Unnamed Item, CORES: fusion of supervised and unsupervised training methods for a multi-class classification problem, Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions, Weighted automata are compact and actively learnable, Order-Revealing Encryption and the Hardness of Private Learning, Pac-learning non-recursive Prolog clauses, Probabilistic learnability of context-free grammars with basic distributional properties from positive examples, Computational sample complexity and attribute-efficient learning, The power of random counterexamples, Cryptographic hardness for learning intersections of halfspaces, Efficient learning algorithms yield circuit lower bounds, Exact Learning Algorithms, Betting Games, and Circuit Lower Bounds, Learning large-alphabet and analog circuits with value injection queries, Arcing classifiers. (With discussion), Learning commutative deterministic finite state automata in polynomial time, Unnamed Item, Learning a circuit by injecting values, Learning with unreliable boundary queries, Hybrid classification algorithms based on boosting and support vector machines, Boosting in the presence of noise, On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems, A \(\mathbb R\)eal generalization of discrete AdaBoost, Structural results about exact learning with unspecified attribute values, Learning a Random DFA from Uniform Strings and State Information, Interactive Clustering of Linear Classes and Cryptographic Lower Bounds, Unnamed Item, Synthesizers and their application to the parallel construction of pseudo-random functions, Quantum Hardness of Learning Shallow Classical Circuits, Diameter and stationary distribution of random \(r\)-out digraphs, Explaining AI decisions using efficient methods for learning sparse Boolean formulae, On the influence of the variable ordering for algorithmic learning using OBDDs, THEORETICAL FOUNDATIONS AND EXPERIMENTAL RESULTS FOR A HIERARCHICAL CLASSIFIER WITH OVERLAPPING CLUSTERS, On the boosting ability of top-down decision tree learning algorithms, Prediction-hardness of acyclic conjunctive queries, Unnamed Item, Hardness results for neural network approximation problems, Theory revision with queries: Horn, read-once, and parity formulas, The complexity of learning concept classes with polynomial general dimension
