__
Revision #1 to TR19-120 | 25th February 2020 14:23
__
#### Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation

Revision #1
Authors:

Or Meir
Accepted on: 25th February 2020 14:23

Downloads: 163

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$). Karchmer, Raz, and Wigderson (Computational Complexity 5, 3/4) suggested to approach this problem by proving that depth complexity behaves "as expected" with respect to the composition of functions $f \diamond g$. They showed that the validity of this conjecture would imply that $\mathbf{P}\not\subseteq\mathbf{NC}^1$.

As a way to realize this program, Edmonds et. al. (Computational Complexity 10, 3) suggested to study the "multiplexor relation" $MUX$, which is a simplification of functions. In this note, we present two results regarding this relation:

- The multiplexor relation is "complete" for the approach of Karchmer et. al.

in the following sense: if we could prove (a variant of) their conjecture

for the composition $f \diamond MUX$ for every function $f$, then this would

imply $\mathbf{P}\not\subseteq\mathbf{NC}^1$.

- A simpler proof of a lower bound for the multiplexor relation due

to Edmonds et. al. Our proof has the additional benefit of fitting

better with the machinery used in previous works on the subject.

**Changes to previous version:**
Some minor fixes, and added a new "open problems" section.

__
TR19-120 | 11th September 2019 17:37
__

#### Toward Better Depth Lower Bounds: Two Results on the Multiplexor Relation

TR19-120
Authors:

Or Meir
Publication: 15th September 2019 17:52

Downloads: 363

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$). Karchmer, Raz, and Wigderson (Computational Complexity 5, 3/4) suggested to approach this problem by proving that depth complexity behaves "as expected" with respect to the composition of functions $f \diamond g$. They showed that the validity of this conjecture would imply that $\mathbf{P}\not\subseteq\mathbf{NC}^1$.

As a way to realize this program, Edmonds et. al. (Computational Complexity 10, 3) suggested to study the "multiplexor relation" $MUX$, which is a simplification of functions. In this note, we present two results regarding this relation:

- The multiplexor relation is "complete" for the approach of Karchmer et. al.

in the following sense: if we could prove (a variant of) their conjecture

for the composition $f \diamond MUX$ for every function $f$, then this would

imply $\mathbf{P}\not\subseteq\mathbf{NC}^1$.

- A simpler proof of a lower bound for the multiplexor relation due

to Edmonds et. al. Our proof has the additional benefit of fitting

better with the machinery used in previous works on the subject.