Name
Abstract | ||
|---|---|---|
One of the major open problems in complexity theory is proving super-logarithmic
lower bounds on the depth of circuits (i.e.,
$$\textbf{P} \not\subseteq \textbf{NC}^{1}$$
).
Karchmer, Raz, and Wigderson (Computational Complexity 5(3/4):191–204, 1995)
suggested to approach this problem by proving that depth complexity
behaves ``as expected'' with respect to the composition of functions f ◊ g.
They showed that the validity of this conjecture would imply that
$$\textbf{P} \not\subseteq \textbf{NC}^{1}$$
. As a way to realize this program, Edmonds et al. (Computational Complexity
10(3):210–246, 2001) suggested to study the ``multiplexor relation'' MUX.
In this paper, we present two results regarding this relation: |
Year | DOI | Venue |
|---|---|---|
2019 | 10.1007/s00037-020-00194-8 | computational complexity |
Keywords | DocType | Volume |
Circuit complexity, Circuit Lower Bounds, Depth complexity, Depth lower bounds, Communication complexity, Karchmer–Wigersion relations, KRW conjecture, Multiplexor, Multiplexer, Address function, 68Q15 | Journal | 29 |
Issue | ISSN | Citations |
1 | 1016-3328 | 0 |
PageRank | References | Authors |
0.34 | 0 | 1 |