Unambiguous Parity‐Query Complexity
Dmitry Gavinsky · Random Structures and Algorithms · 2025
ABSTRACT We give a lower bound of on the unambiguous randomized parity‐query complexity of the approximate majority problem—that is, on the lowest randomized parity‐query complexity of any function over whose value is “” if the Hamming weight of the input is at most , is “” if the weight is at least , and may be arbitrary otherwise.