Yaakov Malinovsky

dblp:119/8621 · DBLP profile ↗
← Back
2ranked-venue papers
1as first author
2since 2021 · last 2026
0000-0003-2888-674XORCID · corroborated

Domains — the database's venue-derived domains; a paper can count in several

Theory of computation · 2 · 1 first-author · 2 since 2021
YearPublicationVenuePosition
2026 Uniqueness of maximum scores in countable-outcome round-robin tournaments
Gideon Amir, Yaakov Malinovsky
Discret. Appl. Math.2
2026 The Optimality of a Nested Generalized Pairwise Group Testing Procedure
abstract
We study the problem of identifying defective units in a finite population ofnunits, where unit no.iis independently defective with known probabilitypi. This setting is referred to as theGeneralized Group Testing Problem. A testing procedure is called optimal if it minimizes the expected number of tests. It has been conjectured that, when all probabilitiespilie within the interval [1 − 1/√2, 3−√5/2], thegeneralized pairwise testing algorithm, applied to thepiarranged in non-decreasing order, constitutes the optimal nested testing strategy among all such order-preserving nested strategies. In this work, we confirm this conjecture and establish the optimality of the procedure within the specified regime. Additionally, we provide a complete structural characterization of the procedure and derive a closed-form expression for its expected number of tests. These results offer new insights into the theory of optimal nested strategies in generalized group testing.
Yaakov Malinovsky, Viktor Skorniakov
IEEE Trans. Inf. Theory1