Cryptographic limitations on learning Boolean formulae and finite automata
From MaRDI portal
Publication:4299296
Recommendations
Cited in
(81)- 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
- Optimal quantum sample complexity of learning algorithms
- Learning fallible deterministic finite automata
- Learnability of quantified formulas.
- Hybrid classification algorithms based on boosting and support vector machines
- Approximate learning of limit-average automata
- The learnability of description logics with equality constraints
- Structural results about exact learning with unspecified attribute values
- Prediction-hardness of acyclic conjunctive queries
- Arcing classifiers. (With discussion)
- A time-series modeling method based on the boosting gradient-descent theory
- Learning a circuit by injecting values
- Classic learning
- Learning a Random DFA from Uniform Strings and State Information
- Optimally learning social networks with activations and suppressions
- Learning infinite-word automata with loop-index queries
- Learning large-alphabet and analog circuits with value injection queries
- Submodular functions: learnability, structure, and optimization
- Theoretical foundations and experimental results for a hierarchical classifier with overlapping clusters
- Testing \(k\)-monotonicity
- The unbounded-error communication complexity of symmetric functions
- Cryptographic lower bounds for learnability of Boolean functions on the uniform distribution
- Low-complexity weak pseudorandom functions in \(\mathtt{AC}0[\mathtt{MOD}2]\)
- Order-revealing encryption and the hardness of private learning
- Partial Occam's Razor and its applications
- A complete characterization of statistical query learning with applications to evolvability
- Learning theory and epistemology
- Learning invariant features using inertial priors
- Restricted distribution automatizability in PAC-semantics
- Interactive clustering of linear classes and cryptographic lower bounds
- On the complexity of small description and related topics
- scientific article; zbMATH DE number 7561484 (Why is no real title available?)
- Regular inference as vertex coloring
- Probabilistic learnability of context-free grammars with basic distributional properties from positive examples
- Learning commutative deterministic finite state automata in polynomial time
- Modelling additive extremile regression by iteratively penalized least asymmetric weighted squares and gradient descent boosting
- Learning weighted automata
- Quantum hardness of learning shallow classical circuits
- On the boosting ability of top-down decision tree learning algorithms
- Boosting in the presence of noise
- 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
- CORES: fusion of supervised and unsupervised training methods for a multi-class classification problem
- Learning deterministic context free grammars: the Omphalos competition
- The query complexity of learning DFA
- Hardness results for neural network approximation problems
- Synthesizers and their application to the parallel construction of pseudo-random functions
- Structural analysis of polynomial-time query learnability
- Quantum machine learning: a classical perspective
- A multi-parameter analysis of hard problems on deterministic finite automata
- Minimizing nfa's and regular expressions
- The power of random counterexamples
- Diameter and stationary distribution of random \(r\)-out digraphs
- scientific article; zbMATH DE number 7561750 (Why is no real title available?)
- Boosting algorithms: regularization, prediction and model fitting
- The complexity of properly learning simple concept classes
- On the approximability of minimizing nonzero variables or unsatisfied relations in linear systems
- A moment-matching approach to testable learning and a new characterization of Rademacher complexity
- Explaining AI decisions using efficient methods for learning sparse Boolean formulae
- Learnability of solutions to conjunctive queries
- An algorithm for learning representations of models with scarce data
- Efficient learning algorithms yield circuit lower bounds
- Optimal Cryptographic Hardness of Learning Monotone Functions
- On the difficulty of approximately maximizing agreements.
- Exact learning algorithms, betting games, and circuit lower bounds
- Simple learning algorithms using divide and conquer
- Neural networks and complexity theory
- Cryptographic limitations on parallelizing membership and equivalence queries with applications to random-self-reductions
- Efficient learning of typical finite automata from random walks
- Theory revision with queries: Horn, read-once, and parity formulas
- The complexity of learning concept classes with polynomial general dimension
- Pac-learning non-recursive Prolog clauses
- Weighted automata are compact and actively learnable
- Computational sample complexity and attribute-efficient learning
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)
