The parity search problem

zbMATH Open1304.05144arXiv1603.06164MaRDI QIDQ2249168FDOQ2249168

Authors: Christian Reiher 

Publication date: 9 July 2014

Published in: Moscow Journal of Combinatorics and Number Theory (Search for Journal in Brave)

Abstract: We prove that for any positive integers $n$ and $d$ there exists a collection consisting of $f=dlogn+O(1)$ subsets $A_1,A_2,ldots,A_f$ of $[n]$ such that for any two distinct subsets $X$ and $Y$ of $[n]$ whose size is at most $d$ there is an index $iin[f]$ for which $|A_{i}capX|$ and $|A_{i}capY|$ have different parity. Here we think of $d$ as fixed whereas $n$ is thought of as tending to infinity, and the base of the logarithm is $2$. Translated into the language of combinatorial search theory, this tells us that [ d log n+O(1) ] queries suffice to identify up to $d$ marked items from a totality of $n$ items if the answers one gets are just whether an even or an odd number of marked elements has been queried, even if the search is performed non-adaptively. Since the entropy method easily yields a matching lower bound for the adaptive version of this problem, our result is asymptotically best possible. This answers a question posed by D'aniel Gerbner and Bal'azs Patk'os in Gyula O.H. Katona's Search Theory Seminar at the R'enyi institute.

Full work available at URL: https://arxiv.org/abs/1603.06164

Recommendations

• scientific article; zbMATH DE number 2100868
• Nonadaptive search problem with sets of equal sum
• Search using queries on indistinguishable items
• Identifying defective sets using queries of small size
• On a parity based group testing algorithm

zbMATH Keywords

finite fieldscombinatorial search theoryparity search

Mathematics Subject Classification ID

Search theory (90B40) Extremal set theory (05D05) Finite fields and commutative rings (number-theoretic aspects) (11T99)

Cited In (2)

• Nonadaptive search problem with sets of equal sum
• Finitely repeated search and the diamond paradox

This page was built for publication: The parity search problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2249168)