N. Bshouty

activity

20102026

most citedOn Learning Graphs with Edge-Detecting Queries

13 citations · 32 across the 25 of their papers we have counts for

collaborators

36 papers

cs.DS2026

Classes Testable with $O (1/ ε)$ Queries for Small $ε$ Independent of the Number of Variables

Nader H. Bshouty, George Haddad

In this paper, we study classes of Boolean functions that are testable with $O (ψ + 1/ ε)$ queries, where $ψ$ depends on the parameters of the class (e.g., the number of terms, the num…

cs.DS2023

A Tight Lower Bound of $Ω (lo g n)$ for the Estimation of the Number of Defective Items

Nader H. Bshouty, Gergely Harcos

Let $X$ be a set of items of size $n$ , which may contain some defective items denoted by $I$ , where $I \subseteq X$ . In group testing, a {\it test} refers to a subset of items $Q…

cs.DS2023

Improved Lower Bound for Estimating the Number of Defective Items

Nader H. Bshouty

Let $X$ be a set of items of size $n$ that contains some defective items, denoted by $I$ , where $I \subseteq X$ . In group testing, a {\it test} refers to a subset of items $Q \subs…

cs.DS2023

On Detecting Some Defective Items in Group Testing

Nader H. Bshouty, Catherine A. Haddad-Zaknoon

Group testing is an approach aimed at identifying up to $d$ defective items among a total of $n$ elements. This is accomplished by examining subsets to determine if at least one de…

cs.DS2023

Superpolynomial Lower Bounds for Learning Monotone Classes

Nader H. Bshouty

Koch, Strassle, and Tan [SODA 2023], show that, under the randomized exponential time hypothesis, there is no distribution-free PAC-learning algorithm that runs in time $n^{\tilde…

cs.DS2023

A Note on Property Testing of the Binary Rank

Nader H. Bshouty

Let $M$ be a $n \times m$ $(0, 1)$ -matrix. We define the $s$ -binary rank, $b r_{s} (M)$ , of $M$ to be the minimal integer $d$ such that there are $d$ monochromatic rectangles that cover…

cs.LG2022

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 $s$ -sparse polynomial over…

cs.DS2021★ 3 cited

On Learning and Testing Decision Tree

Nader H. Bshouty, Catherine A. Haddad-Zaknoon

In this paper, we study learning and testing decision tree of size and depth that are significantly smaller than the number of attributes $n$ . Our main result addresses the problem…

cs.IT2020

Optimal Deterministic Group Testing Algorithms to Estimate the Number of Defectives

Nader H. Bshouty, Catherine A. Haddad-Zaknoon

We study the problem of estimating the number of defective items $d$ within a pile of $n$ elements up to a multiplicative factor of $Δ > 1$ , using deterministic group testing algorit…

cs.CC2020

An Optimal Tester for $k$ -Linear

Nader H. Bshouty

A Boolean function $f : {0, 1}^{n} \to {0, 1}$ is $k$ -linear if it returns the sum (over the binary field $F_{2}$ ) of $k$ coordinates of the input. In this paper, we study property test…

cs.CC2020

Lecture Note on LCSSX's Lower Bounds for Non-Adaptive Distribution-free Property Testing

Nader H. Bshouty

In this lecture note we give Liu-Chen-Servedio-Sheng-Xie's (LCSSX) lower bound for property testing in the non-adaptive distribution-free.

cs.IT2020

Optimal Randomized Group Testing Algorithm to Determine the Number of Defectives

Nader H. Bshouty, Catherine A. Haddad-Zaknoon, Raghd Boulos +4

We study the problem of determining exactly the number of defective items in an adaptive Group testing by using a minimum number of tests. We improve the existing algorithm and pro…

cs.LG2019

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…

cs.DS2019

Almost Optimal Testers for Concise Representations

Nader H. Bshouty

We give improved and almost optimal testers for several classes of Boolean functions on $n$ inputs that have concise representation in the uniform and distribution-free model. Clas…

cs.LG2019

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 $d$ from membership queries. This has many applications in automated scientific discovery such a…

cs.DS2019

Almost Optimal Distribution-free Junta Testing

Nader H. Bshouty

We consider the problem of testing whether an unknown $n$ -variable Boolean function is a $k$ -junta in the distribution-free property testing model, where the distance between funct…

cs.LG2018★ 13 cited

On Learning Graphs with Edge-Detecting Queries

Hasan Abasi, Nader H. Bshouty

We consider the problem of learning a general graph $G = (V, E)$ using edge-detecting queries, where the number of vertices $∣ V ∣ = n$ is given to the learner. The information theoretic…

cs.DS2018

On Polynomial time Constructions of Minimum Height Decision Tree

Nader H. Bshouty, Waseem Makhoul

In this paper we study a polynomial time algorithms that for an input $A \subseteq B_{m}$ outputs a decision tree for $A$ of minimum depth. This problem has many applications that i…

cs.DS2017

Adaptive Group Testing Algorithms to Estimate the Number of Defectives

Nader H. Bshouty, Vivian E. Bshouty-Hurani, George Haddad +3

We study the problem of estimating the number of defective items in adaptive Group testing by using a minimum number of queries. We improve the existing algorithm and prove a lower…

cs.LG2017

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…

cs.LG2017

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…

cs.LG2017

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…

cs.LG2017★ 2 cited

Learning Disjunctions of Predicates

Nader H. Bshouty, Dana Drachsler-Cohen, Martin Vechev +1

Let $F$ be a set of boolean functions. We present an algorithm for learning $F_{\lor} := {\lor_{f \in S} f ∣ S \subseteq F}$ from membership queries. Our algorithm asks at most $…

cs.LG2017

Exact Learning from an Honest Teacher That Answers Membership Queries

Nader H. Bshouty

Given a teacher that holds a function $f : X \to R$ from some class of functions $C$ . The teacher can receive from the learner an element~ $d$ in the domain $X$ (a query) and returns t…

Classes Testable with O(1/ε) Queries for Small ε Independent of the Number of Variables

A Tight Lower Bound of Ω(logn) for the Estimation of the Number of Defective Items

Improved Lower Bound for Estimating the Number of Defective Items

On Detecting Some Defective Items in Group Testing

Superpolynomial Lower Bounds for Learning Monotone Classes

A Note on Property Testing of the Binary Rank

Almost Optimal Proper Learning and Testing Polynomials

On Learning and Testing Decision Tree

Optimal Deterministic Group Testing Algorithms to Estimate the Number of Defectives

An Optimal Tester for k-Linear

Lecture Note on LCSSX's Lower Bounds for Non-Adaptive Distribution-free Property Testing

Optimal Randomized Group Testing Algorithm to Determine the Number of Defectives

Bounds for the Number of Tests in Non-Adaptive Randomized Algorithms for Group Testing

Almost Optimal Testers for Concise Representations

Adaptive Exact Learning of Decision Trees from Membership Queries

Almost Optimal Distribution-free Junta Testing

On Learning Graphs with Edge-Detecting Queries

On Polynomial time Constructions of Minimum Height Decision Tree

Adaptive Group Testing Algorithms to Estimate the Number of Defectives

Non-Adaptive Randomized Algorithm for Group Testing

The Maximum Cosine Framework for Deriving Perceptron Based Linear Classifiers

Exact Learning of Juntas from Membership Queries

Learning Disjunctions of Predicates

Exact Learning from an Honest Teacher That Answers Membership Queries

Classes Testable with $O (1/ ε)$ Queries for Small $ε$ Independent of the Number of Variables

A Tight Lower Bound of $Ω (lo g n)$ for the Estimation of the Number of Defective Items

An Optimal Tester for $k$ -Linear