PaperlayerView exact revision on arXiv

Source-linked AI summary

No Perfect Randomized Composition

Alexander Meiburg

arXiv:2610.31638v1cs.CCmath.CO

TL;DR

The paper asks whether randomized query complexity of a composition of total Boolean functions must match the product of the factors’ complexities. It constructs total-function separations involving linearised and noisy randomized complexity, and shows that composition can save Θ(log R(g)) over that product.

  • Problem

    The question is whether randomized query complexity for composing total Boolean functions must be at least a constant times the product of the factors’ complexities.

    Source: §1 · p. 1

  • Method

    The paper develops total-function constructions that separate randomized complexity from linearised and noisy randomized query complexity, then combines the mechanisms for composition.

    Source: §1 · p. 2, §4.4 · p. 16, §8 · p. 34

  • Results

    Θ(log R(g)) is the saving relative to the product in the total–total composition separation.

    Source: §1 · pp. 1–2

  • Takeaways & Limitations

    The total–total result rules out a universal constant-factor randomized composition lower bound.

    Source: §1 · pp. 1–2

    The saving does not rule out a lower bound of eΩ(R(f)R(g)), and its optimality is established for the inner family, not for all compositions.

    Source: §11 · p. 54

Abstract

from arXiv · show

Does computing a composition of total Boolean functions require the product of the randomized query complexities of its factors? We give a negative answer. There are families of total functions $f,g$ such that $R(f\circ g) =\Theta\!\left(\frac1{\log R(g)}\right)R(f)R(g)$ This result requires first separating linearized query complexity $\LR$, as well as noisy randomized query complexity $noisyR$, from standard randomized query complexity $R$. Both constructions essentially come from totalizing existing partial function separations, albeit via different techniques. By adapting these techniques, we also construct total functions separating every adjacent pair in the chain from sabotage $RS$, max-conflict $\bar{\chi}$, and linearised query complexity $LR$. We show that AND-of-ORs separates conflict $\chi$ from max-conflict $\bar{\chi}$ complexity and makes conflict and sabotage incomparable. Finally, randomized complexity can be smaller than its composition limit $R^*$ by the maximal factor $\Theta(\log R)$. The total--total composition separation is also formalized in Lean.

1 Introduction

The paper answers the total-function randomized composition question negatively, with a saving of Θ(log R(g)) relative to the product of the factors’ complexities. It also gives total-function separations among query-complexity measures and studies how repeated composition compares with one-level complexity.

1 Introduction

  • A total–total composition can save Θ(log R(g)) relative to the product of the factors’ randomized query complexities.The paper states that requiring both functions to be total does not restore the composition inequality.Source: §1 · pp. 1–2
  • The construction combines an inner exact detector with a total outer function that stores independently encoded certificates at address-indexed cells.The inner function is a majority of encoded pointer functions; the outer construction makes short transcripts independent of decoded payloads and permits exact certificate checking after an approximate address is found.Source: §1 · pp. 2–3
  • Every adjacent comparison in the chain from sabotage through max-conflict and linearised complexity is strict on total functions.The parity, majority, and masking constructions produce gaps of Ω(log N), Ω(log N), and Ω(√log N), respectively.Source: §1 · p. 3
  • For AND-of-ORs, sabotage and max-conflict are maximal, while each opposite-output pair admits a cheaper conflict tree.Together with the parity family, this makes sabotage and conflict incomparable and separates conflict from max-conflict on total functions; it also yields a failure of perfect composition for conflict.Source: §1 · pp. 3–4
  • A cyclic rotation of compositions gives a total family whose composition limit exceeds its one-level complexity by the maximal Θ(log R) factor.This is a different direction of separation from the single-composition result.Source: §1 · p. 4
  • The total–total randomized composition separation is checked in Lean 4.The paper also uses Lean to formalize its main result.Source: §1 · p. 4

2 Preliminaries

The preliminaries define randomized query complexity and the auxiliary measures used to compare algorithms and establish lower bounds. They also introduce the encoded pointer block that supplies the paper’s constructions.

2.1 Notation

  • Randomized query complexity is defined through bounded-error decision trees, with constant-error worst-case depth and expected-cost versions equivalent up to constants.At smaller error rates, the two versions can differ, so bounds specify which one they use.Source: §2.1 · p. 4

2.2 Sabotage complexity

  • Sabotage complexity is the zero-error expected cost of finding a wildcard in an input consistent with both a 0-input and a 1-input.The wildcard set may exceed the coordinates on which the two consistent inputs differ.Source: §2.2 · p. 4

2.3 Conflict complexity

  • Conflict and max-conflict complexity differ in the outer maximization: max-conflict allows ensembles of distribution pairs, while conflict uses a single pair.Conflict is at most max-conflict, and the paper reports a total-function separation between them.Source: §2.3 · p. 5

2.4 Linearised complexity

  • Linearised complexity minimizes worst-input cost divided by positive signed bias, and supports the lower bound R(f ◦ g) = Ω(R(f) LR(g)) for partial functions.Its upper-bound certificates require bias bounded below uniformly on every input.Source: §2.4 · pp. 5–6

2.5 Hard pairs at every budget

  • Hellinger-hard pairs yield a bound that applies to every randomized decision tree, controlling distinguishing advantage across query budgets rather than only at bounded error.The paper uses the mixture cost as the cost term because it is at least the minimum of the two distribution-specific costs.Source: §2.5 · p. 6

2.6 The Blais–Brody block

  • The total pointer block gq has input length mq = Θ(q^3 log q) and randomized complexity Tq = Θ(q^2 log q), while its 1-certificates can be checked from O(q) cells.The encoding is resilient, and amplification is necessary for the stated error range.Source: §2.6 · p. 7

3 Exact detectors separate LR from R

The section builds an exact detector for the pointer block and uses it to separate linearised from standard randomized query complexity. The resulting majority family also supplies a composition construction with a total inner function, with a gap that depends on the composed input length.

3 Exact detectors separate LR from R

  • For majority, a cheap one-sided test on a randomly chosen block gives bias with the correct sign when its acceptance rate is constant across 1-inputs.This is the weak evaluator constructed for the inside of the composition.Source: §3 · p. 7

3.1 The detector lemma

  • A detector with acceptance probability zero on 0-inputs and the same constant probability on every 1-input gives majority a uniformly correct signed bias after affine correction.Exactness is essential: a varying acceptance rate on 1-inputs prevents one affine correction from calibrating both boundary layers.Source: §3.1 · pp. 7–8

3.2 A detector for the pointer block

  • The pointer-block detector has worst-case cost O(Cq q) and accepts a 1-input exactly when the sampled column is one of its (q − 1)/2 good columns.Its closing check verifies the pointer conditions using cells it has read, yielding zero false accepts.Source: §3.2 · pp. 8–10

3.3 The separation

  • LR(Mq) = O(mq) while R(Mq) = Θ(mq log q), separating linearised from randomized complexity on a total majority family.The family has Nq = Θ(q^4 log q) input bits.Source: §3.3 · p. 10

3.4 Composition with a total inner function

  • The construction gives a partial outer function and a total inner function, with a gap of only Ω(log log M) measured against the composed input length M.The natural-parameter gap is Ω(log q); the composed input length is M ≍ m^2K.Source: §3.4 · p. 11

4 A total separation between noisy and ordinary queries

This section develops a separation between noisy and ordinary randomized query complexity for total Boolean functions, with noisy complexity asymptotically smaller as input length grows. It also presents a noisy construction that isolates the outer-function task using weak-information evaluation, cheap exact certificates, and a persistent ordinary-query lower bound.

4 A total separation between noisy and ordinary queries

  • R(Wq)/noisyR(Wq) = Ω(q/log log(q + 2)), yielding Ω((log Nq)^1/4/log log log Nq) for sufficiently large q, where log Nq = Θ(q^4).The construction has log Nq = Θ(q^4).Source: §4 · p. 11, §4.4 · p. 17

4.1 The seed and its hard distribution

  • The seed has a noisy algorithm of cost 400q^2 + 1, while its hard distribution bounds ordinary algorithms’ chance of querying an inside-ball table location.The ordinary-query bound applies to adaptive algorithms on E(a, z) with a uniform address.Source: §4.1 · p. 12

4.2 A core with cheap certificates

  • The core has noisyR_{1/100}(Sq) = O(u^2q^2), while under µq every ordinary-query tree of depth at most u^2q^3 succeeds with probability at most 5/8.The robust AND-of-ORs evaluation achieves error at most 1/100 with a worst-case cost bound.Source: §4.2 · pp. 13–14

4.3 Private cells and a list direct-product bound

  • Fibers of a surjective linear encoding have identical uniform marginals on any at-most-12a coordinates, and the list direct-product bound also holds for randomized trees.The encoding also supports total decoding of an alphabet of size at most 2^a from 36a bits.Source: §4.3 · pp. 14–15

4.4 The total certificate function

  • Wq is total: it accepts when some addressed cell has a flag and witnesses verifying every core answer, and noisyR(Wq) = O(c log(c + 2)u^2q^2).A malformed core causes rejection at every address.Source: §4.4 · p. 16

4.5 Comparison with the linearised separation

  • LR buys biased ordinary answers at cost divided by output bias, whereas noisyR pays squared query correlations yet still requires constant-success function evaluation.Ordinary amplification of output bias δ can require order 1/δ^2 repetitions; weak information loses value when intermediate answers must be reliable.Source: §4.5 · p. 17
  • Many weak address samples locate a table entry in a large Hamming ball for exact one-cell verification, while private encoding blocks cheap exploratory reads.Robust AND-of-ORs raises ordinary cost more than certificate cost, and the certificate array turns the promise algorithm into a total algorithm.Source: §4.5 · p. 17
  • Neither separation alone yields a total–total composition counterexample: known bounds [8] [6] require inner LR-vs-R and outer noisyR-vs-R gaps, plus weak-sample implementation and affordable exact verification.The construction isolates the outer task with a total function having fast weak-information evaluation, cheap exact certificates, and an ordinary lower bound that persists despite the certificate array.Source: §4.5 · p. 17

5 Failure of perfect composition for total functions

This section develops a total–total separation showing that perfect randomized composition can fail for nonconstant total Boolean functions. It builds and lower-bounds an inner function, uses a composed-seed algorithm to obtain the separation, and describes the scope of its Lean certificate.

5 Failure of perfect composition for total functions

  • Explicit nonconstant total Boolean functions Wq and cMq show that perfect randomized composition can fail even when both factors are total.The construction uses certificates of Wq to convert an algorithm for a partial composition into one for a total composition.Source: §5 · pp. 17–18

5.1 The total inner function and its weak evaluator

  • The total inner function has a weak evaluator using at most (6q + 2)bCq queries whose signed bias is at least 1/(5q).Its exact detector accepts precisely when a uniformly chosen column is one of the (q −1)/2 good columns; verification gives perfect soundness.Source: §5.1 · pp. 19–20
  • Determining all q pointer-block values by repeated exact detection gives R(cMq) = O(bq q^2 log q).The section applies the inner-composition bound R(F ◦g) = Ω(R(F) LR(g)) to establish the final assertion for this inner family.Source: §5.1 · p. 20

5.2 A self-contained lower bound for the inner function

  • For q = 2s −1 and s ≥1000, every full-cell algorithm of depth at most T from (24) succeeds with probability at most 3/5 under a fixed distribution on inputs to Majq ◦Πq.An independent 36b-bit private encoding yields R ≥(T + 1)(12b + 1).Source: §5.2 · pp. 23–24
  • An encoding argument transfers a cell-query lower bound to c Mq by hiding each symbol until 12b + 1 distinct bits in its cell are exposed.The encoded function is exactly c Mq after flattening its coordinates.Source: §5.2 · p. 24

5.3 A fast algorithm for the composed seed

  • The partial composition pq ∘c Mq has error at most 1/(100q^2), and its worst-case cost bound also holds outside the seed promise.The algorithm estimates the address with weak evaluators, then fully reads the inner block for the selected value bit.Source: §5.3 · pp. 24–25

5.4 From the composed core to the total composition

  • The total-total construction achieves a Θ(log log Lq) = Θ(log R(c Mq)) factor saving over the product of the factors’ randomized query complexities.The paper states that replacing the outer function cannot yield a larger asymptotic saving with this inner family.Source: §5.4 · p. 27

5.5 The machine-checked formulation

  • The Lean certificate proves a total–total little-o composition separation for ordinary randomized query complexity on a subsequence, but not the sharper Θ(1/s) rate.That sharper rate uses the small-error robust evaluator and matching linearised lower bound, which are not part of the certificate.Source: §5.5 · pp. 27–28

6 Sabotage does not pay for amplification

Sabotage complexity can avoid the amplification cost that makes randomized evaluation of composed functions more expensive. A block-by-block scan yields a logarithmic separation between sabotage and randomized query complexity for a total parity family.

6 Sabotage does not pay for amplification

  • A sabotage scan for Φ ◦ g^k can achieve RS(Φ ◦ g^k) ≤ kT/(1−2ϵ) using an evaluator for g with error ϵ and expected cost T.It scans blocks in turn, stopping when it finds a wildcard; independent repeated scans give a zero-error procedure.Source: §6 · p. 28
  • The scan succeeds because a witness block has differing completions, so if both coupled evaluations are correct, its simulation must encounter a wildcard.A union bound gives probability at least 1−2ϵ that both evaluations are correct; the argument does not require independence.Source: §6 · p. 28
  • The scan needs only to disturb a block, not identify it or compute its value, and its guarantee does not depend on the outer function Φ.This is why the scan avoids paying for reliable evaluation of every block.Source: §6 · p. 28
  • RS(Pq) = O(mq) while R(Pq) = Θ(mq log q), giving R(Pq) / RS(Pq) = Ω(log Nq).Here Pq is the total function XORq ◦ gq^q on Nq = Θ(q^4 log q) bits.Source: §6 · p. 29
  • The parity family rules out a constant-factor bound of randomized complexity by sabotage complexity, but its logarithmic gap does not settle whether the two agree up to e^Θ.The paper connects the randomized logarithm to amplification, while sabotage avoids that cost; this section refutes only the constant-factor form.Source: §6 · p. 29

7 The parity family separates RS from χ

The parity family separates sabotage from conflict complexity by combining hidden-row distributions with a posterior-based lower bound that survives encoded queries. For k = q, sabotage is O(mq), while conflict, max-conflict, linearised, and randomized complexities are Θ(mq log q).

7.1 The hard distributions

  • The hard distributions make missed hidden cells have likelihood ratio 1, while their hidden-row structure yields 0-inputs under μ0 and 1-inputs under μ1.The parity construction combines these block distributions so that νb is supported on inputs with parity b.Source: §7.1 · pp. 29–30

7.2 From posteriors to conflicts

  • For a deterministic transcript tree, posterior bias is a bounded martingale, and conflict mass is controlled by accumulated posterior variance.When the tree separates the two supports, the lemma converts a small expected squared posterior bias at depth t into expected conflict-walk depth at least t/2.Source: §7.1 · p. 30, §7.2 · pp. 30–31
  • Conflict complexity can increase when one alphabet-symbol query is refined into bit queries, so a direct lift of an alphabet-level conflict bound is unavailable.In the example, survival falls from 0.60 for one four-way query to 0.48 for sequential bit queries.Source: §7.2 · p. 31

7.3 From bits to cells

  • A bit transcript can be simulated by opening at most ⌈4t/Cq⌉ cells, because resilience makes queried bits in unopened cells independent of their symbols.Once the threshold of distinct encoding-bit queries is reached, the full cell symbol is revealed; the refined transcript is a cell-query process with label-independent randomness.Source: §7.3 · p. 32

7.4 Adaptive hidden-row discovery

  • The hidden-row bound controls adaptive discovery by splitting discoveries into early and late cases, with late discoveries bounded deterministically by 2Q/q.Combining this with the early-discovery estimate gives the posterior control used for the parity-family lower bound; the stated application uses k = q under log k = O(q).Source: §7.4 · pp. 32–33

7.5 The separation

  • For k = q, RS(Pq) = O(mq), while χ(Pq), χ̄(Pq), LR(Pq), and R(Pq) are Θ(mq log q).The lower bound comes from a hard distribution pair; the upper measures coincide through χ ≤ χ̄ ≲ LR ≲ R.Source: §7.5 · p. 34

8 Parity masks separate ¯χ from LR

The paper masks a hard function with long parity to separate max-conflict from linearised complexity. The mask affects the measures differently, and the resulting separation is limited by the one-mask construction.

8 Parity masks separate χ̄ from LR

  • A parity mask makes conflict complexity add at most t + χ̄(h), while linearised complexity must read every mask bit before gaining any bias.The mask is XORed with h; the construction exploits the different responses of the two measures.Source: §8 · p. 34
  • Non-completing mask transcripts have equal probabilities under ν0 and ν1, so they contribute nothing to distinguishing advantage.The proof handles the completing branch without conditioning on completion, because completion depends on answers from the h-input as well.Source: §8 · p. 35
  • The lower bound converts a distributional distinguishing bound into LR by averaging cost and signed bias over the mixture.The resulting bound is LR(Ht) = Ω(tR(h)).Source: §8 · p. 36
  • For Gq, sabotage and max-conflict complexities are Θ(mq), while randomized complexity is Θ(mq log q).The mask length is Θ(mq), smaller than the Mq input, leaving the total input length Θ(q^4 log q).Source: §8 · p. 37
  • The max-conflict-versus-linearised separation is only √log, and the remaining √log q could lie on either side of R(Gq).Within the one-mask template, the ratio peaks at t = Θ(mq), so improving the mask length alone cannot exceed √log q.Source: §8 · p. 37

9 AND of ORs: conflict below sabotage

This section studies how conflict complexity relates to sabotage, max-conflict, and certificate complexity on total functions, using AND-of-ORs and a product-conditioned pair. It establishes separations and incomparability, a Θ(m²/log² m) conflict-cost lower bound, and a failure of perfect conflict composition, while leaving one certificate lower-bound question open.

9 AND of ORs: conflict below sabotage

  • For Fm = ANDm ◦ ORm, RS(Fm)=Θ(m²) while χ(Fm)=O(m²/ln m), and the section establishes that RS and χ are incomparable on total functions.Since max-conflict complexity is at least sabotage complexity, this also separates χ from max-conflict.Source: §9 · p. 37
  • The gap comes from adversarial correlation: sabotage couples the two sides through boundary edges, whereas conflict sees only their separate conditional marginals.The lower-bound mechanism is described as a first-hit harvest of the empty row, which caps the natural hard pair.Source: §9 · p. 38

9.1 A robust OR-row lemma

  • After peeling heavy marginals, one of two row trees—full scan or fixed-order first-hit—achieves conflict probability Ω(a√ln m) per row phase, where a is the posterior empty-row probability.The outer induction pays for the peeling and yields a deterministic tree with conflict cost O(m²/ln m).Source: §9 · p. 38, §9.1 · p. 38

9.3 The lower bound: a product-conditioned pair

  • The lower-bound section uses the simplest hard pair: an i.i.d. bit distribution conditioned on the value of Fm, with p between 2 ln m/m and ln m/m.Under that product distribution, Pr[Fm=1]=(1−1/m)^m, bounded between 1/4 and 1/e.Source: §9.3 · p. 45
  • For the product-conditioned pair, conflict complexity is Θ(m²/log² m), and the fixed-order row scan attains the matching upper bound.The lower bound applies to any tree for the pair; the upper-bound argument needs no independence assumption between successive row phases.Source: §9.3 · p. 47

9.4 Consequences: incomparability, composition, certificates

  • χ and sabotage RS are incomparable on total functions: χ(Pq)/RS(Pq) = Ω(log Nq), while RS(Fm)/χ(Fm) = Ω(√log N).The two separations occur on different functions; χ pays for amplification while RS exploits cross-side coupling.Source: §9.4 · p. 47
  • On Fm, χ is separated from max-conflict complexity by Ω(√log N), with the chain χ ≪ RS ≲ χ̄.The passage notes that the separation cannot exceed quadratic because of the general bounds relating χ, χ̄, and R.Source: §9.4 · p. 47
  • No constant c > 0 guarantees χ(f ◦ g) ≥ cχ(f)χ(g) for all total Boolean f and g.The counterexample uses Fm = ANDm ◦ ORm; on this instance the loss lies between √log m and log² m.Source: §9.4 · p. 48
  • χ(Fm) exceeds certificate complexity C(Fm) by more than a constant factor, while whether χ(f) ≥ Ω(C(f)) for every total function remains open.For Fm, C(Fm) = m; the paper says the known upper bound χ ≤ C0C1 is tight up to a log² factor.Source: §9.4 · p. 48

10 Randomised complexity versus its composition limit

The paper constructs a total family attaining the logarithmic gap between randomized query complexity and its composition limit. It develops noisy-query simulations and a GapMajority transfer to establish the separation.

10.1 Noisy transcripts of resilient encodings

  • A noisy algorithm of expected cost D can be simulated with error at most ϵ + Mη using at most D/a + M2η expected cell openings.The simulation opens a cell when its accumulated noisy-query cost reaches the threshold a.Source: §10.1 · pp. 50–51

10.2 Transferring a small-error bound through GapMajority

  • For every ϵ, noisyRϵ(f) is at most O(Rϵ(f ◦ GapMajb)/b), with the simulation preserving error exactly.Virtual blocks are sampled from fixed-weight distributions; queries are simulated at noisy cost O(1/b) each.Source: §10.2 · p. 52

10.3 A helper and its two rotations

  • D(Aq) = q3, while RS(Aq), max-conflict, LR, and R are all Θ(q3).This helper supports two total compositions on Θ(q6 log q) bits: one evaluates it exactly, while the other forces small-error evaluation of pointer blocks.Source: §10.3 · pp. 52–53
  • The two rotations are total, but their costs differ: one evaluates the helper exactly, while the other forces small-error evaluation of pointer blocks.The contrast is separate from the earlier composition counterexample, which makes one composition cheaper than the product of its factors.Source: §10.3 · p. 53
  • R(Hq) = Θ(q5 log q) while R∗(Hq) = Θ(q5 log2 q), attaining the Θ(log Nq) gap for total Boolean functions.The family has Nq = Θ(q6 log q) input bits.Source: §10.3 · p. 53

10 Randomised complexity versus its composition limit

  • R∗(f) = O(R(f) log R(f)) is tight for total Boolean functions, with R∗(Hq)/R(Hq) = Θ(log Nq).The family has polynomial input length in q.Source: §10 · p. 49, §10.3 · p. 53

11 Discussion

The discussion clarifies the scope of the composition separation and the algorithmic features that make it work. It also identifies open gaps among query-complexity measures and distinguishes single composition from iteration.

How much composition fails

  • The composition loss is Θ(log log L), equivalently Θ(log R(g)), for this construction; the result rules out a constant-factor bound but not an eΩ(R(f)R(g)) lower bound.The authors state that this logarithmic saving is a restriction on the present family, not a general bound on composition savings.Source: §11 · p. 54
  • The inner evaluator supplies independent evidence with a uniform sign, while the outer sampler tolerates varying bias and its verifier’s exact-query cost fits the budget.The construction also relies on a direct-product lower bound for the address.Source: §11 · p. 54

The remaining gaps among measures

  • The parity-mask approach leaves open separating LR from R on the same family as the max-conflict-to-LR separation, and optimizing mask length alone cannot achieve that goal.Its guaranteed ratio is proportional to ptmq log q/(mq + t), maximized at t = Θ(mq).Source: §11 · p. 54
  • For AND-of-ORs, χ(Fm) remains between m2/ log2 m and m2/√log m; neither endpoint calculation determines its value.The lower endpoint is exact for the product-conditioned pair analyzed, while the upper endpoint follows from balancing scan cost against the random-priority estimate.Source: §11 · p. 54
  • Whether χ(f) = Ω(C(f)) for every total f remains open; the paper’s certificate separation concerns the opposite direction [17].Source: §11 · p. 54

Product distributions

  • The explicit distributions use correlation within pointer blocks and between latent labels, but do not establish that every hard distribution for these functions must be correlated.The authors leave open whether such correlation can support a larger separation.Source: §11 · p. 54

Iteration

  • The Θ(log R) maximal gap between R* and R concerns repeated composition, whereas the unbounded saving in Theorem 1.1 concerns one composition of different total functions.The paper does not show R*(f) = o(R(f)) or a comparable saving from composing a function with itself.Source: §11 · p. 54
Loading 2610.31638v1…