ECCC-Report TR13-164https://eccc.weizmann.ac.il/report/2013/164Comments and Revisions published for TR13-164en-usThu, 28 Nov 2013 03:07:06 +0200
Paper TR13-164
| Weak Parity |
Scott Aaronson,
Andris Ambainis,
Kaspars Balodis,
Mohammad Bavarian
https://eccc.weizmann.ac.il/report/2013/164We 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+eps 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^0.246(1/eps)) queries, as well as a quantum algorithm that makes only O(n/sqrt(log(1/eps))) queries. We also prove a lower bound of Omega(n/log(1/eps)) in both cases; and using extremal combinatorics, prove lower bounds of Omega(log n) in the randomized case and Omega(sqrt(log n)) in the quantum case for any eps>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.Thu, 28 Nov 2013 03:07:06 +0200https://eccc.weizmann.ac.il/report/2013/164