## 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.