A theory of the learnable

DOI10.1145/1968.1972zbMath0587.68077OpenAlexW4238893454WikidataQ29398622 ScholiaQ29398622MaRDI QIDQ3714486

Leslie G. Valiant

Publication date: 1984

Published in: Unnamed Author (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/1968.1972

zbMATH Keywords

learninginformation gatheringknowledge acquisition in the absence of explicit programming

Mathematics Subject Classification ID

Learning and adaptive systems in artificial intelligence (68T05)

Related Items (only showing first 100 items - show all)

DNA sequencing and string learning ⋮ Learning to Recognize Three-Dimensional Objects ⋮ Sample Complexity Bounds on Differentially Private Learning via Communication Complexity ⋮ Fast Pseudorandom Functions Based on Expander Graphs ⋮ The GGM Function Family Is a Weakly One-Way Family of Functions ⋮ Bloom Filters in Adversarial Environments ⋮ Efficient Pseudorandom Functions via On-the-Fly Adaptation ⋮ Boosting the partial least square algorithm for regression modelling ⋮ Reduction from Cost-Sensitive Ordinal Ranking to Weighted Binary Classification ⋮ An inductive inference approach to classification ⋮ A framework for polynomial-time query learnability ⋮ Structural analysis of polynomial-time query learnability ⋮ Learning Weighted Automata ⋮ Discriminative Reranking for Natural Language Parsing ⋮ Abductive learning of quantized stochastic processes with probabilistic finite automata ⋮ The learnability of quantum states ⋮ Learning reliably and with one-sided error ⋮ Efficiency in the Identification in the Limit Learning Paradigm ⋮ Learning Grammars and Automata with Queries ⋮ Learning Probability Distributions Generated by Finite-State Machines ⋮ Learning Tree Languages ⋮ Separating Models of Learning with Faulty Teachers ⋮ Parameterized Learnability of k-Juntas and Related Problems ⋮ Polynomial Time Algorithms for Learning k-Reversible Languages and Pattern Languages with Correction Queries ⋮ On Learning Regular Expressions and Patterns Via Membership and Correction Queries ⋮ Polynomial Time Probabilistic Learning of a Subclass of Linear Languages with Queries ⋮ Massive online teaching to bounded learners ⋮ Learning mixtures of spherical gaussians ⋮ Low-weight halfspaces for sparse boolean vectors ⋮ Learnability of DNF with representation-specific queries ⋮ Can theories be tested? ⋮ Making evolution rigorous ⋮ On the convergence of the Hegselmann-Krause system ⋮ Is privacy compatible with truthfulness? ⋮ Differentially private data analysis of social networks via restricted sensitivity ⋮ Characterizing the sample complexity of private learners ⋮ Barriers in cryptography with weak, correlated and leaky sources ⋮ On the possibilities and limitations of pseudodeterministic algorithms ⋮ Evasiveness through a circuit lens ⋮ The garden-hose model ⋮ Space-bounded communication complexity ⋮ Towards an optimal query efficient PCP? ⋮ A characterization of approximation resistance for even k-partite CSPs ⋮ On the optimality of semidefinite relaxations for average-case and generalized constraint satisfaction ⋮ On the power of many one-bit provers ⋮ Approaching utopia ⋮ Learning and incentives in user-generated content ⋮ Welfare maximization and the supermodular degree ⋮ Reachability in graph timelines ⋮ Runtime guarantees for regression problems ⋮ An energy complexity model for algorithms ⋮ Streaming computations with a loquacious prover ⋮ Adversary lower bound for the k-sum problem ⋮ Stronger methods of making quantum interactive proofs perfectly complete ⋮ Active self-assembly of algorithmic shapes and patterns in polylogarithmic time ⋮ An equational approach to secure multi-party computation ⋮ Publicly verifiable proofs of sequential work ⋮ On the power of nonuniformity in proofs of security ⋮ Fast reductions from RAMs to delegatable succinct constraint satisfaction problems ⋮ Resource-based corruptions and the combinatorics of hidden diversity ⋮ Time hierarchies for sampling distributions ⋮ Properties and applications of boolean function composition ⋮ Pseudo-partitions, transversality and locality ⋮ Competing provers protocols for circuit evaluation ⋮ Catch them if you can ⋮ Instance-sensitive robustness guarantees for sequencing with unknown packing and covering constraints ⋮ Robust optimization in the presence of uncertainty ⋮ Sorting noisy data with partial information ⋮ New affine-invariant codes from lifting ⋮ H-wise independence ⋮ Sparse extractor families for all the entropy ⋮ On the power of conditional samples in distribution testing ⋮ Natural Language Processing, Moving from Rules to Data ⋮ Learning $$AC^0$$ Under k-Dependent Distributions ⋮ Inductive inference of context-free languages based on context-free expressions ⋮ On the relationship between diagnostic and checking tests of the read-once functions ⋮ On learning monotone Boolean functions with irrelevant variables ⋮ On the Complexity of Computing and Learning with Multiplicative Neural Networks ⋮ On some recent advances on high dimensional Bayesian statistics ⋮ Precise induction from statistical data ⋮ The functions of finite support: a canonical learning problem ⋮ Order-Revealing Encryption and the Hardness of Private Learning ⋮ On the Nonlearnability of a Single Spiking Neuron ⋮ Optimal Bounds on Approximation of Submodular and XOS Functions by Juntas ⋮ On memoryless provers and insincere verifiers ⋮ Hybrid classification algorithms based on boosting and support vector machines ⋮ Learning Hurdles for Sleeping Experts ⋮ On Statistically Secure Obfuscation with Approximate Correctness ⋮ Random Graphs In A Neural Computation Model ⋮ Computing the Expected Edit Distance from a String to a PFA ⋮ Labeled Compression Schemes for Extremal Classes ⋮ On the Evolution of Monotone Conjunctions: Drilling for Best Approximations ⋮ An Algebraic Perspective on Boolean Function Learning ⋮ Agnostic Clustering ⋮ Learning a Random DFA from Uniform Strings and State Information ⋮ Interactive Clustering of Linear Classes and Cryptographic Lower Bounds ⋮ Bounds on the Sample Complexity for Private Learning and Private Data Release ⋮ BOOSTING-BASED FRAMEWORK FOR PORTFOLIO STRATEGY DISCOVERY AND OPTIMIZATION ⋮ SIMILARITY-BASED COMBINATION OF MULTIPLE CLUSTERINGS ⋮ An inductive method with genetic algorithm for learning phrase-structure-rule of natural language

This page was built for publication: A theory of the learnable