Fast learning of \(k\)-term DNF formulas with queries.

DOI10.1006/jcss.1995.1075zbMath1294.68095OpenAlexW3203591206MaRDI QIDQ960515

Steven Rudich, Avrim L. Blum

Publication date: 21 December 2008

Published in: Journal of Computer and System Sciences (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1006/jcss.1995.1075

zbMATH Keywords

exact learning algorithm

Mathematics Subject Classification ID

Computational learning theory (68Q32)

Related Items (18)

Efficient multiple constraint acquisition ⋮ Learning nearly monotone \(k\)-term DNF ⋮ Learning DNF in time \(2^{\widetilde O(n^{1/3})}\) ⋮ Exact learning from an honest teacher that answers membership queries ⋮ Simple learning algorithms using divide and conquer ⋮ An efficient membership-query algorithm for learning DNF with respect to the uniform distribution ⋮ Parameterized Learnability of k-Juntas and Related Problems ⋮ \(P\)-sufficient statistics for PAC learning \(k\)-term-DNF formulas through enumeration ⋮ On the limits of proper learnability of subclasses of DNF formulas ⋮ Constraint acquisition ⋮ Learning orthogonal F-Horn formulas ⋮ Exact learning of DNF formulas using DNF hypotheses ⋮ Hardness of approximate two-level logic minimization and PAC learning with membership queries ⋮ Parameterized learnability of juntas ⋮ The query complexity of finding local minima in the lattice ⋮ Efficient dualization of \(O(\log n\))-term monotone disjunctive normal forms ⋮ On using the Fourier transform to learn disjoint DNF ⋮ Theory revision with queries: Horn, read-once, and parity formulas

This page was built for publication: Fast learning of \(k\)-term DNF formulas with queries.