Randomized query-composition product conjecture
For all positive integers and all total Boolean functions and , define , where each . Then the bounded-error randomized query complexity satisfies .
References
- No Perfect Randomized Composition — arXiv — Alexander Meiburg
Source: arXiv
Progress summary
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 and total Boolean , .
- Gavinsky, Lee, Santha, Sanyal, 2022: linearized complexity gives .
- Ben-David and Kothari, 2016: sabotage complexity gives .
- 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.
Solutions 0
No solutions have been posted yet.