Imagine you're estimating how long it takes to assemble a car. You know the time to build the engine and the time to build the chassis separately. The question is: does building the full car always take roughly engine-time × chassis-time, or could clever engineering sometimes cheat the product? For approximate degree of Boolean functions under block composition, the answer is now definitive: you cannot cheat the product. The time (degree) always multiplies. The paper by Pednekar and Podder resolves a longstanding open problem in computational complexity theory. The question: when you compose two Boolean functions f and g (plugging copies of g into each input bit of f), does the approximate degree — the minimum degree of a real polynomial that approximates the composed function to constant error — always equal Θ(deg̃(f) · deg̃(g))? Sherstov proved the upper bound years ago. The lower bound was known only for restricted function classes. This paper proves it for all total Boolean functions. The claim is a genuine closure result, not an incremental improvement. Prior work by Sherstov, Bun–Thaler, and others had established the lower bound for specific families — symmetric functions, certain composed functions with known dual witnesses. The general case resisted because constructing dual polynomials (the witnesses for lower bounds) for arbitrary compositions required new machinery. This paper delivers that machinery. The architecture lives squarely in the polynomial method tradition of Boolean function complexity. The core technique involves constructing explicit dual witnesses for the composed function by combining dual witnesses for f and g. This is a proof-based result — no algorithms, no experiments, no hardware. The 27-page paper is pure combinatorics and approximation theory, working within the framework that Nisan–Szegedy, Paturi, and Sherstov built over three decades. Integrity here means mathematical proof, which is the gold standard for this kind of claim. There's no simulation to audit, no benchmark to cherry-pick, no dataset to overfit. The result either holds or it doesn't, and independent verification will come from the community reading the 27 pages. The paper is on arXiv, so the proof is fully public. Why should you care if you're not a complexity theorist? Approximate degree is one of the core measures connecting Boolean function complexity to quantum query complexity, communication complexity, and circuit lower bounds. A tight composition theorem means that complexity measures propagate predictably through composition — which constrains how much structure-exploitation is possible when building complex functions from simple ones. It's the kind of foundational brick that other results build on for decades. The obvious successor question: does this technique extend to partial functions, where the composition question remains open and substantially harder? The authors likely know this is the next target. The restriction to total functions is load-bearing in the proof, and partial functions have resisted analogous composition results across multiple complexity measures. That's the frontier now.
