SwePub
Sök i LIBRIS databas

  Utökad sökning

onr:"swepub:oai:lup.lub.lu.se:ffc36c30-1050-428a-803d-a12c0bc7ef01"
 

Sökning: onr:"swepub:oai:lup.lub.lu.se:ffc36c30-1050-428a-803d-a12c0bc7ef01" > KRW composition the...

KRW composition theorems via lifting

De Rezende, Susanna F. (författare)
Institute of Mathematics of the Academy of Sciences of the Czech Republic
Meir, Or (författare)
University of Haifa
Nordstrom, Jakob (författare)
Lund University,Lunds universitet,Parallella System,Institutionen för datavetenskap,Institutioner vid LTH,Lunds Tekniska Högskola,Parallel Systems,Department of Computer Science,Departments at LTH,Faculty of Engineering, LTH,University of Copenhagen
visa fler...
Pitassi, Toniann (författare)
Institute for Advanced Study, Princeton
Robere, Robert (författare)
McGill University
visa färre...
 (creator_code:org_t)
2020
2020
Engelska 7 s.
Ingår i: Proceedings - 2020 IEEE 61st Annual Symposium on Foundations of Computer Science, FOCS 2020. - 0272-5428. - 9781728196220 - 9781728196213 ; 2020-November, s. 43-49
  • Konferensbidrag (refereegranskat)
Abstract Ämnesord
Stäng  
  • 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.

Ämnesord

NATURVETENSKAP  -- Matematik -- Matematisk analys (hsv//swe)
NATURAL SCIENCES  -- Mathematics -- Mathematical Analysis (hsv//eng)
NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Nyckelord

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

Publikations- och innehållstyp

kon (ämneskategori)
ref (ämneskategori)

Hitta via bibliotek

Till lärosätets databas

Sök utanför SwePub

Kungliga biblioteket hanterar dina personuppgifter i enlighet med EU:s dataskyddsförordning (2018), GDPR. Läs mer om hur det funkar här.
Så här hanterar KB dina uppgifter vid användning av denna tjänst.

 
pil uppåt Stäng

Kopiera och spara länken för att återkomma till aktuell vy