← All problems

Randomized query-composition product conjecture

For all positive integers m,nm,n and all total Boolean functions f:{0,1}m→{0,1}f:\{0,1\}^{m}\to\{0,1\} and g:{0,1}n→{0,1}g:\{0,1\}^{n}\to\{0,1\}, define (f∘g)(x(1),…,x(m))=f(g(x(1)),…,g(x(m)))(f\circ g)(x^{(1)},\ldots,x^{(m)})=f\bigl(g(x^{(1)}),\ldots,g(x^{(m)})\bigr), where each x(i)∈{0,1}nx^{(i)}\in\{0,1\}^{n}. Then the bounded-error randomized query complexity satisfies R(f∘g)=Ω(R(f)R(g))R(f\circ g)=\Omega\bigl(R(f)R(g)\bigr).

References

Source: arXiv

Progress summary

Refreshed
Open · solution reported

An October 2026 preprint claims a counterexample to the exact product rule for composing two total Boolean functions, but the claim has not been independently checked.

The conjecture asks whether randomized query complexity obeys an exact product lower bound under composition of total Boolean functions. Earlier work established strong substitutes and settled related partial-function cases, but not this total-total statement.

Known results

  • Sanyal, 2024: for a relation ff and total Boolean gg, R(f∘gn)=Ω~(R(f)Dprod(g))\mathrm{R}(f\circ g^n)=\widetilde{\Omega}(\mathrm{R}(f)D^{\mathrm{prod}}(g)).
  • Gavinsky, Lee, Santha, Sanyal, 2022: linearized complexity gives R(f∘g)≥Ω(R(f)LR(g))\mathrm{R}(f\circ g)\ge\Omega(\mathrm{R}(f)\mathrm{LR}(g)).
  • Ben-David and Kothari, 2016: sabotage complexity gives R(f∘g)=Ω(R(f)RS(g))\mathrm{R}(f\circ g)=\Omega(\mathrm{R}(f)\mathrm{R_S}(g)).
  • 2020 work: the direct product conjecture is false for partial Boolean functions.

October 2026 counterexample

On October 22, 2026, Alexander Meiburg's unrefereed preprint No Perfect Randomized Composition claimed a total-total counterexample, along with separations among related complexity measures. This would disprove the conjecture, but the retrieved evidence supplies no independent mathematical assessment.

Current status (as of October 2026): The total-total product conjecture is claimed false by Meiburg's preprint, but that counterexample.

Sources

Solutions 0

No solutions have been posted yet.