Eventual multiplicativity of algorithmic complexity under parity-perturbed composition

From papers

For Boolean functions ff on nn bits and gg on mm bits, let fgf\circ g denote their block composition, let PARk\operatorname{PAR}_k be parity on kk bits, let gPARkg\oplus\operatorname{PAR}_k denote the corresponding XOR construction, and let a(h,π1/2)a(h,\pi_{1/2}) be the distributional algorithmic complexity of hh under the uniform distribution.

Composition multiplicativity conjecture. For every n,m1n,m\ge1, there exists k0(n,m)Nk_0(n,m)\in\mathbb N such that, for every Boolean functions ff and gg on nn and mm bits, respectively, and every kk0(n,m)k\ge k_0(n,m),

a(f(gPARk),π1/2)=a(f,π1/2)a(gPARk,π1/2).a\left(f\circ\left(g\oplus\operatorname{PAR}_k\right),\pi_{1/2}\right)=a(f,\pi_{1/2})\cdot a\left(g\oplus\operatorname{PAR}_k,\pi_{1/2}\right).

The conjecture is motivated by the preceding composition theorem and is intended to connect distributional algorithmic complexity with asymptotic separation questions. Its status remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Laurin Köhler-Schindler and Jeffrey E. Steif, “A study of distributional complexity measures for Boolean functions”, arXiv:2408.12995 (2024).

Solutions 0

No solutions have been posted yet.