\(\mathrm{LS}([k]^d)\)
Local search on the grid
Tight at $\Theta(k^{d/2})$ randomized for $d\ge4$ and $\Theta(k^{d/3})$ quantum for $d\ge6$; the low dimensions took another decade, and $d=4$ quantum is still open.
relation relational arity: a table $f:[k]^d \to \mathbb{Z}$, so $N = k^d$ cells; $d$ is constant
Description
As \(\mathrm{LS}(\{0,1\}^n)\), on the $d$-dimensional grid with nearest-neighbour edges, so $\Delta = 2d$.
Measure values
| Measure | Value | Notes |
|---|---|---|
| \(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity | \(\Theta(k^{d/2})\ (d \ge 4)\) | [Zhang09localsearch, Thm. 3], matching Aldous' $O(\sqrt{N\Delta}) = O(k^{d/2})$. The two small dimensions cost a log: $\mathrm{R} = \tilde\Theta(k^{3/2})$ at $d = 3$, from $\Omega((k^3/\log k)^{1/2})$ [Zhang09localsearch, Thm. 3]; and $\mathrm{R} = \tilde\Theta(k)$ at $d = 2$, from $\Omega(k^{1-\delta})$ for every constant $\delta > 0$ [SunYao09] via Sarkozy-Szemeredi, against Aldous' $O(k)$ -- [Zhang09localsearch] had reached only $\Omega(k^{2/3})$ there. Zhang09localsearch Aldous83 SunYao09 |
| \(\mathrm{Q}_{\varepsilon}(f)\) Bounded-error quantum query complexity | \(\Theta(k^{d/3})\ (d \ge 6)\) | [Zhang09localsearch, Thm. 3], matching Aaronson's $O(N^{1/3}\Delta^{1/6}) = O(k^{d/3})$. Below $d = 6$ the picture degrades one dimension at a time: $\tilde\Theta(k^{5/3})$ at $d = 5$, from $\Omega((k^5/\log k)^{1/3})$ [Zhang09localsearch, Thm. 3]; a genuine polynomial gap $\Omega(k^{6/5})$ to $O(k^{4/3})$ at $d = 4$, the one cell of the table still open; $\tilde\Theta(k)$ at $d = 3$, from $\Omega(k^{1-\delta})$ [SunYao09] against $O(k)$; and $\tilde\Theta(\sqrt k)$ at $d = 2$, from $\Omega(k^{1/2-\delta})$ [SunYao09] against $O(\sqrt k\log\log k)$ [Verhoeven06] via graph genus (also $O(\sqrt k(\log\log k)^{1.5})$ [Zhang09localsearch, Thm. 5]). Zhang09localsearch Aaronson06 SunYao09 Verhoeven06 |
| \(\mathrm{D}(f)\) Deterministic query complexity | \(\Theta(k^{d-1})\) | Not merely $\tilde\Theta$: the deterministic case was settled before the randomized one. Upper $O(k^{d-1})$ by the divide-and-conquer of Llewellyn-Tovey-Trick: query the $(d-1)$-dimensional middle slab together with the boundary of the current region, take the smallest value seen, and recurse into whichever half contains a strictly smaller neighbour of it -- the region halves each round, so the slab costs form a geometric series. Matching $\Omega(k^{d-1})$ lower bounds are due to [LlewellynTovey93] and, independently, to Althofer and Koschnick (1993). The generic $\mathrm{D} = O(\log N\,(\Delta + s))$ of [SanthaSzegedy09, Thm. 2] with separation number $s([k]^d) = \Theta(k^{d-1})$ recovers the upper bound only up to the $\log$. LTT89 LlewellynTovey93 |
| \(\mathrm{R}_{0}(f)\) Zero-error randomized query complexity | \(\Theta(k^{d/2})\ (d \ge 4)\) | A candidate local minimum is verified with $\Delta = 2d = O(1)$ further queries, so $\mathrm{R}_0 = O(\mathrm{R} + d)$; with $d$ constant this is $\Theta(k^{d/2})$. Same remark as on \(\mathrm{LS}(\{0,1\}^n)\). |
| \(\mathrm{Q}_{0}(f)\) Zero-error (Las Vegas) quantum query complexity | \(\Theta(k^{d/3})\ (d \ge 6)\) | Same verification argument: $\mathrm{Q}_0 = O(\mathrm{Q} + d)$, and $d$ is constant. Zero error is free here for the same reason it is free classically. |
| \(\bar{\mathrm{R}}_{\varepsilon}(f)\) Expected-cost randomized query complexity | \(\Theta(k^{d/2})\ (d \ge 4)\) | $\bar{\mathrm{R}}_{\varepsilon}(f) = \Theta(\mathrm{R}_{\varepsilon}(f))$ for every $f$ (\(\bar{\mathrm{R}}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). |
| \(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity | \(\Theta(k^{d/2})\ (d \ge 4)\) | By Yao, $\max_\mu \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon$; [Zhang09localsearch, Thm. 3] argues against an explicit random-walk distribution, so the bound is a $\mathrm{D}^\mu$ bound already. |
| \(\mathrm{Adv}^{\pm}(f)\) General (negative-weights) adversary bound | \(\Theta(k^{d/3})\ (d \ge 6)\) | $\mathrm{Adv}^{\pm}(f) = \Theta(\mathrm{Q}_{\varepsilon}(f))$ for every $f$ (\(\mathrm{Adv}^{\pm}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)). In the open dimension $d = 4$ the general adversary inherits the window $[\Omega(k^{6/5}), O(k^{4/3})]$ verbatim. |
| \(\mathrm{D}^{\mathrm{na}}(f)\) Non-adaptive deterministic query complexity | \(k^d = N\) putative | Every cell, for every $d \ge 1$, so non-adaptivity is catastrophic already at $d = 2$ where $\mathrm{D} = \Theta(k)$. If the fixed query set $S$ omits the cell $u$, let $f$ agree on $S$ with the $\ell_1$ distance to $u$: when $f(u) = 0$ the unique local minimum is $u$, and when $f(u)$ is huge the local minima are exactly the neighbours of $u$. Same transcript, different required output. |
| \(\mathrm{C}(f)\) Certificate complexity | \(2d+1 = \Theta(1)\) putative | A local minimum is certified by its own value and those of its $\le 2d$ neighbours, and no smaller set will do -- omit a neighbour and it can be completed to a strictly smaller value. With $d$ constant this is $\Theta(1)$ against $\mathrm{D} = \Theta(k^{d-1})$, an unbounded $\mathrm{D}$-vs-$\mathrm{C}$ gap on a total search problem. Compare \(\mathrm{LS}(\{0,1\}^n)\), where the same argument gives $n+1$ because the degree grows. |
| \(\mathrm{R}^{\mathrm{na}}(f)\) Non-adaptive randomized query complexity | \(\Theta(k^d)\) putative | Every cell, even with randomness, so $\mathrm{R}^{\mathrm{na}} = \Theta(\mathrm{D}^{\mathrm{na}}) = \Theta(N)$. Randomise the \(\mathrm{D}^{\mathrm{na}}(f)\) construction: draw $u$ uniformly from $[k]^d$, let $f$ be the $\ell_1$ distance to $u$ off $u$, and set $f(u) \in \{0, 2dk\}$ by a fair coin. The two completions have disjoint solution sets and agree everywhere but $u$, so a fixed query set of size $t$ succeeds with probability at most $t/k^d + 1/2$. |
| \(\mathrm{psD}(S)\) Pseudo-deterministic query complexity | \(\Omega(k^{d/2}),\ O(k^{d-1})\ (d \ge 4)\) | Only the generic $\mathrm{R} \le \mathrm{psD} \le \mathrm{D}$ (\(\mathrm{psD}(S)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). The window is a factor $k^{d/2-1}$ wide, and unlike \(\mathrm{LS}(\{0,1\}^n)\) it stays wide for every fixed $d \ge 4$, so the grid is the cleaner family to ask the pseudo-deterministic question on: is there a canonical local minimum findable in $\tilde O(k^{d/2})$ randomized queries? |
| \(\mathrm{N}_{p}(f)\) Noisy decision tree complexity | \(\tilde\Theta(k^{d/2})\ (d \ge 4)\) | Between $\mathrm{R} = \Theta(k^{d/2})$ and $O(\mathrm{R}\log \mathrm{R}) = O(k^{d/2}\log k)$ (\(\mathrm{N}_{p}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\)). |
| \(\mathrm{Q}^{\mathrm{rob}}(f)\) Robust quantum query complexity | \(\tilde\Theta(k^{d/3})\ (d \ge 6)\) | Between $\mathrm{Q} = \Theta(k^{d/3})$ and $O(\mathrm{Q}\log \mathrm{Q}) = O(k^{d/3}\log k)$ (\(\mathrm{Q}^{\mathrm{rob}}(f)\) vs \(\mathrm{Q}_{\varepsilon}(f)\)). |
| \(\gamma_2^{\alpha}(f)\) Approximate gamma_2 norm | \(\Theta(k^{d/3})\ (d \ge 6)\)· | Equal to $\mathrm{Adv}^{\pm}$ up to constants (\(\gamma_2^{\alpha}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)). Medium confidence only because $\gamma_2$ is listed as partially defined on relations. |
| \(\mathrm{MAdv}(f)\) Multiplicative adversary | \(\Theta(k^{d/3})\ (d \ge 6)\)· | Squeezed between $\mathrm{Adv}^{\pm} = \Theta(k^{d/3})$, which it dominates, and $\mathrm{Q} = \Theta(k^{d/3})$, which it is below. Same definedness caveat as $\gamma_2$. |
| \(\mathrm{C}_{\min}(f)\) Minimum certificate complexity | \(\Theta(1)\) | Between $d+1$ and $\mathrm{C}=2d+1$: a corner cell has only $d$ neighbours to check, an interior cell has $2d$, and $d$ is a constant. |
| \(\mathrm{Adv}(f)\) Positive-weights adversary bound | \(O(k^{d/3})\ (d \ge 6)\) | $\mathrm{Adv}\le\mathrm{Adv}^{\pm}=\Theta(k^{d/3})$ (\(\mathrm{Adv}(f)\) vs \(\mathrm{Adv}^{\pm}(f)\)). As on \(\mathrm{LS}(\{0,1\}^n)\), the known lower bound is a relational adversary argument rather than a positive-weight quantum one. |
| \(\mathrm{Q}_{\mathrm{E}}(f)\) Exact quantum query complexity | \(\Omega(k^{d/3}),\ O(k^{d-1})\ (d \ge 6)\) | $\mathrm{Q}\le\mathrm{Q}_0\le\mathrm{Q}_{\mathrm{E}}\le\mathrm{D}$, with $\mathrm{Q}=\Theta(k^{d/3})$ and $\mathrm{D}=\Theta(k^{d-1})$. |
| \(\mathrm{PostQ}_{\varepsilon}(f)\) Post-selected quantum query complexity | \(O(k^{d/3})\ (d \ge 6)\) | Post-selection can only help, so $\mathrm{PostQ}\le\mathrm{Q}=\Theta(k^{d/3})$. |
| \(\mathrm{prt}_{\varepsilon}(f)\) Partition bound | \(O(k^{d/2})\ (d \ge 4)\) | $\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon$ [JainKlauck10] in the relation setting, and $\mathrm{R}=\Theta(k^{d/2})$ for $d\ge4$. JainKlauck10 |
| \(\overline{\mathrm{prt}}_{\varepsilon}(f)\) Relaxed partition bound | \(O(k^{d/2})\ (d \ge 4)\) | $\overline{\mathrm{prt}}_\varepsilon\le\mathrm{prt}_\varepsilon\le2\,\mathrm{R}_\varepsilon$ [JainKlauck10]. JainKlauck10 |
| \(\mathrm{cjdeg}_{\varepsilon}(f)\) Conical junta degree | \(O(k^{d/2})\ (d \ge 4)\) | $\mathrm{cjdeg}_\varepsilon\le\mathrm{R}_\varepsilon$ (\(\mathrm{cjdeg}_{\varepsilon}(f)\) vs \(\mathrm{R}_{\varepsilon}(f)\), relation setting). |
| \(\mathrm{DTsize}(f)\) Decision tree size | \(\Omega(k^d)\) putative | Answer counting: for every cell $v$ the table $f(x)=\|x-v\|_1$ has $v$ as its unique local minimum, so all $N=k^d$ cells force distinct leaves. |