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 |
| _version_ | 1811078112769736704 |
|---|---|
| author | Aaronson, Scott Ambainis, Andris Balodis, Kaspars Bavarian, Mohammad |
| author2 | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science |
| author_facet | Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Aaronson, Scott Ambainis, Andris Balodis, Kaspars Bavarian, Mohammad |
| author_sort | Aaronson, Scott |
| collection | MIT |
| description | 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. |
| first_indexed | 2024-09-23T10:53:35Z |
| format | Article |
| id | mit-1721.1/99645 |
| institution | Massachusetts Institute of Technology |
| language | en_US |
| last_indexed | 2024-09-23T10:53:35Z |
| publishDate | 2015 |
| publisher | Springer-Verlag |
| record_format | dspace |
| spelling | mit-1721.1/996452022-09-30T23:46:09Z Weak Parity Aaronson, Scott Ambainis, Andris Balodis, Kaspars Bavarian, Mohammad Massachusetts Institute of Technology. Department of Electrical Engineering and Computer Science Massachusetts Institute of Technology. Department of Mathematics Aaronson, Scott Bavarian, Mohammad 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. National Science Foundation (U.S.) (Grant 0844626) National Science Foundation (U.S.) (Alan T. Waterman Award) National Science Foundation (U.S.). Science and Technology Center (Award 0939370) 2015-11-02T17:16:49Z 2015-11-02T17:16:49Z 2014 Article http://purl.org/eprint/type/ConferencePaper 978-3-662-43947-0 978-3-662-43948-7 0302-9743 1611-3349 http://hdl.handle.net/1721.1/99645 Aaronson, Scott, Andris Ambainis, Kaspars Balodis, and Mohammad Bavarian. “Weak Parity.” Lecture Notes in Computer Science (2014): 26–38. https://orcid.org/0000-0003-3292-2520 https://orcid.org/0000-0003-1333-4045 en_US http://dx.doi.org/10.1007/978-3-662-43948-7_3 Automata, Languages, and Programming Creative Commons Attribution-Noncommercial-Share Alike http://creativecommons.org/licenses/by-nc-sa/4.0/ application/pdf Springer-Verlag MIT web domain |
| spellingShingle | Aaronson, Scott Ambainis, Andris Balodis, Kaspars Bavarian, Mohammad Weak Parity |
| title | Weak Parity |
| title_full | Weak Parity |
| title_fullStr | Weak Parity |
| title_full_unstemmed | Weak Parity |
| title_short | Weak Parity |
| title_sort | weak parity |
| url | http://hdl.handle.net/1721.1/99645 https://orcid.org/0000-0003-3292-2520 https://orcid.org/0000-0003-1333-4045 |
| work_keys_str_mv | AT aaronsonscott weakparity AT ambainisandris weakparity AT balodiskaspars weakparity AT bavarianmohammad weakparity |