13 citations · 32 across the 25 of their papers we have counts for
13 papers · 1 filter
Almost Optimal Proper Learning and Testing Polynomials
Nader H. Bshouty
We give the first almost optimal polynomial-time proper learning algorithm of Boolean sparse multivariate polynomial under the uniform distribution. For -sparse polynomial over…
Bounds for the Number of Tests in Non-Adaptive Randomized Algorithms for Group Testing
Nader H. Bshouty, George Haddad, Catherine A. Haddad-Zaknoon
We study the group testing problem with non-adaptive randomized algorithms. Several models have been discussed in the literature to determine how to randomly choose the tests. For…
Adaptive Exact Learning of Decision Trees from Membership Queries
Nader H. Bshouty, Catherine A. Haddad-Zaknoon
In this paper we study the adaptive learnability of decision trees of depth at most from membership queries. This has many applications in automated scientific discovery such a…
On Learning Graphs with Edge-Detecting Queries
Hasan Abasi, Nader H. Bshouty
We consider the problem of learning a general graph using edge-detecting queries, where the number of vertices is given to the learner. The information theoretic…
Non-Adaptive Randomized Algorithm for Group Testing
Nader H. Bshouty, Nuha Diab, Shada R. Kawar +1
We study the problem of group testing with a non-adaptive randomized algorithm in the random incidence design (RID) model where each entry in the test is chosen randomly independen…
The Maximum Cosine Framework for Deriving Perceptron Based Linear Classifiers
Nader H. Bshouty, Catherine A. Haddad-Zaknoon
In this work, we introduce a mathematical framework, called the Maximum Cosine Framework or MCF, for deriving new linear classifiers. The method is based on selecting an appropriat…
Exact Learning of Juntas from Membership Queries
Nader H. Bshouty, Areej Costa
In this paper, we study adaptive and non-adaptive exact learning of Juntas from membership queries. We use new techniques to find new bounds, narrow some of the gaps between the lo…
Learning Disjunctions of Predicates
Nader H. Bshouty, Dana Drachsler-Cohen, Martin Vechev +1
Let be a set of boolean functions. We present an algorithm for learning from membership queries. Our algorithm asks at most $…
Exact Learning from an Honest Teacher That Answers Membership Queries
Nader H. Bshouty
Given a teacher that holds a function from some class of functions . The teacher can receive from the learner an element~ in the domain (a query) and returns t…
Non-Adaptive Learning a Hidden Hipergraph
Hasan Abasi, Nader H. Bshouty, Hanna Mazzawi
We give a new deterministic algorithm that non-adaptively learns a hidden hypergraph from edge-detecting queries. All previous non-adaptive algorithms either run in exponential tim…
Learning Boolean Halfspaces with Small Weights from Membership Queries
Hasan Abasi, Ali Z. Abdi, Nader H. Bshouty
We consider the problem of proper learning a Boolean Halfspace with integer weights from membership queries only. The best known algorithm for this problem is an…
On Exact Learning Monotone DNF from Membership Queries
Hasan Abasi, Nader H. Bshouty, Hanna Mazzawi
In this paper, we study the problem of learning a monotone DNF with at most terms of size (number of variables in each term) at most ( term -MDNF) from membership que…
Optimal Query Complexity for Reconstructing Hypergraphs
Nader H. Bshouty, Hanna Mazzawi
In this paper we consider the problem of reconstructing a hidden weighted hypergraph of constant rank using additive queries. We prove the following: Let be a weighted hidden h…