Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #11 to TR13-190 | 23rd October 2017 19:33

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

Revision #11
Authors: Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
Accepted on: 23rd October 2017 19:33
Keywords:

Abstract:

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\mathbf{P} \subseteq \mathbf{NC}^1$). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, 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 $g\diamond f$ is roughly the sum of the depth complexities of $f$ and $g$. They showed that the validity of this conjecture would imply that $\mathbf{P} \subseteq \mathbf{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 universal relations. This suggestion proved fruitful, and an analogue of the KRW conjecture for the universal relation was proved by Edmonds et. al. [EIRS01]. An alternative proof was given later by Hastad and Wigderson [HW93]. However, studying the composition of functions seems more difficult, and the KRW conjecture is still wide open.

In this work, we make a natural step in this direction, which lies between what is known and the original conjecture: we show that an analogue of the conjecture holds for the composition of a function with a universal relation.

Changes to previous version:

Now gives proper credit to Hastad for the efficient randomized protocol that solves KW relations with an unbounded number of rounds.

Revision #10 to TR13-190 | 20th August 2016 00:30

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

Revision #10
Authors: Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
Accepted on: 20th August 2016 00:30
Keywords:

Abstract:

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\P\not\subseteq\NCo$). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, 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 $g\diamond f$ is roughly the sum of the depth complexities of $f$ and $g$. They showed that the validity of this conjecture would imply that $\P\not\subseteq\NCo$.

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 universal relations. This suggestion proved fruitful, and an analogue of the KRW conjecture for the universal relation was proved by Edmonds et. al. [EIRS01]. An alternative proof was given later by H{\aa}stad and Wigderson [HW93]. However, studying the composition of functions seems more difficult, and the KRW conjecture is still wide open.

In this work, we make a natural step in this direction, which lies between what is known and the original conjecture: we show that an analogue of the conjecture holds for the composition of a function
with a universal relation.

Changes to previous version:

Fixes following the journal version.

Revision #9 to TR13-190 | 23rd April 2015 21:36

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

Revision #9
Authors: Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
Accepted on: 23rd April 2015 21:36
Keywords:

Abstract:

One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1~$). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, 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 $g\circ f$ is roughly the sum of the depth complexities of $f$ and $g$. They showed that the validity of this conjecture would imply that $\mathbf{P}\not\subseteq\mathbf{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 universal relations. This suggestion proved fruitful, and an analogue of the KRW conjecture for the universal relation was proved by Edmonds et. al. [EIRS01]. An alternative proof was given later by Hastad and Wigderson [HW93]. However, studying the composition of functions seems more difficult, and the KRW conjecture is still wide open.

In this work, we make a natural step in this direction, which lies between what is known and the original conjecture: we show that an analogue of the conjecture holds for the composition of a function with a universal relation. We also suggest a candidate for the next step and provide initial results toward it.

Our main technical contribution is developing an approach based on the notion of information complexity for analyzing KW relations - communication problems that are closely related to questions on circuit depth and formula complexity. Recently, information complexity has proved to be a powerful tool, and underlined some major progress on several long-standing open problems in communication complexity. In this work, we develop general tools for analyzing the information complexity of KW relations, which may be of independent interest.

Revision #8 to TR13-190 | 29th May 2014 23:57

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

Revision #8
Authors: Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
Accepted on: 29th May 2014 23:57
Keywords:

Abstract:

One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}_1~$). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, it is one of the first milestones toward proving super-polynomial circuit lower bounds.

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}_1~$). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, 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 $g\circ f$ is roughly the sum of the depth complexities of $f$ and $g$. They showed that the validity of this conjecture would imply that $\mathbf{P}\not\subseteq\mathbf{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 universal relations. This suggestion proved fruitful, and an analogue of the KRW conjecture for the universal relation was proved by Edmonds et. al. [EIRS01]. An alternative proof was given later by H{\aa}stad and Wigderson [HW93]. However, studying the composition of functions seems more difficult, and the KRW conjecture is still wide open.

In this work, we make a natural step in this direction, which lies between what is known and the original conjecture: we show that an analogue of the conjecture holds for the composition of a function with a universal relation. We also suggest a candidate for the next step and provide initial results toward it.

Our main technical contribution is developing an approach based on the notion of information complexity for analyzing KW relations -- communication problems that are closely related to questions on circuit depth and formula complexity. Recently, information complexity has proved to be a powerful tool, and underlined some major progress on several long-standing open problems in communication complexity. In this work, we develop general tools for analyzing the information complexity of KW relations, which may be of independent interest.

Changes to previous version:

Updated an acknowledgement.

Revision #7 to TR13-190 | 28th April 2014 21:13

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

Revision #7
Authors: Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
Accepted on: 28th April 2014 21:13
Keywords:

Abstract:

One of the major open problems in complexity theory is proving super-logarithmic
lower bounds on the depth of circuits (i.e., $\mathbf{P} \not\subseteq \mathbf{NC}^1$).
This problem is interesting for two reasons: first, it is tightly
related to understanding the power of parallel computation and of
small-space computation; second, 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
$g \circ f$ is roughly the sum of the depth complexities of $f$ and
$g$. They showed that the validity of this conjecture would imply
that $\mathbf{P} \not\subseteq \mathbf{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 universal relations. This suggestion proved
fruitful, and an analogue of the KRW conjecture for the universal
relation was proved by Edmonds et. al. [EIRS01]. An alternative proof was given later by H{\aa}stad and Wigderson [HW93].
However, studying the composition of functions seems more difficult,
and the KRW conjecture is still wide open.

In this work, we make a natural step in this direction, which lies
between what is known and the original conjecture: we show that an
analogue of the conjecture holds for the composition of a function
with a universal relation. We also suggest a candidate for the next
step and provide initial results toward it.

Our main technical contribution is developing an approach based on
the notion of information complexity for analyzing KW relations - communication problems that are closely related to questions on
circuit depth and formula complexity. Recently, information complexity
has proved to be a powerful tool, and underlined some major progress
on several long-standing open problems in communication complexity.
In this work, we develop general tools for analyzing the information
complexity of KW relations, which may be of independent interest.

Revision #6 to TR13-190 | 20th March 2014 23:13

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

Revision #6
Authors: Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
Accepted on: 20th March 2014 23:13
Keywords:

Abstract:

One of the major open problems in complexity theory is proving super-logarithmic
lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1~$).
This problem is interesting for two reasons: first, it is tightly
related to understanding the power of parallel computation and of
small-space computation; second, 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
$g\circ f$ is roughly the sum of the depth complexities of $f$ and
$g$. They showed that the validity of this conjecture would imply
that $\mathbf{P}\not\subseteq\mathbf{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 universal relations. This suggestion proved
fruitful, and an analogue of the KRW conjecture for the universal
relation was proved by Edmonds et. al. [EIRS01]. An alternative proof was given later by H{\aa}stad and Wigderson [HW93].
However, studying the composition of functions seems more difficult,
and the KRW conjecture is still wide open.

In this work, we make a natural step in this direction, which lies
between what is known and the original conjecture: we show that an
analogue of the conjecture holds for the composition of a function
with a universal relation. We also suggest a candidate for the next
step and provide initial results toward it.

Our main technical contribution is developing an approach based on
the notion of information complexity for analyzing KW relations - communication problems that are closely related to questions on
circuit depth and formula complexity. Recently, information complexity
has proved to be a powerful tool, and underlined some major progress
on several long-standing open problems in communication complexity.
In this work, we develop general tools for analyzing the information
complexity of KW relations, which may be of independent interest.

Revision #5 to TR13-190 | 19th March 2014 22:26

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

Revision #5
Authors: Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
Accepted on: 19th March 2014 22:26
Keywords:

Abstract:

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1~$). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, it is one of the first milestones toward proving super-polynomial circuit lower bounds.

Abstract 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 $g\circ f$ is roughly the sum of the depth complexities of $f$ and $g$. They showed that the validity of this conjecture would imply that $\mathbf{P}\not\subseteq\mathbf{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 universal relations. This suggestion proved fruitful, and an analogue of the KRW conjecture for the universal relation was proved by Edmonds et. al. [EIRS01]. An alternative proof was given later by H{\aa}stad and Wigderson [HW93]. However, studying the composition of functions seems more difficult, and the KRW conjecture is still wide open.

In this work, we make a natural step in this direction, which lies between what is known and the original conjecture: we show that an analogue of the conjecture holds for the composition of a function with a universal relation. We also suggest a candidate for the next step and provide initial results toward it.

Our main technical contribution is developing an approach based on the notion of information complexity for analyzing KW relations -- communication problems that are closely related to questions on circuit depth and formula complexity. Recently, information complexity has proved to be a powerful tool, and underlined some major progress on several long-standing open problems in communication complexity. In this work, we develop general tools for analyzing the information complexity of KW relations, which may be of independent interest.

Revision #4 to TR13-190 | 19th March 2014 22:22

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

Revision #4
Authors: Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
Accepted on: 19th March 2014 22:22
Keywords:

Abstract:

One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}_1~$). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, 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 $g\circ f$ is roughly the sum of the depth complexities of $f$ and $g$. They showed that the validity of this conjecture would imply that $\mathbf{P}\not\subseteq\mathbf{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 universal relations. This suggestion proved fruitful, and an analogue of the KRW conjecture for the universal relation was proved by Edmonds et. al. [EIRS01]. An alternative proof was given later by Hastad and Wigderson [HW93]. However, studying the composition of functions seems more difficult, and the KRW conjecture is still wide open.

In this work, we make a natural step in this direction, which lies between what is known and the original conjecture: we show that an analogue of the conjecture holds for the composition of a function with a universal relation. We also suggest a candidate for the next step and provide initial results toward it.

Our main technical contribution is developing an approach based on the notion of information complexity for analyzing KW relations - communication problems that are closely related to questions on circuit depth and formula complexity. Recently, information complexity has proved to be a powerful tool, and underlined some major progress on several long-standing open problems in communication complexity. In this work, we develop general tools for analyzing the information complexity of KW relations, which may be of independent interest.

Changes to previous version:

Minor fixes.

Revision #3 to TR13-190 | 19th March 2014 22:21

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

Revision #3
Authors: Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
Accepted on: 19th March 2014 22:21
Keywords:

Abstract:

One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}_1~$). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, 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 $g\circ f$ is roughly the sum of the depth complexities of $f$ and $g$. They showed that the validity of this conjecture would imply that $\mathbf{P}\not\subseteq\mathbf{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 universal relations. This suggestion proved fruitful, and an analogue of the KRW conjecture for the universal relation was proved by Edmonds et. al. [EIRS01]. An alternative proof was given later by Hastad and Wigderson [HW93]. However, studying the composition of functions seems more difficult, and the KRW conjecture is still wide open.

In this work, we make a natural step in this direction, which lies between what is known and the original conjecture: we show that an analogue of the conjecture holds for the composition of a function with a universal relation. We also suggest a candidate for the next step and provide initial results toward it.

Our main technical contribution is developing an approach based on the notion of information complexity for analyzing KW relations - communication problems that are closely related to questions on circuit depth and formula complexity. Recently, information complexity has proved to be a powerful tool, and underlined some major progress on several long-standing open problems in communication complexity. In this work, we develop general tools for analyzing the information complexity of KW relations, which may be of independent interest.

Revision #2 to TR13-190 | 19th March 2014 22:18

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

Revision #2
Authors: Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
Accepted on: 19th March 2014 22:18
Keywords:

Abstract:

Abstract One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}^1~$). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, 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 $g\circ f$ is roughly the sum of the depth complexities of $f$ and $g$. They showed that the validity of this conjecture would imply that $\mathbf{P}\not\subseteq\mathbf{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 universal relations. This suggestion proved fruitful, and an analogue of the KRW conjecture for the universal relation was proved by Edmonds et. al. [EIRS01]. An alternative proof was given later by H{\aa}stad and Wigderson [HW93]. However, studying the composition of functions seems more difficult, and the KRW conjecture is still wide open.

Abstract In this work, we make a natural step in this direction, which lies between what is known and the original conjecture: we show that an analogue of the conjecture holds for the composition of a function with a universal relation. We also suggest a candidate for the next step and provide initial results toward it.

Abstract Our main technical contribution is developing an approach based on the notion of information complexity for analyzing KW relations -- communication problems that are closely related to questions on circuit depth and formula complexity. Recently, information complexity has proved to be a powerful tool, and underlined some major progress on several long-standing open problems in communication complexity. In this work, we develop general tools for analyzing the information complexity of KW relations, which may be of independent interest.

Changes to previous version:

Minor fixes.

Revision #1 to TR13-190 | 31st December 2013 11:12

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

Revision #1
Authors: Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
Accepted on: 31st December 2013 11:12
Keywords:

Abstract:

One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}_1~$). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, 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 $g\circ f$ is roughly the sum of the depth complexities of $f$ and $g$. They showed that the validity of this conjecture would imply that $\mathbf{P}\not\subseteq\mathbf{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 universal relations. This suggestion proved fruitful, and an analogue of the KRW conjecture for the universal relation was proved by Edmonds et. al. [EIRS01]. An alternative proof was given later by Hastad and Wigderson [HW93]. However, studying the composition of functions seems more difficult, and the KRW conjecture is still wide open.

In this work, we make a natural step in this direction, which lies between what is known and the original conjecture: we show that an analogue of the conjecture holds for the composition of a function with a universal relation. We also suggest a candidate for the next step and provide initial results toward it.

Our main technical contribution is developing an approach based on the notion of information complexity for analyzing KW relations - communication problems that are closely related to questions on circuit depth and formula complexity. Recently, information complexity has proved to be a powerful tool, and underlined some major progress on several long-standing open problems in communication complexity. In this work, we develop general tools for analyzing the information complexity of KW relations, which may be of independent interest.

### Paper:

TR13-190 | 28th December 2013 00:03

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

TR13-190
Authors: Dmitry Gavinsky, Or Meir, Omri Weinstein, Avi Wigderson
Publication: 28th December 2013 13:29
Keywords:

Abstract:

One of the major open problems in complexity theory is proving super-polynomial lower bounds for circuits with logarithmic depth (i.e., $\mathbf{P}\not\subseteq\mathbf{NC}_1~$). This problem is interesting for two reasons: first, it is tightly related to understanding the power of parallel computation and of small-space computation; second, 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 $g\circ f$ is roughly the sum of the depth complexities of $f$ and $g$. They showed that the validity of this conjecture would imply that $\mathbf{P}\not\subseteq\mathbf{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 universal relations. This suggestion proved fruitful, and an analogue of the KRW conjecture for the universal relation was proved by Edmonds et. al. [EIRS01]. An alternative proof was given later by Hastad and Wigderson [HW93]. However, studying the composition of functions seems more difficult, and the KRW conjecture is still wide open.

In this work, we make a natural step in this direction, which lies between what is known and the original conjecture: we show that an analogue of the conjecture holds for the composition of a function with a universal relation. We also suggest a candidate for the next step and provide initial results toward it.

Our main technical contribution is developing an approach based on the notion of information complexity for analyzing KW relations - communication problems that are closely related to questions on circuit depth and formula complexity. Recently, information complexity has proved to be a powerful tool, and underlined some major progress on several long-standing open problems in communication complexity. In this work, we develop general tools for analyzing the information complexity of KW relations, which may be of independent interest.

ISSN 1433-8092 | Imprint