Q The Query Complexity Zoo
\(\mathrm{D}^{\mathrm{prod}}(f)\)

Product-distribution distributional complexity

Max over product input distributions of the bounded-error distributional query complexity.

Definition

$\mathrm{D}^{\mathrm{prod}}_\varepsilon(f) = \max_{\mu \text{ product}} \mathrm{D}^{\mu}_\varepsilon(f)$, where $\mathrm{D}^\mu_\varepsilon(f)$ is the least depth of a deterministic tree that errs with probability $\le\varepsilon$ under $\mu$. By Yao's minimax $\max_{\mu} \mathrm{D}^\mu_\varepsilon = \mathrm{R}_\varepsilon$ over all $\mu$; restricting to product $\mu$ gives a (possibly much) smaller measure.

Parameters

\(\varepsilon\) (eps) default \(1/3\)

error probability under the distribution

Basic facts

  • $\mathrm{D}^{\mathrm{prod}}(f) \le \mathrm{R}(f)$.
  • $\mathrm{RS}(g) = \tilde\Omega(\mathrm{D}^{\mathrm{prod}}(g))$ for total $g$, hence $\mathrm{R}(f\circ g^n) = \tilde\Omega(\mathrm{R}(f)\,\mathrm{D}^{\mathrm{prod}}(g))$ [Sanyal24].
  • Product distributions genuinely miss hardness: on the balanced \(\bar{\wedge}\text{-tree}\), $\mathrm{D}^{\mathrm{prod}} = O(N^{0.698})$ against $\mathrm{R} = \Theta(N^{0.754})$ [Sanyal24]. Whether $\mathrm{R}$ is polynomially bounded by $\mathrm{D}^{\mathrm{prod}}$ at all is open (\(\mathrm{R}_{\varepsilon}(f)\) vs $\mathrm{D}^{\mathrm{prod}}$).
  • The restriction to total $g$ above is not a technicality. The support of a product distribution is a combinatorial rectangle, and a rectangle sitting inside a promise is usually forced to be one-sided, so $\mathrm{D}^\mu = 0$ for every product $\mu$: this happens at \(\mathrm{forr}\), \(\mathrm{SIMON}_n\), \(\mathrm{BV}_n\), \(\mathrm{COL}_n\) and \(\mathrm{GapMaj}^{\delta}_{n}\). Nothing is bounded in terms of $\mathrm{D}^{\mathrm{prod}}$ on partial functions.

Relations to other measures

A row shows what the zoo knows about the two ordered pairs involving \(\mathrm{D}^{\mathrm{prod}}(f)\). “\(\mathrm{D}^{\mathrm{prod}}(f)\) in terms of it” is the pair with \(\mathrm{D}^{\mathrm{prod}}(f)\) on the left (the matrix row); the other column is the reverse. Each cell gives, per setting, the exponent range a,b of the best bounds known — \(\mathrm{M_1} = \Omega(\mathrm{M_2}^{a})\) below and \(\mathrm{M_1} = O(\mathrm{M_2}^{b})\) above, so \(a = b\) means settled — or a glyph where no polynomial bound exists at all. These are derived, not just read off the exponent table, so they are present for pairs the table does not cover. A cell with no entry for a setting is one where the zoo has nothing at that setting, and a — one where the ordered pair is empty in all three; derived marks a direction with no hand-written relation record behind it, which is the common case and not a hole.

Other measure \(\mathrm{D}^{\mathrm{prod}}(f)\) in terms of it It in terms of \(\mathrm{D}^{\mathrm{prod}}(f)\)
\(\mathrm{R}_{\varepsilon}(f)\) Bounded-error randomized query complexity total1,1 partial1,1 relation1,1 open pair → total1.08,? partial∞ relation∞ open pair →
\(\mathrm{D}^{\mu}_{\varepsilon}(f)\) Distributional query complexity total1,1 partial1,1 relation1,1 derived open pair → total1.08,? partial∞ relation∞ derived open pair →
\(\mathrm{RS}(f)\) Sabotage complexity total1,1 partial1,? open pair → total1,? partial∞ derived open pair →
\(\mathrm{D}(f)\) Deterministic query complexity total1,1 partial1,1 relation1,1 derived open pair → total2,? partial∞ relation∞ derived open pair →

The 4 above are this entry’s hand-picked neighbours; the other 89 are everything else in the zoo, by category.

Known values

FunctionValueNotes
OR total \(\Theta(n)\) Take the product distribution with each bit $1$ independently with probability $1/n$. After seeing $m$ zeros the conditional probability that a $1$ remains is $1 - (1-1/n)^{n-m}$, which is $\ge 1 - e^{-1/2} > 0.39$ for $m \le n/2$; so no depth-$n/2$ tree has error $\le 1/3$. Product distributions are already as hard as OR gets, which is not true for every function.
AND total \(n\) Take $p = 1-1/n$ in the previous line: $\log(1/p) = \Theta(1/n)$, so the bound saturates at $n$. Product distributions are already worst-case-hard for AND.
PARITY total \(n\) The uniform distribution is a product distribution, and $\mathrm{D}^{\mathrm{prod}} \le \mathrm{R} = n$.
MAJORITY total \(\Theta(n)\) putative The uniform distribution is already a product distribution and already hard: after $m$ queries the unseen weight is $\mathrm{Bin}(n-m,\tfrac12)$, whose standard deviation $\tfrac12\sqrt{n-m}$ exceeds the distance to the threshold with constant probability unless $n - m = O(1)$. Unlike \(\mathrm{Tribes}_{w,s}\) or \(\mathrm{ADDR}_k\), majority needs no correlated distribution to be hard.
Threshold total \(\Theta(n)\) putative Take the product distribution with each bit $1$ independently with probability $p$ chosen so that $\Pr[|x| \ge k] = \tfrac12$; this is $p = \Theta(k/n)$. Run a depth-$m$ deterministic tree and follow the single path on which every answer is $0$: it is reached with probability $(1-p)^{m}$, and conditioned on it the residual weight is $\mathrm{Bin}(n-m,p)$, whose chance of reaching $k$ stays bounded away from $0$ and $1$ as long as $m \le \alpha n$ for a small constant $\alpha$. The product of the two is more than $1/3$, so $\mathrm{D}^{\mathrm{prod}} = \Omega(n)$, matching the trivial $\mathrm{D} = n$. Even at $k=1$, where the threshold sits at the very edge, no product distribution is easy.
Symmetric functions (general) total \(\Theta(n)\) putative Take the product distribution with each bit $1$ independently with probability $k/n$, where $k$ is a jump. After $m$ queries the unseen part of the weight is a $\mathrm{Bin}(n-m,k/n)$ variable whose standard deviation is $\Omega(\sqrt{n-m})$, so the conditional probability of landing on either side of the jump stays bounded away from $0$ and $1$ until $n-m = O(1)$. Product distributions are already worst case for symmetric functions.
EXACT-HALF total \(\Theta(n)\) putative Fix $n/2$ coordinates to be $1$ with probability $1$ and give each of the other $n/2$ probability $2/n$. Then $\mathrm{EH} = 1$ exactly when none of the low-probability bits fires, which happens with probability $\to e^{-1} > 1/3$, and deciding that is $\mathrm{OR}$ under its own hard product distribution: after $m$ zeros the conditional probability of a remaining $1$ is still $1 - (1-2/n)^{n/2-m}$. So $m = \Omega(n)$, and product distributions are already worst case.
ODD-MAX-BIT total \(\Theta(n)\) putative Take the product distribution with each bit $1$ independently with probability $c/n$ for a suitable constant $c$. Run a depth-$m$ deterministic tree and follow the path on which every answer is $0$: it is reached with probability $\approx e^{-cm/n}$, and conditioned on it the highest $1$ lies among the $n-m$ unread coordinates, where its index is odd with probability $\tfrac12(1-e^{-c(n-m)/n})$ -- bounded away from $0$ and $1$. For $m \le 0.1n$ the product of the two exceeds $1/3$, so $\mathrm{D}^{\mathrm{prod}} = \Omega(n)$, matching $\mathrm{D} = n$. Unlike its randomized expected cost, which is $O(1)$ under this distribution, the worst-case depth stays linear.
ADDRESS / multiplexer total \(\Theta(k)\) putative Take the uniform distribution. A tree of depth $m$ leaves at least $k-m$ address bits unread, so the addressed entry is uniform over $\ge 2^{k-m}$ candidates of which at most $m$ have been read; for $m \le k/2$ the algorithm identifies it with probability $\le m2^{-k/2}$ and is otherwise flipping a fair coin. Hence $\mathrm{D}^{\mathrm{prod}} = \Omega(k)$, matching $\mathrm{D} = k+1$. (The exact optimum is $k$, not $k+1$: read $k-1$ address bits and one of the two surviving entries, and guess when the address misses -- error $1/4$.)
Binary tree navigation total \(k\) putative Take the uniform (product) distribution. The output is determined only once every one of the $k$ walk nodes has been read, since the last of them is the output bit and the earlier ones are what identify it; so a tree of depth $< k$ leaves an unbiased bit and errs with probability $1/2$. Hence $\mathrm{D}^{\mathrm{prod}} \ge k$, matching $\mathrm{D}^{\mathrm{prod}} \le \mathrm{D} = k$. Product distributions are already worst case for navigation.
TRIBES total \(\Theta(n/\log n)\)· putative Equal to $\Theta(s)$, strictly below $\mathrm{R} = \Theta(n)$: product distributions are provably not worst case for TRIBES. Lower: under the uniform distribution a depth-$m$ tree touches at most $m$ tribes, and each of the $\ge s-m$ untouched tribes is independently all-ones with probability $2^{-w} = \Theta(1/s)$, so for $m = \varepsilon s$ the answer is still an almost-fair coin at every leaf. Upper: for any product distribution, resolve tribes one at a time, querying each tribe's bits in increasing order of $\Pr[x_i=1]$; the expected cost of resolving a tribe with all-ones probability $q_j$ is at most $\sum_{t<w} q_j^{t/w}$, which is $O(1)$ in the only hard regime $q_j = \Theta(1/s)$ (larger $q_j$ makes some tribe satisfied almost surely, smaller makes the answer almost surely $0$). $O(s)$ queries then resolve every tribe except with probability $e^{-\Omega(s)}$. Marked medium confidence because the upper bound is a case analysis over product distributions rather than a single clean argument.
NAND tree (balanced AND-OR formula) total \(O\!\big(N^{\,0.698}\big)\) Strictly below $\mathrm{R} = \Theta(N^{0.753\ldots})$, and this is the only total function for which $\mathrm{R}$ and $\mathrm{D}^{\mathrm{prod}}$ are known to be polynomially apart [Sanyal24, Thm. 1.7]. The tempting argument -- that the Saks-Wigderson lower bound is proved against an explicit product distribution, so it certifies $\mathrm{D}^{\mathrm{prod}}$ -- is wrong, and instructively so: what that distribution certifies is the zero-error cost $\overline{\mathrm{D}_0^{\mu}} = \Theta(\alpha^d)$, $\alpha = (1+\sqrt{33})/4$, and bounded error is cheaper. Knowing $\mu$, run Saks-Wigderson but recurse first on the child likelier to evaluate to $0$ rather than on a random one. Two levels down, independence gives $p_{\ell} \ge (1-\alpha_{\ell})^2$ and the recursion closes at $T(d) \le \max_{x\in[0,1]}(2-x)(1+2x-x^2)\,T(d-2) = \tfrac{2}{27}(17+7\sqrt7)\,T(d-2)$, i.e. base $\sqrt{\tfrac2{27}(17+7\sqrt7)} = 1.62207\ldots$ per level against $\alpha = 1.68614\ldots$. With $N = 2^d$ that is $N^{0.69789\ldots}$. Sanyal does not claim the exponent is tight, so no lower bound is recorded. Sanyal24
FORRELATION partial \(0\) putative The support of a product distribution is a combinatorial rectangle $\prod_i S_i$, and no rectangle inside the promise can meet both sides. Flipping one bit of $x$ or $y$ moves $\Phi$ by at most $2/\sqrt n$, since $|\partial\Phi/\partial x_i| = n^{-3/2}\big|\sum_j (-1)^{i\cdot j}y_j\big| \le n^{-1/2}$. So if the rectangle held a $1$-input ($\Phi \ge 3/5$) and a $0$-input ($|\Phi| \le 1/100$) one could walk between them inside the rectangle one bit at a time, and for $n \ge 16$ some intermediate point -- also in the rectangle -- would have $\Phi$ in the forbidden band $(1/100, 3/5)$, off the promise. Hence every product $\mu$ is one-sided and $\mathrm{D}^\mu = 0$, against $\mathrm{R} = \widetilde\Theta(\sqrt n)$. This collapse is generic for promise problems, not special to forrelation: it recurs at \(\mathrm{SIMON}_n\), \(\mathrm{BV}_n\), \(\mathrm{COL}_n\), \(\mathrm{GapMaj}^{\delta}_{n}\) and \(\mathrm{ApproxIndex}_k\), and it is why $\mathrm{RS}(g) = \widetilde\Omega(\mathrm{D}^{\mathrm{prod}}(g))$ is stated only for total $g$.
Simon's problem partial \(0\) putative The support of a product distribution is a rectangle $\prod_i S_i$ of oracle functions, and no rectangle inside the promise meets both sides. Suppose it held a $1$-$1$ function $g$ and a two-to-one function $h$, and let $h(i) = h(j) = v$ with $i \ne j$. The hybrid agreeing with $h$ at $i$ and with $g$ elsewhere lies in the rectangle, so it must be on the promise, which forces it to be $1$-$1$, i.e. $v \notin g(\mathrm{dom} \setminus \{i\})$. But then the hybrid agreeing with $h$ at both $i$ and $j$ and with $g$ elsewhere -- also in the rectangle -- takes the value $v$ exactly twice and every other value once, so it is neither $1$-$1$ nor two-to-one. Hence every product $\mu$ is one-sided and $\mathrm{D}^\mu = 0$, an exponential gap below $\mathrm{R} = \Theta(2^{n/2})$. See \(\mathrm{forr}\) for the general form of this collapse.
Deutsch-Jozsa partial \(\Theta(1)\) At most $\mathrm{D}^\mu = \Theta(1)$ for every $\mu$, and at least one query.
Bernstein-Vazirani partial \(0\) putative The support of a product distribution is a rectangle $\prod_i S_i$ of truth tables. If two truth tables in it differ at position $i$, then copying that one bit from the second into the first gives another point of the rectangle, and a string that differs from a linear function in exactly one place is not linear -- so it is off the promise. Hence any rectangle inside the promise is a single point and $\mathrm{D}^\mu = 0$ for every product $\mu$, against $\mathrm{R} = \Theta(n)$. See the \(\mathrm{forr}\) entry for the general phenomenon.
Two-or-none search partial \(0\) putative The support of a product distribution is a subcube, and a subcube of dimension $k \ge 1$ inside the domain would contain points of $k+1$ consecutive Hamming weights, of which at most one lies in $\{0,2\}$. So every product $\mu$ is a point mass and $\mathrm{D}^\mu = 0$, against $\mathrm{R} = \Theta(n)$. See \(\mathrm{forr}\) for the general shape of this collapse.
Marked bit partial \(0\) putative Every subcube inside the promise is monochromatic, so no product distribution is hard at all. If a subcube held a $1$-input and a $0$-input then some $y_b$ and some $z_c$ would both be free in it, and the subcube would also contain the point with $y_b = z_c = 1$ -- marks of both colours if $b \ne c$, the invalid encoding $11$ if $b = c$, and off the domain either way. Against $\mathrm{R} = \Theta(n)$; see \(\mathrm{forr}\).
Dense marked bit partial \(0\) putative Every subcube inside the promise is monochromatic, by the argument on \(\mathrm{MARK}_n\): a subcube holding both a $1$-input and a $0$-input has some $y_b$ and some $z_c$ free, hence also contains the point setting both to $1$ -- marks of two colours, or the invalid encoding $11$, and off the domain either way.
Unstructured search (relation) relation \(\Theta(n)\) putative Even a product distribution is hard: set each bit to $1$ independently with probability $1/n$. After $q$ all-zero answers each unqueried coordinate is still $1$ with probability $\approx 1/n$, so answering $\bot$ errs with probability $\approx (n-q)/n$ and naming an unqueried index does worse; hence $q = \Omega(n)$. And $\mathrm{D}^{\mathrm{prod}} \le \mathrm{R} = \Theta(n)$.
FIND-1 under a density promise relation \(\Theta(1)\) At most $\mathrm{D}^\mu = \Theta(1)$ for every $\mu$, hence in particular for product ones; and at least one query.
Approximate Hamming weight relation \(\Theta(1)\) At most $\mathrm{R} = \Theta(1)$ by Yao, and at least one query.
SearchCNF relation \(\Theta(1)\) At most $\mathrm{D}_\mu = \Theta(1)$.
Gap-Majority partial \(0\) putative The support of a product distribution is a subcube: some coordinates are fixed, the rest free. If the fixed part has weight $w$ and there are $m$ free coordinates, the weights realised in the subcube are exactly the integers in $[w, w+m]$, an unbroken interval. Meeting both sides of the promise would mean the interval contains a weight $\le n/2 - \delta n$ and a weight $\ge n/2 + \delta n$, hence also every weight strictly between -- and those points are off the promise. So every product $\mu$ is one-sided and $\mathrm{D}^\mu = 0$, against $\mathrm{R} = \Theta(\min(n, 1/\delta^2))$. See \(\mathrm{forr}\).
Gap-Majority at constant gap partial \(0\) putative The support of a product distribution is a subcube, whose realisable Hamming weights form an unbroken interval; an interval meeting both sides of the promise would have to contain the forbidden middle. So every product $\mu$ is one-sided.
Parity-labelled FIND-1 partial \(0\) putative The support of a product distribution on $\{0,1\}^n$ is a subcube, and the domain here contains no subcube of dimension $\ge 1$: flipping any single coordinate breaks $|x| = n/4$. So every product $\mu$ supported on the promise is a point mass, hence one-sided, and $\mathrm{D}^\mu = 0$ -- against $\mathrm{R} = \Theta(1)$ the measure is simply blind, as at \(\mathrm{GapMaj}^{\delta}_{n}\) and \(\mathrm{forr}\).
Approximate index partial \(0\) putative A rectangle inside the promise is a single input. First the address is pinned: if inputs $(a,x)$ and $(a',x')$ with $a \ne a'$ both lay in the rectangle, so would $(a, x')$, and $x'$ marks the ball around $a'$, a different set of cells from the ball around $a$. With $a$ fixed, the array is pinned too: every one of the $\binom{k}{\le k/2 - 2\sqrt{k\log k}}$ cells in the ball must hold the same bit, so a rectangle with even one free array coordinate contains an input where two ball cells disagree. Hence $\mathrm{D}^\mu = 0$ for every product $\mu$, against $\mathrm{R} = \Theta(\sqrt{k\log k})$. See \(\mathrm{forr}\).
Collision problem partial \(0\) putative Exactly the argument recorded at \(\mathrm{SIMON}_n\): a rectangle $\prod_i S_i$ of functions that contains a $1$-$1$ function $g$ and a two-to-one function $h$ also contains the hybrids that copy one, then two, of $h$'s colliding positions into $g$, and one of those two hybrids has exactly one repeated value -- neither $1$-$1$ nor two-to-one, hence off the promise. So every product distribution inside the promise is one-sided and $\mathrm{D}^\mu = 0$, against $\mathrm{R} = \Theta(\sqrt n)$. Contrast \(\mathrm{ED}_n\), the total version, where the uniform product distribution gives $\mathrm{D}^{\mathrm{prod}} = \Theta(n)$: the promise, not the collision structure, is what kills the measure.
Element distinctness total \(\Theta(n)\) putative Upper: $\mathrm{D}^{\mathrm{prod}} \le \mathrm{R} = O(n)$. Lower: take $\mu$ to be $n$ independent uniform symbols from an alphabet of size $n^2$ -- a product distribution. By the birthday bound the input is all-distinct with probability $e^{-1/2} + o(1)$, so both answers have constant mass, and because the coordinates are i.i.d. adaptivity is useless: after $q$ symbol-reads the algorithm has seen a collision with probability at most $\binom{q}{2}/n^2$, and otherwise its posterior is the same as at the start. Erring with probability $\le 1/3$ therefore needs $q = \Omega(n)$. This is worth recording because $\mathrm{D}^{\mathrm{prod}}$ can be far below $\mathrm{R}$ -- a collision is a correlation between two coordinates, which product distributions cannot plant on purpose, yet the birthday paradox plants one for free.
Ambainis-Belovs function partial \(O(n)\) At most $\mathrm{R} = O(n)$. Unlike \(\mathrm{forr}\) the promise does not force $\mathrm{D}^{\mathrm{prod}} = 0$: two inputs of opposite value can differ in a single variable, so a rectangle inside the promise can meet both sides.
Ben-David-Kundu total search problems relation \(\widetilde\Omega(\sqrt n)\) The hard distribution of [BenDavidKundu24search, Thm 39] is the uniform distribution on $t$ independent blocks, which is a product distribution, and a deterministic tree is in particular a quantum algorithm. So the restriction to product distributions costs nothing here: $\mathrm{D}^{\mathrm{prod}} = \widetilde\Omega(\sqrt n)$, and combined with $\mathrm{RS}(g) = \widetilde\Omega(\mathrm{D}^{\mathrm{prod}}(g))$ this makes the problem hard to use as an inner function in a composition.
Yamakawa-Zhandry problem relation \(2^{\Omega(n)}\) The classical lower bound is proved against a uniformly random oracle, which is a product distribution, so the hardness needs no correlated hard distribution at all: $\mathrm{D}^{\mathrm{prod}} = 2^{\Omega(n)}$. YamakawaZhandry22
Surjectivity total \(\Theta(n)\)· putative Upper: $\mathrm{D}^{\mathrm{prod}}\le\mathrm{R}=\Theta(n)$ (also $\widetilde O(\mathrm{RS})$ [Sanyal24]). Lower: point masses are product measures, so fix slots $1,\dots,R-1$ to the values $1,\dots,R-1$ and give each of the remaining $R+1$ slots independent bits, each $1$ with probability $1-1/\log_2 R$ except the last, which is $1$ with probability $e/(R+1)$. Then a free slot equals the one uncovered value (the all-ones codeword) with probability $1/(R+1)$, so the answer is balanced, and resolving one free slot costs $\Theta(\log R)$ bits in expectation because a $0$ is rare. Any tree must resolve a constant fraction of the $R+1$ slots, giving $\Omega(R\log R)=\Omega(n)$. Sanyal24
$k$-distinctness total \(\Theta(n)\)· putative Upper: $\mathrm{D}^{\mathrm{prod}}\le\mathrm{R}=\Theta(n)$. Lower: fix (point masses are product measures) $n/2$ symbols as $m=n/(2(k-1))$ groups of $k-1$ copies of distinct values $a_1,\dots,a_m$; let free symbol $j$ independently be $a_{j\bmod m}$ with probability $1/M$ and otherwise a private value $b_j$ used nowhere else, where $M=n/2$. No accidental collision is possible, so the instance is a $1$-input exactly when some free symbol picks its $a$, an $\mathrm{OR}$ of $M$ independent events of probability $1/M$. Any tree that leaves a constant fraction of the free symbols unread errs with constant probability, so $\mathrm{D}^\mu=\Omega(n)$. Alphabet size $m+M=O(n)$ suffices.
Triangle finding total \(\Theta(m^2)\)· putative Upper: $\mathrm{D}^{\mathrm{prod}}\le\mathrm{R}=\Theta(m^2)$. Lower: the Erdos-Renyi measure $G(m,c/m)$ is a product distribution on the edge slots, and $c$ can be chosen so that a triangle exists with probability $1/2$. A tree of depth $\varepsilon m^2$ leaves a pair set that still spans $(1-3\varepsilon)\binom m3$ triples, each independently present with probability $c^3/m^3$, so conditioned on any transcript the posterior probability of a triangle in the unread part stays bounded away from $0$ and $1$.
Fourier fishing relation \(\Omega(N/\log N),\ O(N)\)· putative Sharper than the generic $\mathrm{D}^{\mathrm{prod}} \le \mathrm{R}$ would give. [AaronsonChen17, Thm. 6.4] argues against a uniformly random truth table, and the uniform distribution on $\{-1,1\}^N$ is a product distribution; the only caveat is that it is the uniform distribution conditioned on the promise, an event of probability $1-o(1)$, which is no longer literally a product. So the lower bound survives the restriction to product $\mu$ up to that conditioning.
Ordered search partial \(1\) putative The support of a product measure is a subcube, and a subcube inside the promise has dimension at most $1$: a $2$-dimensional subcube contains two inputs of equal Hamming weight, and the chain has none. A $1$-dimensional one is a pair $x^{(k)},x^{(k+1)}$ differing in coordinate $k+1$, which one query settles, and the balanced such measure needs that query. So $\mathrm{D}^{\mathrm{prod}}=1$ while $\mathrm{R}=\Theta(\log n)$ -- product distributions are useless on a chain promise.
Tseitin search on an expander relation \(\Theta(1)\) putative Constant against $\mathrm{R} = \Theta(n)$: the hard distribution for Tseitin must be correlated, and $O(1)$ queries suffice against any product $\mu$. Write $t_e = 1-2\Pr_\mu[x_e=1]$ and $T_v = (-1)^{\chi(v)}\prod_{e \ni v} t_e$, so that $\Pr_\mu[v \text{ violated}] = (1-T_v)/2$. Every edge meets exactly two vertices, so $\prod_v T_v = (-1)^{\sum_v \chi(v)}\prod_e t_e^2 = -\prod_e t_e^2 \le 0$, and therefore some $v^*$ has $T_{v^*} \le 0$, i.e. is violated with probability $\ge 1/2$. Query its $d = O(1)$ edges. If it is not violated, delete $v^*$ and fold the revealed bits into the charges of its neighbours: the residual instance on $G - v^*$ has total charge $\sum_v \chi(v) + \sum_{e \ni v^*} x_e \equiv \sum_v \chi(v)$, still odd, and the unqueried edges are still independent. Two rounds leave error $\le 1/4$, so $\mathrm{D}^{\mathrm{prod}} \le 2d = O(1)$.
Inner product mod 2 total \(\Theta(n)\) putative The uniform distribution is already hard, and it is a product distribution. A depth-$d$ tree leaves at least $m-d$ index pairs $(x_i,y_i)$ entirely free, and conditioned on any leaf the value is the XOR of that many independent $\mathrm{Bernoulli}(1/4)$ terms, whose bias is $2^{-(m-d)}$; error $\le 1/3$ therefore forces $d \ge m-1 = n/2 - 1$. Upper: $\mathrm{D}^{\mathrm{prod}} \le \mathrm{R} = \Theta(n)$.
Minsky-Papert one-in-a-box total \(\Omega(m^3/\log m),\ O(m^3)\)· putative Lower: take each leaf independently $1$ with probability $p$ chosen so that each $\mathrm{OR}_{m^2}$ is $0$ with probability $q = \ln 2/m$, i.e. $p = \Theta(\log m / m^2)$; then $\mathrm{AND}$ is $1$ with probability $\tfrac12$, so the answer is balanced. Resolving one box costs $\approx 1/p = \Theta(m^2/\log m)$ queries in expectation, and leaving $t$ boxes unresolved leaves error $\approx tq$, so at least $m/2$ boxes must be resolved: $\mathrm{D}^{\mu} = \Omega(m^3/\log m)$. Upper: $\mathrm{D}^{\mathrm{prod}} \le \mathrm{R} = \Theta(m^3)$. The log is probably real and cannot be argued away by the tempting route -- the classical $\Omega(mb)$ lower bound is proved against a correlated distribution (one planted $1$ per box), not a product one, and \(\bar{\wedge}\text{-tree}\) shows that at growing depth the analogous gap is not a log but a polynomial [Sanyal24]. At depth $2$ the saving compounds only once, which is why it stays logarithmic here. Sanyal24
Sink of a tournament total \(\Theta(m) = \Theta(\sqrt N)\) putative Product distributions lose nothing here. Upper: $\mathrm{D}^{\mathrm{prod}} \le \mathrm{R} = \Theta(m)$. Lower, by the same $\mathrm{AND}_{m-2}$ restriction as \(\mathrm{noisyR}(f)\) -- restricting is legal because a product distribution on the free variables extends to a product distribution with point masses on the fixed ones -- together with $\mathrm{D}^{\mathrm{prod}}(\mathrm{AND}_k) = \Theta(k)$: take each bit $1$ independently with probability $1-1/k$, so that after $d$ observed ones the conditional probability of $\mathrm{AND} = 1$ is $(1-1/k)^{k-d}$, which stays in $[e^{-1}, e^{-1/2}]$ until $d \ge k/2$ and therefore keeps the error above $1/3$.
Scorpion graphs total \(\Theta(m) = \Theta(\sqrt N)\) putative The same $\mathrm{AND}_{m-3}$ restriction as \(\mathrm{noisyR}(f)\), with $\mathrm{D}^{\mathrm{prod}}(\mathrm{AND}_k) = \Theta(k)$ (each bit $1$ independently with probability $1-1/k$; see the \(\mathrm{SINK}_m\) entry), against the ceiling $\mathrm{D}^{\mathrm{prod}} \le \mathrm{R} = \Theta(m)$. Note the contrast with $\mathrm{D}$: the scorpion property is $\Theta(m)$-easy deterministically too, so unlike \(\mathrm{CONN}_m\) there is nothing for randomness or for a product distribution to exploit.
Graph connectivity total \(\Theta(m^2) = \Theta(N)\) putative Product distributions are worst-case here. Upper: $\mathrm{D}^{\mathrm{prod}} \le \mathrm{R} = \Theta(m^2)$. Lower: split the vertices into halves $A$ and $B$ and fix every edge inside $A$ and inside $B$ to be present. The graph is then connected iff at least one of the $\lfloor m^2/4\rfloor$ free $A$-$B$ edges is present, i.e. the restriction is $\mathrm{OR}_{\lfloor m^2/4\rfloor}$, and $\mathrm{D}^{\mathrm{prod}}(\mathrm{OR}_k) = \Theta(k)$: take each bit $1$ independently with probability $1/k$, so that after $d$ observed zeros the conditional probability of $\mathrm{OR} = 1$ is $1-(1-1/k)^{k-d}$, still above $1/3$ until $d \ge 0.59k$.