The complexity of properly learning simple concept classes (Q2462500): Difference between revisions

@@ Property / full work available at URL @@
+https://doi.org/10.1016/j.jcss.2007.04.011
+Normal rank
@@ Property / OpenAlex ID @@
+W1990948892
@@ Property / OpenAlex ID: W1990948892 / rank @@
+Normal rank
@@ Property / cites work @@
+Resolution Is Not Automatizable Unless W[P] Is Tractable
+Normal rank
@@ Property / cites work @@
+Occam's razor
@@ Property / cites work: Occam's razor / rank @@
+Normal rank
@@ Property / cites work @@
+Q4542576
@@ Property / cites work: Q4542576 / rank @@
+Normal rank
@@ Property / cites work @@
+Lower bounds for cutting planes proofs with small coefficients
+Normal rank
@@ Property / cites work @@
+A subexponential exact learning algorithm for DNF using equivalence queries
+Normal rank
@@ Property / cites work @@
+Short proofs are narrow—resolution made simple
@@ Property / cites work: Short proofs are narrow—resolution made simple / rank @@
+Normal rank
@@ Property / cites work @@
+Q4228469
@@ Property / cites work: Q4228469 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4393480
@@ Property / cites work: Q4393480 / rank @@
+Normal rank
@@ Property / cites work @@
+The hardness of 3-uniform hypergraph coloring
@@ Property / cites work: The hardness of 3-uniform hypergraph coloring / rank @@
+Normal rank
@@ Property / cites work @@
+Randomized graph products, chromatic numbers, and Lovasz j-function
+Normal rank
@@ Property / cites work @@
+Complexity of automaton identification from given data
+Normal rank
@@ Property / cites work @@
+Lower bounds on learning decision lists and trees
@@ Property / cites work: Lower bounds on learning decision lists and trees / rank @@
+Normal rank
@@ Property / cites work @@
+Exact learning of DNF formulas using DNF hypotheses
+Normal rank
@@ Property / cites work @@
+Learnability beyond AC             <sup>0</sup>
@@ Property / cites work: Learnability beyond AC <sup>0</sup> / rank @@
+Normal rank
@@ Property / cites work @@
+Cryptographic hardness of distribution-specific learning
+Normal rank
@@ Property / cites work @@
+Learning DNF in time
@@ Property / cites work: Learning DNF in time / rank @@
+Normal rank
@@ Property / cites work @@
+Cryptographic limitations on learning Boolean formulae and finite automata
+Normal rank
@@ Property / cites work @@
+Learning juntas
@@ Property / cites work: Learning juntas / rank @@
+Normal rank
@@ Property / cites work @@
+Q4249529
@@ Property / cites work: Q4249529 / rank @@
+Normal rank
@@ Property / cites work @@
+Computational limitations on learning from examples
+Normal rank
@@ Property / cites work @@
+A theory of the learnable
@@ Property / cites work: A theory of the learnable / rank @@
+Normal rank