KRW Composition Theorems via Lifting
Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Standard
KRW Composition Theorems via Lifting. / de Rezende, Susanna; Meir, Or; Nordström, Jakob; Pitassi, Toniann; Robere, Robert.
Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS '20). IEEE, 2020. p. 4149.Research output: Chapter in Book/Report/Conference proceeding › Article in proceedings › Research › peer-review
Harvard
, Durham, NC, United States, 16/11/2020. https://doi.org/10.1109/FOCS46700.2020.00013
APA
Vancouver
Author
Bibtex
}
RIS
TY - GEN
T1 - KRW Composition Theorems via Lifting
AU - de Rezende, Susanna
AU - Meir, Or
AU - Nordström, Jakob
AU - Pitassi, Toniann
AU - Robere, Robert
N1 - To appear
PY - 2020/11/1
Y1 - 2020/11/1
N2 - One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., P⊈NC1 ). Karchmer, Raz, and Wigderson [13] 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⊈NC1 . Several works have made progress toward resolving this conjecture by proving special cases. In particular, these works proved the KRW conjecture for every outer function, but only for few inner functions. Thus, it is an important challenge to prove the KRW conjecture for a wider range of inner functions. In this work, we extend significantly the range of inner functions that can be handled. First, we consider the monotone version of the KRW conjecture. We prove it for every monotone inner function whose depth complexity can be lower bounded via a query-to-communication lifting theorem. This allows us to handle several new and well-studied functions such as the s−t -connectivity, clique, and generation functions. In order to carry this progress back to the non-monotone setting, we introduce a new notion of semi-monotone composition, which combines the non-monotone complexity of the outer function with the monotone complexity of the inner function. In this setting, we prove the KRW conjecture for a similar selection of inner functions, but only for a specific choice of the outer function f .
AB - One of the major open problems in complexity theory is proving super-logarithmic lower bounds on the depth of circuits (i.e., P⊈NC1 ). Karchmer, Raz, and Wigderson [13] 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⊈NC1 . Several works have made progress toward resolving this conjecture by proving special cases. In particular, these works proved the KRW conjecture for every outer function, but only for few inner functions. Thus, it is an important challenge to prove the KRW conjecture for a wider range of inner functions. In this work, we extend significantly the range of inner functions that can be handled. First, we consider the monotone version of the KRW conjecture. We prove it for every monotone inner function whose depth complexity can be lower bounded via a query-to-communication lifting theorem. This allows us to handle several new and well-studied functions such as the s−t -connectivity, clique, and generation functions. In order to carry this progress back to the non-monotone setting, we introduce a new notion of semi-monotone composition, which combines the non-monotone complexity of the outer function with the monotone complexity of the inner function. In this setting, we prove the KRW conjecture for a similar selection of inner functions, but only for a specific choice of the outer function f .
U2 - 10.1109/FOCS46700.2020.00013
DO - 10.1109/FOCS46700.2020.00013
M3 - Article in proceedings
SP - 4149
BT - Proceedings of the 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS '20)
PB - IEEE
T2 - 61st Annual Symposium on Foundations of Computer Science (FOCS), 2020 IEEE<br/>
Y2 - 16 November 2020 through 19 November 2020
ER -
ID: 251872420