3 citations · 6 across the 11 of their papers we have counts for
17 papers
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…
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…
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 within a pile of elements up to a multiplicative factor of , using deterministic group testing algorit…
An Optimal Tester for -Linear
Nader H. Bshouty
A Boolean function is -linear if it returns the sum (over the binary field ) of coordinates of the input. In this paper, we study property test…
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.
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…