A Subexponential Exact Learning Algorithm for DNF Using Equivalence Queries

No abstract is available for this paper.

• Publication year

  1996

• Venue

  Information Processing Letters

• Publication date

  1996-07-08

• Fields of study

  Mathematics, Computer Science

• Identifiers
  DOI 10.1016/0020-0190(96)00077-4
• External record

  Open on Semantic Scholar

• Source metadata

  Semantic Scholar

• No claims are published for this paper.

• No concepts are published for this paper.

• Oracles and queries that are sufficient for exact learning (extended abstract)

  1994cited by this paper
• Oracles and Queries That Are Suucient for Exact Learning

  1994cited by this paper
• Rank-r Decision Trees are a Subclass of r-Decision Lists

  1992cited by this paper
• Learning Nested Differences of Intersection-Closed Concept Classes

  1989cited by this paper
• Learning Quickly When Irrelevant Attributes Abound: A New Linear-Threshold Algorithm

  1987cited by this paper
• A theory of the learnable

  1984cited by this paper
• A theory of the learnable

  1984cited by this paper

• The Probably Approximately Correct Learning Model in Computational Learning Theory

  2025cites this paper
• Faster Exact Learning of k-Term DNFs with Membership and Equivalence Queries

  2025cites this paper
• DNF Learning via Locally Mixing Random Walks

  2025cites this paper
• Iterative Rule Extension for Logic Analysis of Data: An MILP-Based Heuristic to Derive Interpretable Binary Classifiers from Large Data Sets

  2024cites this paper
• Polynomial Calculus for Quantified Boolean Logic: Lower Bounds through Circuits and Degree

  2024cites this paper
• Computational Learning Theory & Fourier Analysis

  2022cites this paper
• Hardness Characterisations and Size-width Lower Bounds for QBF Resolution

  2022cites this paper
• Iterative Rule Extension for Logic Analysis of Data: an MILP-based heuristic to derive interpretable binary classification from large datasets

  2021cites this paper
• Power of Decision Trees with Monotone Queries

  2020cites this paper
• Shrinkage of Decision Lists and DNF Formulas

  2020cites this paper
• Hardness Characterisations and Size-Width Lower Bounds for QBF Resolution

  2020influential citation
• Hardness of learning DNFs using halfspaces

  2019cites this paper
• Learning SMaLL Predictors

  2018cites this paper
• The Sign-Rank of AC0

  2010cites this paper
• k + Decision Trees - (Extended Abstract)

  2010cites this paper
• Solving linear constraints over real and rational fields

  2010cites this paper
• Optimal bounds for sign-representing the intersection of two halfspaces by polynomials

  2009cites this paper
• Lower bounds in communication complexity and learning theory via analytic methods

  2009cites this paper
• The Sign-Rank of AC^O

  2008cites this paper
• The complexity of properly learning simple concept classes

  2008cites this paper
• The Sign-rank of Ac

  2008cites this paper
• Collisions Lead to Shallower Decision Trees

  2008cites this paper
• Efficiency and computational limitations of learning algorithms

  2007cites this paper
• Exact Learning Composed Classes with a Small Number of Mistakes

  2006cites this paper
• On PAC learning algorithms for rich Boolean function classes

  2006influential citation
• Maximum Margin Algorithms with Boolean Kernels

  2005cites this paper
• Learning DNF in time 2Õ(n1/3)

  2004cites this paper
• Learnability and automatizability

  2004cites this paper
• Exact learning of DNF formulas using DNF hypotheses

  2002cites this paper
• Learnability beyond AC0

  2002influential citation
• Decision lists and threshold decision lists

  2002cites this paper
• Learning DNF in time

  2001influential citation
• Learning DNF in time 2 Õ(n 1/3 ) .

  2001influential citation