KRW Conjecture and KRW-Like Theorems: New Lower Bounds via Lifting — E8 Intelligence Research

FINDING: The KRW conjecture — a proposed composition theorem for Boolean circuit depth — remains open, but recent work by Or Meir and others has produced "KRW-like" theorems for restricted forms of composition, yielding new lower bounds via information complexity and lifting techniques. | MATH: The conjecture states that for Boolean functions \(f: \{0,1\}^n → \{0,1\}\) and \(g: \{0,1\}^m → \{0,1\}\), the composition \(f g\) (where \(g\) is applied to each of \(n\) blocks of \(m\) bits) has circuit depth \(D(f g) ≈ D(f) + D(g)\). More precisely, \(D(f g) ≥ D(f) + D(g) - O(1)\). The "strong composition" variant replaces \(g\) with a "universal" function, and Meir's 2024 result proves a KRW-like theorem for this case, giving depth lower bounds of the form \(Ω(n1/3)\) or similar for explicit functions. Lifting theorems translate communication complexity lower bounds (e.g., \(CC(f ∘ g) ≥ CC(f) · log CC(g)\)) into circuit depth lowe Author: Andrew Stewart Caldin, Independent Researcher, UK. Part of the E8 Intelligence Research series. Platform: e8intelligence.com