Hardness of approximate two-level logic minimization and PAC learning with membership queries (Q5920702): Difference between revisions

@@ Property / cites work @@
+The complexity of properly learning simple concept classes
+Normal rank
@@ Property / cites work @@
+Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
+Normal rank
@@ Property / cites work @@
+When won't membership queries help?
@@ Property / cites work: When won't membership queries help? / rank @@
+Normal rank
@@ Property / cites work @@
+Efficient probabilistically checkable proofs and applications to approximations
+Normal rank
@@ Property / cites work @@
+Fast learning of \(k\)-term DNF formulas with queries.
+Normal rank
@@ Property / cites work @@
+A Greedy Heuristic for the Set-Covering Problem
@@ Property / cites work: A Greedy Heuristic for the Set-Covering Problem / rank @@
+Normal rank
@@ Property / cites work @@
+A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
+Normal rank
@@ Property / cites work @@
+Families of finite sets in which no set is covered by the union of \(r\) others
+Normal rank
@@ Property / cites work @@
+A threshold of ln             <i>n</i>             for approximating set cover
+Normal rank
@@ Property / cites work @@
+Zero knowledge and the chromatic number
@@ Property / cites work: Zero knowledge and the chromatic number / rank @@
+Normal rank
@@ Property / cites work @@
+A Learning Network Using Adaptive Threshold Elements
+Normal rank
@@ Property / cites work @@
+Complexity of automaton identification from given data
+Normal rank
@@ Property / cites work @@
+Exact learning of DNF formulas using DNF hypotheses
+Normal rank
@@ Property / cites work @@
+An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
+Normal rank
@@ Property / cites work @@
+Nonrandom binary superimposed codes
@@ Property / cites work: Nonrandom binary superimposed codes / rank @@
+Normal rank
@@ Property / cites work @@
+Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
+Normal rank
@@ Property / cites work @@
+On the hardness of approximating minimization problems
+Normal rank
@@ Property / cites work @@
+Hardness vs randomness
@@ Property / cites work: Hardness vs randomness / rank @@
+Normal rank
@@ Property / cites work @@
+Q4249529
@@ Property / cites work: Q4249529 / rank @@
+Normal rank
@@ Property / cites work @@
+Boolesche Minimalpolynome und Überdeckungsprobleme
+Normal rank
@@ Property / cites work @@
+Computational limitations on learning from examples
+Normal rank
@@ Property / cites work @@
+The Problem of Simplifying Truth Functions
@@ Property / cites work: The Problem of Simplifying Truth Functions / rank @@
+Normal rank
@@ Property / cites work @@
+A Way to Simplify Truth Functions
@@ Property / cites work: A Way to Simplify Truth Functions / rank @@
+Normal rank
@@ Property / cites work @@
+Q4527015
@@ Property / cites work: Q4527015 / rank @@
+Normal rank
@@ Property / cites work @@
+A note on PCP vs. MIP
@@ Property / cites work: A note on PCP vs. MIP / rank @@
+Normal rank
@@ Property / cites work @@
+Non-approximability results for optimization problems on bounded degree instances
+Normal rank
@@ Property / cites work @@
+A theory of the learnable
@@ Property / cites work: A theory of the learnable / rank @@
+Normal rank