Toward Better Formula Lower Bounds: An InformationOr Meir: Complexity Approach to the KRW Composition Conjecture

One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e.,{P} otsubseteq mathbb{NC_1}$ ). This problem is interesting both because it is tightly related to understanding the power of parallel computation and of small-space computation, and because it is one of the first milestones toward proving super-polynomial circuit lower bounds.

Karchmer, Raz, and Wigderson [KRW95] suggested to approach this problem by proving the following conjecture: given two boolean functions f and g, the depth complexity of the composed function circ f$ is roughly the sum of the depth complexities of f and g. They showed that proving this conjecture would imply that {P} ot subseteq mathbb{NC_1}$.

As a starting point for studying the composition of functions, they introduced a relation called the universal relation, and suggested to study the composition of two universal relations. This suggestion proved fruitful, and indeed, an analogue of the KRW conjecture for the universal relation was proved later by Edmonds et. al. [EIRS01] and H{aa}stad and Wigderson [HW93]. However, studying the composition of two functions seems more difficult, and the KRW conjecture is still wide open.

In this work, we make a natural step in this direction, which sits between what is known and the real goal: we show that an analogue of the KRW conjecture holds for the composition of a one function with one universal relation. We also suggest a candidate for the next step and provide initial results toward solving it. We hope that these results will revive the study of the KRW conjecture.

Our main technical contribution is developing an approach based on the notion of information complexity for analyzing KW games -- communication problems that are closely related to questions on circuit depth and formula complexity. Information complexity has proved recently to be a powerful tool to make major progress on another long-standing "economy-of-scale" problem in communication complexity: the direct-sum conjecture. We develop general tools for analyzing the information complexity of KW relations, which may be of independent interest.