Eventual multiplicativity of algorithmic complexity under parity-perturbed composition

About 2 years old · traced to

For Boolean functions ff on nn bits and gg on mm bits, let f∘gf\circ g denote their block composition, let PAR⁡k\operatorname{PAR}_k be parity on kk bits, let g⊕PAR⁡kg\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,m≥1n,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 k≥k0(n,m)k\ge k_0(n,m),

a(f∘(g⊕PAR⁡k),π1/2)=a(f,π1/2)⋅a(g⊕PAR⁡k,π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.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.