Geodesic
On non-adaptive majority problems of large query size
Discrete mathematics & theoretical computer science, Tome 23 (2021-2022) no. 3.

Voir la notice de l'article provenant de la source Episciences

We are given $n$ balls and an unknown coloring of them with two colors. Our goal is to find a ball that belongs to the larger color class, or show that the color classes have the same size. We can ask sets of $k$ balls as queries, and the problem has different variants, according to what the answers to the queries can be. These questions has attracted several researchers, but the focus of most research was the adaptive version, where queries are decided sequentially, after learning the answer to the previous query. Here we study the non-adaptive version, where all the queries have to be asked at the same time.
DOI : 10.46298/dmtcs.7084
Classification : 68P10, 68R05 
@article{DMTCS_2021_23_3_a9,
     author = {Gerbner, D\'aniel and Vizer, M\'at\'e},
     title = {On non-adaptive majority problems of large query size},
     journal = {Discrete mathematics & theoretical computer science},
     publisher = {mathdoc},
     volume = {23},
     number = {3},
     year = {2021-2022},
     doi = {10.46298/dmtcs.7084},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.7084/}
}
TY  - JOUR
AU  - Gerbner, Dániel
AU  - Vizer, Máté
TI  - On non-adaptive majority problems of large query size
JO  - Discrete mathematics & theoretical computer science
PY  - 2021-2022
VL  - 23
IS  - 3
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.7084/
DO  - 10.46298/dmtcs.7084
LA  - en
ID  - DMTCS_2021_23_3_a9
ER  - 
%0 Journal Article
%A Gerbner, Dániel
%A Vizer, Máté
%T On non-adaptive majority problems of large query size
%J Discrete mathematics & theoretical computer science
%D 2021-2022
%V 23
%N 3
%I mathdoc
%U http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.7084/
%R 10.46298/dmtcs.7084
%G en
%F DMTCS_2021_23_3_a9
Gerbner, Dániel; Vizer, Máté. On non-adaptive majority problems of large query size. Discrete mathematics & theoretical computer science, Tome 23 (2021-2022) no. 3. doi : 10.46298/dmtcs.7084. http://geodesic.mathdoc.fr/articles/10.46298/dmtcs.7084/

Cité par Sources :