A central question in computational complexity is how the difficulty of a task grows when we combine simple building blocks into a larger system. If a function $f$ requires a certain amount of resources to compute, and we use $f$ as an input to another function $g$, intuition suggests the total complexity should be roughly the product of their individual complexities. This intuition is formalized through composition theorems and lifting theorems, which seek to prove that computational difficulty scales multiplicatively rather than additively.
The Multiplicative Nature of Composition
The core challenge in this field is proving that the complexity of a composed function $g \circ f$ is indeed related to the product of the complexities of $g$ and $f$. While it is easy to show that complexity is at most the product (an upper bound), proving that it is at least the product (a lower bound) is notoriously difficult.
As Victor Lecomte et al. demonstrate in The composition complexity of majority, many functions incur a "composition overhead." For example, computing the majority of $n$ bits using functions that only see $k$ bits requires more than just a simple coverage of inputs; it requires a logarithmic overhead to coordinate these local parts. This suggests that composition is inherently resource-intensive, requiring computational structures that grow significantly as functions are nested.
Lifting Theorems: Bridging Complexity Measures
Lifting theorems provide a mechanism to transfer lower bounds from a simple computational model to a more complex one. By "lifting" a function through composition—typically by replacing each input variable with a small "gadget" function—researchers can prove hardness in models that are otherwise difficult to analyze directly.
For instance, Sam McGuire et al. in Log-rank and lifting for AND-functions develop lifting theorems specifically for AND-functions to connect sparsity and rank to communication complexity. Similarly, Adam Bouland et al. use a "quantum method" in Classical Lower Bounds from Quantum Upper Bounds to establish optimal composition bounds for approximate degree and rank, showing that the complexity of $OR_n \circ f$ scales with $\sqrt{n} \deg(f)$.
Hardness Amplification via Recursive Nesting
Composition is also a primary tool for hardness amplification. By recursively nesting a function within itself, researchers can construct functions that are extremely difficult to approximate or compute.
In Hardness Amplification and the Approximate Degree of Constant-Depth Circuits, Mark Bun and Justin Thaler show that composing a function with an OR gate can transform a function that is only slightly hard into one that is nearly impossible to approximate. This technique allowed Mark Bun and Justin Thaler to resolve a long-standing problem in A Nearly Optimal Lower Bound on the Approximate Degree of AC0, proving that even simple constant-depth circuits can have a very high approximate degree.
Limits and Open Conjectures
Despite progress, the "Randomized Composition Conjecture"—which posits that randomized query complexity is perfectly multiplicative—remains unproven for total functions. Andrew Bassilakis et al. note in The Power of Many Samples in Query Complexity that while more data (samples) might seem helpful, extra samples provide no advantage in the hardest cases of function composition.
Furthermore, the scaling behavior is not always a clean product. Ryan O'Donnell et al. found in A composition theorem for parity kill number that certain complexity measures might scale with sub-optimal exponents (e.g., $k-1$ instead of $k$ for $k$ iterations). To study these long-term trends, Michael E. Saks introduced the concept of a composition limit in Composition limits and separating examples for some boolean function complexity measures, which analyzes the asymptotic growth rate of complexity as a function is nested infinitely many times.
Structural Obstacles to Composition
The difficulty in proving these bounds often stems from how composition obscures structure. In functional programming, Ruyi Ji et al. point out in Proving Functional Program Equivalence via Directed Lemma Synthesis that nested calls hide the underlying recursive patterns, making it hard for automated tools to verify properties.
In circuit complexity, the "Tree Evaluation Problem" serves as a benchmark for this difficulty. As the authors of Hardness of Function Composition for Semantic Read once Branching Programs establish, the size of a computational model required to solve such problems scales exponentially with the height of the composition tree, confirming that combining tasks is fundamentally more expensive than the sum of its parts.
Key Foundational Work
A decision procedure for linear "big O" equations (2007) — contributed 1 concept elements to this direction.
ANGIE: Active Knowledge for Interactive Exploration (2009) — contributed 1 concept elements to this direction.