scientific article; zbMATH DE number 7064047

zbMath1489.68114MaRDI QIDQ5381121

Hubie Chen, Matthew A. Valeriote

Publication date: 7 June 2019

Full work available at URL: http://jmlr.csail.mit.edu/papers/v20/17-734.html

Title: zbMATH Open Web Interface contents unavailable due to conflicting licenses.

zbMATH Keywords

computational learning theoryreductionsconcept learninguniversal algebradichotomy theorems

Mathematics Subject Classification ID

Computational learning theory (68Q32) Applications of universal algebra in computer science (08A70)

Related Items

On the non-efficient PAC learnability of conjunctive queries, Unnamed Item

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A strong Mal'cev condition for locally finite varieties omitting the unary type
• On the expression complexity of equivalence and isomorphism of primitive positive formulas
• Prediction-preserving reducibility
• Existence theorems for weakly symmetric operations
• The complexity of satisfiability problems: Refining Schaefer's theorem
• Learning conjunctions of Horn clauses
• On the algebraic structure of combinatorial problems
• Size-depth tradeoffs for Boolean formulae
• Learnability of quantified formulas.
• Finitely related algebras in congruence modular varieties have few subpowers
• Exploring learnability between exact and PAC
• Learning closed Horn expressions
• When won't membership queries help?
• Generic expression hardness results for primitive positive formula comparison
• A dichotomy theorem for learning quantified Boolean formulas
• Queries and concept learning
• Learning intersection-closed classes with signatures
• Optimal strong Mal'cev conditions for omitting type 1 in locally finite varieties.
• Complexity Classifications of Boolean Constraint Satisfaction Problems
• Exact Learning from Membership Queries: Some Techniques, Results and New Directions
• Meditations on Quantified Constraint Satisfaction
• Constraint Satisfaction Problems Solvable by Local Consistency Methods
• Varieties with few subalgebras of powers
• ON THE COMPLEXITY OF SOME MALTSEV CONDITIONS
• The structure of finite algebras
• Varieties Obeying Homotopy Laws
• The Computational Structure of Monotone Monadic SNP and Constraint Satisfaction: A Study through Datalog and Group Theory
• Cryptographic limitations on learning Boolean formulae and finite automata
• Asking the Metaquestions in Constraint Tractability
• Classifying the Complexity of Constraints Using Finite Algebras
• An Algebraic Characterization of Testable Boolean CSPs
• Tractability and Learnability Arising from Algebras with Few Subpowers
• The complexity of the counting constraint satisfaction problem
• The complexity of satisfiability problems