Dániel Gerbner ; Máté Vizer - On non-adaptive majority problems of large query size

dmtcs:7084 - Discrete Mathematics & Theoretical Computer Science, November 26, 2021, vol. 23, no. 3 - https://doi.org/10.46298/dmtcs.7084
On non-adaptive majority problems of large query sizeArticle

Authors: Dániel Gerbner ; Máté Vizer

    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.


    Volume: vol. 23, no. 3
    Section: Analysis of Algorithms
    Published on: November 26, 2021
    Accepted on: October 27, 2021
    Submitted on: January 13, 2021
    Keywords: Mathematics - Combinatorics

    Classifications

    Consultation statistics

    This page has been seen 593 times.
    This article's PDF has been downloaded 331 times.