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...
| Hoofdauteurs: | , , , |
|---|---|
| Andere auteurs: | |
| Formaat: | Artikel |
| Taal: | en_US |
| Gepubliceerd in: |
Springer-Verlag
2015
|
| Online toegang: | http://hdl.handle.net/1721.1/99645 https://orcid.org/0000-0003-3292-2520 https://orcid.org/0000-0003-1333-4045 |