Eventual multiplicativity of algorithmic complexity under parity-perturbed composition
Eventual multiplicativity of algorithmic complexity under parity-perturbed composition
For Boolean functions on bits and on bits, let denote their block composition, let be parity on bits, let denote the corresponding XOR construction, and let be the distributional algorithmic complexity of under the uniform distribution.
Composition multiplicativity conjecture. For every , there exists such that, for every Boolean functions and on and bits, respectively, and every ,
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
Sign in to submit a solution.
No solutions have been posted yet.