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 (73)
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
This page was built for publication: Cryptographic limitations on learning Boolean formulae and finite automata
