All reports by Author Nader Bshouty:

__
TR14-004
| 30th November 2013
__

Hasan Abasi, Nader Bshouty, Ariel Gabizon, Elad Haramaty#### On $r$-Simple $k$-Path

__
TR02-019
| 20th March 2002
__

Nader Bshouty, Lynn Burroughs#### On the proper learning of axis parallel concepts

__
TR98-076
| 13th November 1998
__

Nader Bshouty, Jeffrey J. Jackson, Christino Tamon#### Attribute Efficient PAC Learning of DNF with Membership Queries under the Uniform Distribution

__
TR98-013
| 3rd March 1998
__

Nader Bshouty#### A New Composition Theorem for Learning Algorithms

__
TR96-059
| 12th November 1996
__

Shai Ben-David, Nader Bshouty, Eyal Kushilevitz#### A Composition Theorem for Learning Algorithms with Applications to Geometric Concept Classes

__
TR96-009
| 17th January 1996
__

Francesco Bergadano, Nader Bshouty, Christino Tamon, Stefano Varricchio#### On Learning Branching Programs and Small Depth Circuits

__
TR95-060
| 21st November 1995
__

Nader Bshouty#### A Subexponential Exact Learning Algorithm for DNF Using Equivalence Queries

__
TR95-059
| 21st November 1995
__

Nader Bshouty#### The Monotone Theory for the PAC-Model

__
TR95-032
| 6th April 1995
__

Nader Bshouty, Christino Tamon#### On the Fourier spectrum of monotone functions

Hasan Abasi, Nader Bshouty, Ariel Gabizon, Elad Haramaty

An $r$-simple $k$-path is a {path} in the graph of length $k$ that

passes through each vertex at most $r$ times. The \simpath{r}{k}

problem, given a graph $G$ as input, asks whether there exists an

$r$-simple $k$-path in $G$. We first show that this problem is

NP-Complete. We then show ...
more >>>

Nader Bshouty, Lynn Burroughs

We study the proper learnability of axis parallel concept classes

in the PAC learning model and in the exact learning model with

membership and equivalence queries. These classes include union of boxes,

DNF, decision trees and multivariate polynomials.

For the {\it constant} dimensional axis parallel concepts $C$

we ...
more >>>

Nader Bshouty, Jeffrey J. Jackson, Christino Tamon

We study attribute efficient learning in the PAC learning model with

membership queries. First, we give an {\it attribute efficient}

PAC-learning algorithm for DNF with membership queries under the

uniform distribution. Previous algorithms for DNF have sample size

polynomial in the number of attributes $n$. Our algorithm is the

first ...
more >>>

Nader Bshouty

We present a new approach to the composition

of learning algorithms (in various models) for

classes of constant VC-dimension into learning algorithms for

more complicated classes.

We prove that if a class $\CC$ is learnable

in time $t$ from a hypothesis class $\HH$ of constant VC-dimension

then the class ...
more >>>

Shai Ben-David, Nader Bshouty, Eyal Kushilevitz

This paper solves the open problem of exact learning

geometric objects bounded by hyperplanes (and more generally by any constant

degree algebraic surfaces) in the constant

dimensional space from equivalence queries only (i.e., in the on-line learning

model).

We present a novel approach that allows, under ...
more >>>

Francesco Bergadano, Nader Bshouty, Christino Tamon, Stefano Varricchio

This paper studies the learnability of branching programs and small depth

circuits with modular and threshold gates in both the exact and PAC learning

models with and without membership queries. Some of the results extend earlier

works in [GG95,ERR95,BTW95]. The main results are as follows. For

branching programs we ...
more >>>

Nader Bshouty

We present a $2^{\tilde O(\sqrt{n})}$ time exact learning

algorithm for polynomial size

DNF using equivalence queries only. In particular, DNF

is PAC-learnable in subexponential time under any distribution.

This is the first subexponential time

PAC-learning algorithm for DNF under any distribution.

Nader Bshouty

We show that a DNF formula that has a CNF representation that contains

at least one ``$1/poly$-heavy''

clause with respect to a distribution $D$ is weakly learnable

under this distribution. So DNF that are not weakly

learnable under the distribution $D$ do not have

any ``$1/poly$-heavy'' clauses in any of ...
more >>>

Nader Bshouty, Christino Tamon