Weak Parity
We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2 + ε fraction of input strings, but must do so with high probability on those inputs where one does succeed. It is well-known that n randomized queries an...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | en_US |
| Published: |
Springer-Verlag
2015
|
| Online Access: | http://hdl.handle.net/1721.1/99645 https://orcid.org/0000-0003-3292-2520 https://orcid.org/0000-0003-1333-4045 |
| Summary: | We study the query complexity of Weak Parity: the problem of computing the parity of an n-bit input string, where one only has to succeed on a 1/2 + ε fraction of input strings, but must do so with high probability on those inputs where one does succeed. It is well-known that n randomized queries and n/2 quantum queries are needed to compute parity on all inputs. But surprisingly, we give a randomized algorithm for Weak Parity that makes only O(n/log[superscript 0.246](1/ε)) queries, as well as a quantum algorithm that makes O(n/√log(1/ε)) queries. We also prove a lower bound of Ω(n/log(1/ε)) in both cases, as well as lower bounds of Ω(logn) in the randomized case and Ω(√logn) in the quantum case for any ε > 0. We show that improving our lower bounds is intimately related to two longstanding open problems about Boolean functions: the Sensitivity Conjecture, and the relationships between query complexity and polynomial degree. |
|---|