5 citations · 12 across the 10 of their papers we have counts for
10 papers
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…
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…
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…
Dense Testers: Almost Linear Time and Locally Explicit Constructions
Nader H. Bshouty
We develop a new notion called -tester for a set of functions . A -tester for maps each element to a finite number of elements $B_a=\{b_1,\…