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

by Dmitry Gavinsky, Or Meir, Omri Weinstein, and Avi Wigderson.

Oded's comments

The abstract conveys very well the wide context of the work, but I feel that some narrowing qualification is in place. Specifically, the direction pursued here is the quest for lower bounds on the communication complexity of the KW-relation that arises from the composition of two boolean functions. The ``middle point'' referred to in the abstract lies between the composition of two arbitrary boolean functions (which is the holy grail) and the composition of two universal relations; specifically, it is the composition of an arbitrary function with the universal relation. The techniques include defining hard distribution for several auxiliary protocols that arise from the analysis of a hypothetical protocol for the composed problem.

The original abstract

One of the holy grails of computational complexity theory is to find explicit functions that can not be computed by small boolean circuits (circuits that have AND, OR, and NOT gates). A major open problem toward this holy grail is finding explicit functions that can not be computed by "shallow" circuits. This open problem is tightly related to establishing limitations on highly-parallelizable computations and on small-space computations. In 1991, Karchmer, Raz, and Wigderson made a conjecture on the depth of circuits that, if true, will allow us to solve the latter open problem. Some initial steps toward resolving this conjecture were made during the early 1990's, but since then, it seems that progress stopped. In this work, we make another step toward resolving the KRW conjecture. Specifically, we resolve a special case that lies in the middle between what was known in the 1990's and the full conjecture. To this end, we adapt recent information-theoretic techniques from the field of communication complexity to the setting of the KRW conjecture.


Back to list of Oded's choices.