KRW composition theorems via lifting
De Rezende, Susanna F. LU
; Meir, Or
; Nordstrom, Jakob
LU
; Pitassi, Toniann
and Robere, Robert
(2020)
61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020
In Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
2020-November.
p.43-49
- Abstract
One of the major open problems in complexity theory is proving super-logarithmic 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 super-logarithmic 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 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.
(Less)
- author
- De Rezende, Susanna F.
LU
; Meir, Or
; Nordstrom, Jakob
LU
; Pitassi, Toniann
and Robere, Robert
- organization
- publishing date
- 2020-11
- 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, Karchmer-Wigderson 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
- 2020-November
- 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
- 2020-11-16 - 2020-11-19
- external identifiers
-
- scopus:85100337778
- ISSN
- 0272-5428
- ISBN
- 978-1-7281-9622-0
- 9781728196213
- DOI
- 10.1109/FOCS46700.2020.00013
- language
- English
- LU publication?
- yes
- additional info
- Publisher Copyright: © 2020 IEEE.
- id
- ffc36c30-1050-428a-803d-a12c0bc7ef01
- date added to LUP
- 2021-12-14 15:47:20
- date last changed
- 2024-08-11 03:29:00
@inproceedings{ffc36c30-1050-428a-803d-a12c0bc7ef01,
abstract = {{<p>One of the major open problems in complexity theory is proving super-logarithmic 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 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.</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 = {{978-1-7281-9622-0}},
issn = {{0272-5428}},
keywords = {{circuit complexity; circuit lower bounds; communication complexity; depth complexity; depth lower bounds; formula complexity; formula lower bounds; Karchmer-Wigderson relations; KRW; KW relations; Lifting; Simulation}},
language = {{eng}},
pages = {{43--49}},
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 = {{2020-November}},
year = {{2020}},
}