KRW composition theorems via lifting
(2020) 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020 In Proceedings  Annual IEEE Symposium on Foundations of Computer Science, FOCS 2020November. p.4349 Abstract
One of the major open problems in complexity theory is proving superlogarithmic lower bounds on the depth of circuits (i.e., mathrm{P} nsubseteq text{NC}{1}). 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 diamond g. They showed that the validity of this conjecture would imply that mathrm{P} nsubseteq text{NC}{1}. 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.... (More)
One of the major open problems in complexity theory is proving superlogarithmic lower bounds on the depth of circuits (i.e., mathrm{P} nsubseteq text{NC}{1}). 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 diamond g. They showed that the validity of this conjecture would imply that mathrm{P} nsubseteq text{NC}{1}. 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 querytocommunication lifting theorem. This allows us to handle several new and wellstudied functions such as the stconnectivity, clique, and generation functions. In order to carry this progress back to the nonmonotone setting, we introduce a new notion of semimonotone composition, which combines the nonmonotone 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.
(Less)
 author
 De Rezende, Susanna F. ^{LU} ; Meir, Or ; Nordstrom, Jakob ^{LU} ; Pitassi, Toniann and Robere, Robert
 organization
 publishing date
 202011
 type
 Chapter in Book/Report/Conference proceeding
 publication status
 published
 subject
 keywords
 circuit complexity, circuit lower bounds, communication complexity, depth complexity, depth lower bounds, formula complexity, formula lower bounds, KarchmerWigderson relations, KRW, KW relations, Lifting, Simulation
 host publication
 Proceedings  2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020
 series title
 Proceedings  Annual IEEE Symposium on Foundations of Computer Science, FOCS
 volume
 2020November
 article number
 9317931
 pages
 7 pages
 publisher
 IEEE Computer Society
 conference name
 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
 conference location
 Virtual, Durham, United States
 conference dates
 20201116  20201119
 external identifiers

 scopus:85100337778
 ISSN
 02725428
 ISBN
 9781728196213
 9781728196220
 DOI
 10.1109/FOCS46700.2020.00013
 language
 English
 LU publication?
 yes
 additional info
 Publisher Copyright: © 2020 IEEE.
 id
 ffc36c301050428a803da12c0bc7ef01
 date added to LUP
 20211214 15:47:20
 date last changed
 20240811 03:29:00
@inproceedings{ffc36c301050428a803da12c0bc7ef01, abstract = {{<p>One of the major open problems in complexity theory is proving superlogarithmic lower bounds on the depth of circuits (i.e., mathrm{P} nsubseteq text{NC}{1}). 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 diamond g. They showed that the validity of this conjecture would imply that mathrm{P} nsubseteq text{NC}{1}. 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 querytocommunication lifting theorem. This allows us to handle several new and wellstudied functions such as the stconnectivity, clique, and generation functions. In order to carry this progress back to the nonmonotone setting, we introduce a new notion of semimonotone composition, which combines the nonmonotone 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.</p>}}, author = {{De Rezende, Susanna F. and Meir, Or and Nordstrom, Jakob and Pitassi, Toniann and Robere, Robert}}, booktitle = {{Proceedings  2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020}}, isbn = {{9781728196213}}, issn = {{02725428}}, keywords = {{circuit complexity; circuit lower bounds; communication complexity; depth complexity; depth lower bounds; formula complexity; formula lower bounds; KarchmerWigderson relations; KRW; KW relations; Lifting; Simulation}}, language = {{eng}}, pages = {{4349}}, publisher = {{IEEE Computer Society}}, series = {{Proceedings  Annual IEEE Symposium on Foundations of Computer Science, FOCS}}, title = {{KRW composition theorems via lifting}}, url = {{http://dx.doi.org/10.1109/FOCS46700.2020.00013}}, doi = {{10.1109/FOCS46700.2020.00013}}, volume = {{2020November}}, year = {{2020}}, }