Computing composed boolean functions requires less queries than expected
No Perfect Randomized Composition
Computational Complexity
Summary
The paper finds that combining certain Boolean functions doesn't always need as many computer queries as previously thought. The authors show that the complexity of solving a function made by composing two others can be smaller than the product of their individual complexities, defying old assumptions. They also explore different ways to measure this complexity and provide examples separating these measures. Their work helps clarify relationships between various query complexities and establishes limits on how efficient randomized algorithms can be for these problems.
What this means in practice
- •For algorithm designers: Avoid assuming the query cost of composed Boolean functions is simply the product of their components, enabling more efficient algorithm designs.
- •For complexity theorists: Leverage new separations between query complexity measures to refine theoretical models of randomized computation.
A theory result. No direct application yet.
Authors
Alexander Meiburg
Abstract
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) =Θ\!\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χ$, and linearised query complexity $LR$. We show that AND-of-ORs separates conflict $χ$ from max-conflict $\barχ$ complexity and makes conflict and sabotage incomparable. Finally, randomized complexity can be smaller than its composition limit $R^*$ by the maximal factor $Θ(\log R)$. The total--total composition separation is also formalized in Lean.