Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-009 | 20th January 2024 18:46

Unambiguous parity-query complexity

RSS-Feed




TR24-009
Authors: Dmytro Gavinsky
Publication: 21st January 2024 12:51
Downloads: 285
Keywords: 


Abstract:

We give a lower bound of ?(?n) on the unambiguous randomised parity-query complexity of the approximate majority problem – that is, on the lowest randomised parity-query complexity of any function over {0,1}? whose value is "0" if the Hamming weight of the input is at most n/3, is "1" if the weight is at least 2n/3, and may be arbitrary otherwise.


Comment(s):

Comment #1 to TR24-009 | 21st January 2024 14:59

Unambiguous parity-query complexity

Authors: Dmytro Gavinsky
Accepted on: 21st January 2024 14:59
Keywords: 


Comment:

We give a lower bound of $\Omega(\sqrt n)$ on the unambiguous randomised parity-query complexity of the approximate majority problem – that is, on the lowest randomised parity-query complexity of any function over ${0,1}^n$ whose value is "0"; if the Hamming weight of the input is at most n/3, is "1"; if the weight is at least 2n/3, and may be arbitrary otherwise.




ISSN 1433-8092 | Imprint