6 papers
A Tight Scale-Locality Bound for Partial Detection in Non-Adaptive Group Testing
Nader H. Bshouty
We give a lower bound for randomized non-adaptive group testing when the goal is to find any defective items but the total number of defectives is unknown. Bshouty and H…
Sublinear Time Algorithms for Abelian Group Property Testing
Nader H. Bshouty
In this paper, we study the problems of abelian group property testing in two models. In the partially specified model (PS-model), the algorithm does not know the group size but ca…
A Note on Second-Order Expected Maximum-Load Bounds for Binary Linear Hashing
Nader H. Bshouty
Let have size , and let be a uniformly random linear map. For , write , and let $M(S…
Sublinear Time Algorithms for Abelian Group Isomorphism and Basis Construction
Nader H. Bshouty
In this paper, we study the problems of abelian group isomorphism and basis construction in two models. In the {\it partially specified model} (PS-model), the algorithm does not kn…
On Exact Learning of -Monotone Functions
Nader H. Bshouty
In this paper, we study the learnability of the Boolean class of -monotone functions from membership and equivalence queries, where is a…
Approximating the Number of Relevant Variables in a Parity Implies Proper Learning
Nader H. Bshouty, George Haddad
Consider the model where we can access a parity function through random uniform labeled examples in the presence of random classification noise. In this paper, we show that approxi…