ECCC-Report TR15-098https://eccc.weizmann.ac.il/report/2015/098Comments and Revisions published for TR15-098en-usMon, 26 Oct 2015 18:17:40 +0200
Revision 2
| Separations in Query Complexity Based on Pointer Functions |
Andris Ambainis,
Kaspars Balodis,
Aleksandrs Belovs,
Troy Lee,
Miklos Santha,
Juris Smotrovs
https://eccc.weizmann.ac.il/report/2015/098#revision2In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized
query complexity for a total boolean function is given by the function $f$ on $n=2^k$ bits defined by a complete binary tree
of NAND gates of depth $k$, which achieves $R_0(f) = O(D(f)^{0.7537\ldots})$. We show this is false by giving an example
of a total boolean function $f$ on $n$ bits whose deterministic query complexity is $\Omega(n/\log(n))$ while its zero-error
randomized query complexity is $\tilde O(\sqrt{n})$.
We further show that the quantum query complexity of the same function is $\tilde O(n^{1/4})$, giving the first example of a total function with a super-quadratic gap between its quantum and deterministic query complexities.
We also construct a total boolean function $g$ on $n$ variables that has zero-error randomized query complexity
$\Omega(n/\log(n))$ and bounded-error randomized query complexity $R(g) = \tilde O(\sqrt{n})$. This is the first super-linear separation between these two complexity measures.
The exact quantum query complexity of the same function is $Q_E(g) = \tilde O(\sqrt{n})$.
These two functions show that the relations $D(f) = O(R_1(f)^2)$ and $R_0(f) = \tilde O(R(f)^2)$ are optimal, up to poly-logarithmic factors.
Further variations of these functions give additional separations between other query complexity measures: a cubic separation between $Q$ and $R_0$, a $3/2$-power separation between $Q_E$ and $R$, and a 4th power separation between approximate degree and bounded-error randomized query complexity.
All of these examples are variants of a function recently introduced by G\"{o}\"{o}s, Pitassi, and Watson
which they used to separate the unambiguous 1-certificate complexity
from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity. Mon, 26 Oct 2015 18:17:40 +0200https://eccc.weizmann.ac.il/report/2015/098#revision2
Revision 1
| Separations in Query Complexity Based on Pointer Functions |
Andris Ambainis,
Kaspars Balodis,
Aleksandrs Belovs,
Troy Lee,
Miklos Santha,
Juris Smotrovs
https://eccc.weizmann.ac.il/report/2015/098#revision1In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized
query complexity for a total boolean function is given by the function $f$ on $n=2^k$ bits defined by a complete binary tree
of NAND gates of depth $k$, which achieves $R_0(f) = O(D(f)^{0.7537\ldots})$. We show this is false by giving an example
of a total boolean function $f$ on $n$ bits whose deterministic query complexity is $\Omega(n/\log(n))$ while its zero-error
randomized query complexity is $\tilde O(\sqrt{n})$. This shows that the relations $D(f) \le R_0(f)^2$ and
$D(f) \le 2R_1(f)^2$ are optimal, up to poly-logarithmic factors. We further show that the quantum query complexity of
the same function is $\tilde O(n^{1/4})$, giving the first example of a total function with a super-quadratic gap between its
quantum and deterministic query complexities.
Variations of this function give new separations between several other query complexity measures, including: the first
super-linear separation between bounded-error and zero-error randomized complexity, larger gaps
between exact quantum query complexity and deterministic/randomized query complexities, and a 4th power separation
between approximate degree and bounded-error randomized complexity.
All of these examples are variants of a function recently introduced by G\"{o}\"{o}s, Pitassi, and Watson
which they used to separate the unambiguous 1-certificate complexity
from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.Mon, 13 Jul 2015 15:24:01 +0300https://eccc.weizmann.ac.il/report/2015/098#revision1
Paper TR15-098
| Separations in Query Complexity Based on Pointer Functions |
Andris Ambainis,
Kaspars Balodis,
Aleksandrs Belovs,
Troy Lee,
Miklos Santha,
Juris Smotrovs
https://eccc.weizmann.ac.il/report/2015/098In 1986, Saks and Wigderson conjectured that the largest separation between deterministic and zero-error randomized
query complexity for a total boolean function is given by the function $f$ on $n=2^k$ bits defined by a complete binary tree
of NAND gates of depth $k$, which achieves $R_0(f) = O(D(f)^{0.7537\ldots})$. We show this is false by giving an example
of a total boolean function $f$ on $n$ bits whose deterministic query complexity is $\Omega(n/\log(n))$ while its zero-error
randomized query complexity is $\tilde O(\sqrt{n})$. This shows that the relations $D(f) \le R_0(f)^2$ and
$D(f) \le 2R_1(f)^2$ are optimal, up to poly-logarithmic factors. We further show that the quantum query complexity of
the same function is $\tilde O(n^{1/4})$, giving the first example of a total function with a super-quadratic gap between its
quantum and deterministic query complexities.
Variations of this function give new separations between several other query complexity measures, including: the first
super-linear separation between bounded-error and zero-error randomized complexity, larger gaps
between exact quantum query complexity and deterministic/randomized query complexities, and a 4th power separation
between approximate degree and bounded-error randomized complexity.
All of these examples are variants of a function recently introduced by G\"{o}\"{o}s, Pitassi, and Watson
which they used to separate the unambiguous 1-certificate complexity
from deterministic query complexity and to resolve the famous Clique versus Independent Set problem in communication complexity.Tue, 16 Jun 2015 13:50:13 +0300https://eccc.weizmann.ac.il/report/2015/098