All

What are you looking for?

All
Projects
Results
Organizations

Quick search

  • Projects supported by TA ČR
  • Excellent projects
  • Projects with the highest public support
  • Current projects

Smart search

  • That is how I find a specific +word
  • That is how I leave the -word out of the results
  • “That is how I can find the whole phrase”

Krw composition theorems via lifting

The result's identifiers

  • Result code in IS VaVaI

    <a href="https://www.isvavai.cz/riv?ss=detail&h=RIV%2F67985840%3A_____%2F20%3A00539556" target="_blank" >RIV/67985840:_____/20:00539556 - isvavai.cz</a>

  • Result on the web

    <a href="http://dx.doi.org/10.1109/FOCS46700.2020.00013" target="_blank" >http://dx.doi.org/10.1109/FOCS46700.2020.00013</a>

  • DOI - Digital Object Identifier

    <a href="http://dx.doi.org/10.1109/FOCS46700.2020.00013" target="_blank" >10.1109/FOCS46700.2020.00013</a>

Alternative languages

  • Result language

    angličtina

  • Original language name

    Krw composition theorems via lifting

  • Original language description

    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.

  • Czech name

  • Czech description

Classification

  • Type

    D - Article in proceedings

  • CEP classification

  • OECD FORD branch

    10201 - Computer sciences, information science, bioinformathics (hardware development to be 2.2, social aspect to be 5.8)

Result continuities

  • Project

  • Continuities

    I - Institucionalni podpora na dlouhodoby koncepcni rozvoj vyzkumne organizace

Others

  • Publication year

    2020

  • Confidentiality

    S - Úplné a pravdivé údaje o projektu nepodléhají ochraně podle zvláštních právních předpisů

Data specific for result type

  • Article name in the collection

    2020 IEEE 61st Annual Symposium on Foundations of Computer Science

  • ISBN

    978-1-7281-9622-0

  • ISSN

  • e-ISSN

  • Number of pages

    7

  • Pages from-to

    43-49

  • Publisher name

    IEEE

  • Place of publication

    Los Alamitos

  • Event location

    Durham

  • Event date

    Nov 16, 2020

  • Type of event by nationality

    WRD - Celosvětová akce

  • UT code for WoS article