13 citations · 32 across the 25 of their papers we have counts for
13 papers · 1 filter
Classes Testable with 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 queries, where depends on the parameters of the class (e.g., the number of terms, the num…
A Tight Lower Bound of for the Estimation of the Number of Defective Items
Nader H. Bshouty, Gergely Harcos
Let be a set of items of size , which may contain some defective items denoted by , where . In group testing, a {\it test} refers to a subset of items $Q…
Improved Lower Bound for Estimating the Number of Defective Items
Nader H. Bshouty
Let be a set of items of size that contains some defective items, denoted by , where . In group testing, a {\it test} refers to a subset of items $Q \subs…
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 defective items among a total of elements. This is accomplished by examining subsets to determine if at least one de…
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…
A Note on Property Testing of the Binary Rank
Nader H. Bshouty
Let be a -matrix. We define the -binary rank, , of to be the minimal integer such that there are monochromatic rectangles that cover…
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 . Our main result addresses the problem…
Almost Optimal Testers for Concise Representations
Nader H. Bshouty
We give improved and almost optimal testers for several classes of Boolean functions on inputs that have concise representation in the uniform and distribution-free model. Clas…
Almost Optimal Distribution-free Junta Testing
Nader H. Bshouty
We consider the problem of testing whether an unknown -variable Boolean function is a -junta in the distribution-free property testing model, where the distance between funct…
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 outputs a decision tree for of minimum depth. This problem has many applications that i…
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…
A Simple Algorithm for Hamiltonicity
Hasan Abasi, Nader H. Bshouty
We develop a new algebraic technique that solves the following problem: Given a black box that contains an arithmetic circuit over a field of characteristic of degree~.…
On -Simple -Path
Hasan Abasi, Nader H. Bshouty, Ariel Gabizon +1
An -simple -path is a {path} in the graph of length that passes through each vertex at most times. The -SIMPLE -PATH problem, given a graph as input, asks w…