Improved Composition Theorems for Functions and Relations
Sajin Koroth, Or Meir · DROPS (Schloss Dagstuhl – Leibniz Center for Informatics) · 2018
One of the central problems in complexity theory is to prove super-logarithmic depth bounds for circuits computing a problem in P, i.e., to prove that P is not contained in NC^1. As an approach for this question, Karchmer, Raz and Wigderson [Mauricio Karchmer et al., 1995] proposed a conjecture called the KRW conjecture, which if true, would imply that P is not cotained in NC^{1}. Since proving this conjecture is currently considered an extremely difficult problem, previous works by Edmonds, Impagliazzo, Rudich and Sgall [Edmonds et al., 2001], Håstad and Wigderson [Johan Håstad and Avi Wigderson, 1990] and Gavinsky, Meir, Weinstein and Wigderson [Dmitry Gavinsky et al., 2014] considered weaker variants of the conjecture. In this work we significantly improve the parameters in these variants, achieving almost tight lower bounds.