Hardness of approximate two-level logic minimization and PAC learning with membership queries
From MaRDI portal
Publication:5920702
DOI10.1016/j.jcss.2008.07.007zbMath1181.68192OpenAlexW2017271630MaRDI QIDQ5920702
Publication date: 9 January 2009
Published in: Journal of Computer and System Sciences (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.jcss.2008.07.007
Computational learning theory (68Q32) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)
Related Items (6)
The pervasive reach of resource-bounded Kolmogorov complexity in computational complexity theory ⋮ Learning random monotone DNF ⋮ PCPs and the hardness of generating synthetic data ⋮ Implementation of Boolean functions with a bounded number of zeros by disjunctive normal forms ⋮ Unnamed Item ⋮ Mining circuit lower bound proofs for meta-algorithms
Cites Work
- Unnamed Item
- Unnamed Item
- Fast learning of \(k\)-term DNF formulas with queries.
- Families of finite sets in which no set is covered by the union of \(r\) others
- Boolesche Minimalpolynome und Überdeckungsprobleme
- Zero knowledge and the chromatic number
- Hardness vs randomness
- A note on PCP vs. MIP
- An efficient membership-query algorithm for learning DNF with respect to the uniform distribution
- Learning DNF in time \(2^{\widetilde O(n^{1/3})}\)
- When won't membership queries help?
- The complexity of properly learning simple concept classes
- A threshold of ln n for approximating set cover
- A Way to Simplify Truth Functions
- Minimizing Disjunctive Normal Form Formulas and $AC^0$ Circuits Given a Truth Table
- A theory of the learnable
- Computational limitations on learning from examples
- A Greedy Heuristic for the Set-Covering Problem
- Complexity of automaton identification from given data
- On the hardness of approximating minimization problems
- Non-approximability results for optimization problems on bounded degree instances
- Efficient probabilistically checkable proofs and applications to approximations
- A New Multilayered PCP and the Hardness of Hypergraph Vertex Cover
- Nonrandom binary superimposed codes
- A Learning Network Using Adaptive Threshold Elements
- The Problem of Simplifying Truth Functions
- Exact learning of DNF formulas using DNF hypotheses
This page was built for publication: Hardness of approximate two-level logic minimization and PAC learning with membership queries
