Skip to main content

Lund University Publications

LUND UNIVERSITY LIBRARIES

KRW Composition Theorems via Lifting

Rezende, Susanna F.de LU orcid ; Meir, Or ; Nordström, Jakob LU ; Pitassi, Toniann and Robere, Robert (2024) In Computational Complexity 33(1).
Abstract

One of the major open problems in complexity theory is proving super-logarithmiclower bounds on the depth of circuits (i.e., P⊈NC1). Karchmer et al. (Comput Complex 5(3/4):191–204, 1995) suggested to approach thisproblem by proving that depth complexity behaves “as expected”with respect to the composition of functions f◊g. They showedthat the validity of this conjecture would imply that P⊈NC1.Several works have made progress toward resolving this conjectureby proving special cases. In particular, these works proved the KRWconjecture for every outer function f, but only for few innerfunctions g. Thus, it is an important challenge to prove the KRWconjecture for a wider range of inner functions.In this work, we extend... (More)

One of the major open problems in complexity theory is proving super-logarithmiclower bounds on the depth of circuits (i.e., P⊈NC1). Karchmer et al. (Comput Complex 5(3/4):191–204, 1995) suggested to approach thisproblem by proving that depth complexity behaves “as expected”with respect to the composition of functions f◊g. They showedthat the validity of this conjecture would imply that P⊈NC1.Several works have made progress toward resolving this conjectureby proving special cases. In particular, these works proved the KRWconjecture for every outer function f, but only for few innerfunctions g. Thus, it is an important challenge to prove the KRWconjecture for a wider range of inner functions.In this work, we extend significantly the range of inner functionsthat can be handled. First, we consider the monotone versionof the KRW conjecture. We prove it for every monotone inner function gwhose depth complexity can be lower-bounded via a query-to-communicationlifting theorem. This allows us to handle several new and well-studiedfunctions 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, whichcombines the non-monotone complexity of the outer function f withthe monotone complexity of the inner function g. In this setting,we prove the KRW conjecture for a similar selection of inner functions g,but only for a specific choice of the outer function f.

(Less)
Please use this url to cite or link to this publication:
author
; ; ; and
organization
publishing date
type
Contribution to journal
publication status
published
subject
keywords
68Q06, 68Q11, Circuit complexity, circuit lower Bounds, communication complexity, depth complexity, depth lower bounds, Karchmer–Wigersion relations, KRW conjecture, lifting theorems, simulation theorems
in
Computational Complexity
volume
33
issue
1
article number
4
publisher
Birkhäuser Verlag
external identifiers
  • scopus:85191787679
ISSN
1016-3328
DOI
10.1007/s00037-024-00250-7
language
English
LU publication?
yes
id
46b501fa-f969-4a82-8d42-b6d4f4644943
date added to LUP
2024-05-15 12:23:25
date last changed
2024-05-15 12:24:49
@article{46b501fa-f969-4a82-8d42-b6d4f4644943,
  abstract     = {{<p>One of the major open problems in complexity theory is proving super-logarithmiclower bounds on the depth of circuits (i.e., P⊈NC<sup>1</sup>). Karchmer et al. (Comput Complex 5(3/4):191–204, 1995) suggested to approach thisproblem by proving that depth complexity behaves “as expected”with respect to the composition of functions f◊g. They showedthat the validity of this conjecture would imply that P⊈NC<sup>1</sup>.Several works have made progress toward resolving this conjectureby proving special cases. In particular, these works proved the KRWconjecture for every outer function f, but only for few innerfunctions g. Thus, it is an important challenge to prove the KRWconjecture for a wider range of inner functions.In this work, we extend significantly the range of inner functionsthat can be handled. First, we consider the monotone versionof the KRW conjecture. We prove it for every monotone inner function gwhose depth complexity can be lower-bounded via a query-to-communicationlifting theorem. This allows us to handle several new and well-studiedfunctions 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, whichcombines the non-monotone complexity of the outer function f withthe monotone complexity of the inner function g. In this setting,we prove the KRW conjecture for a similar selection of inner functions g,but only for a specific choice of the outer function f.</p>}},
  author       = {{Rezende, Susanna F.de and Meir, Or and Nordström, Jakob and Pitassi, Toniann and Robere, Robert}},
  issn         = {{1016-3328}},
  keywords     = {{68Q06; 68Q11; Circuit complexity; circuit lower Bounds; communication complexity; depth complexity; depth lower bounds; Karchmer–Wigersion relations; KRW conjecture; lifting theorems; simulation theorems}},
  language     = {{eng}},
  number       = {{1}},
  publisher    = {{Birkhäuser Verlag}},
  series       = {{Computational Complexity}},
  title        = {{KRW Composition Theorems via Lifting}},
  url          = {{http://dx.doi.org/10.1007/s00037-024-00250-7}},
  doi          = {{10.1007/s00037-024-00250-7}},
  volume       = {{33}},
  year         = {{2024}},
}