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

摘要

One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., P 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 g . They showed that the validity of this conjecture would imply that P NC 1 .As a way to realize this program, Edmonds et. al. (Computational Complexity 10, 3) suggested to study the "multiplexor relation" MU X , 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 M U X for every function f , then this would imply P 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.