Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #2 to TR19-120 | 26th March 2023 15:28

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

RSS-Feed




Revision #2
Authors: Or Meir
Accepted on: 26th March 2023 15:28
Downloads: 157
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 additional fixes following the submission to the journal. In particular, fixed an error in the proof of the Kovari-Sos-Turan theorem.


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: 545
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.


Paper:

TR19-120 | 11th September 2019 17:37

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


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.



ISSN 1433-8092 | Imprint