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

Showing 2023Show all

5 papers · 1 filter

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…

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

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