On non-adaptive majority problems of large query size
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...
| Main Authors: | , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2021-11-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/7084/pdf |
| _version_ | 1797270025483059200 |
|---|---|
| author | Dániel Gerbner Máté Vizer |
| author_facet | Dániel Gerbner Máté Vizer |
| author_sort | Dániel Gerbner |
| collection | DOAJ |
| description | 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. |
| first_indexed | 2024-04-25T01:57:42Z |
| format | Article |
| id | doaj.art-ae9e099acf7e4aef8e3a8eeaa5046417 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:42Z |
| publishDate | 2021-11-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-ae9e099acf7e4aef8e3a8eeaa50464172024-03-07T15:45:30ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502021-11-01vol. 23, no. 3Analysis of Algorithms10.46298/dmtcs.70847084On non-adaptive majority problems of large query sizeDániel GerbnerMáté VizerWe 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.https://dmtcs.episciences.org/7084/pdfmathematics - combinatorics |
| spellingShingle | Dániel Gerbner Máté Vizer On non-adaptive majority problems of large query size Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics |
| title | On non-adaptive majority problems of large query size |
| title_full | On non-adaptive majority problems of large query size |
| title_fullStr | On non-adaptive majority problems of large query size |
| title_full_unstemmed | On non-adaptive majority problems of large query size |
| title_short | On non-adaptive majority problems of large query size |
| title_sort | on non adaptive majority problems of large query size |
| topic | mathematics - combinatorics |
| url | https://dmtcs.episciences.org/7084/pdf |
| work_keys_str_mv | AT danielgerbner onnonadaptivemajorityproblemsoflargequerysize AT matevizer onnonadaptivemajorityproblemsoflargequerysize |