SwePub
Sök i LIBRIS databas

  Utökad sökning

onr:"swepub:oai:DiVA.org:kth-200426"
 

Sökning: onr:"swepub:oai:DiVA.org:kth-200426" > How Limited Interac...

How Limited Interaction Hinders Real Communication (and What It Means for Proof and Circuit Complexity)

de Rezende, Susanna F. (författare)
KTH,Teoretisk datalogi, TCS
Nordström, Jakob (författare)
KTH,Teoretisk datalogi, TCS
Vinyals, Marc (författare)
KTH,Teoretisk datalogi, TCS
 (creator_code:org_t)
IEEE Computer Society, 2016
2016
Engelska.
Ingår i: 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS). - : IEEE Computer Society. - 9781509039333 ; , s. 295-304
  • Konferensbidrag (refereegranskat)
Abstract Ämnesord
Stäng  
  • We obtain the first true size-space trade-offs for the cutting planes proof system, where the upper bounds hold for size and total space for derivations with constant-size coefficients, and the lower bounds apply to length and formula space (i.e., number of inequalities in memory) even for derivations with exponentially large coefficients. These are also the first trade-offs to hold uniformly for resolution, polynomial calculus and cutting planes, thus capturing the main methods of reasoning used in current state-of-the-art SAT solvers. We prove our results by a reduction to communication lower bounds in a round-efficient version of the real communication model of [Krajicek ' 98], drawing on and extending techniques in [Raz and McKenzie ' 99] and [Goos et al. '15]. The communication lower bounds are in turn established by a reduction to trade-offs between cost and number of rounds in the game of [Dymond and Tompa '85] played on directed acyclic graphs. As a by-product of the techniques developed to show these proof complexity trade-off results, we also obtain an exponential separation between monotone-AC(i-1) and monotone-AC(i), improving exponentially over the superpolynomial separation in [Raz and McKenzie ' 99]. That is, we give an explicit Boolean function that can be computed by monotone Boolean circuits of depth log(i) n and polynomial size, but for which circuits of depth O (log(i-1) n) require exponential size.

Ämnesord

NATURVETENSKAP  -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
NATURAL SCIENCES  -- Computer and Information Sciences -- Computer Sciences (hsv//eng)

Nyckelord

proof complexity
communication complexity
circuit complexity
cutting planes
trade-offs
pebble games

Publikations- och innehållstyp

ref (ämneskategori)
kon (ämneskategori)

Hitta via bibliotek

Till lärosätets databas

Hitta mer i SwePub

Av författaren/redakt...
de Rezende, Susa ...
Nordström, Jakob
Vinyals, Marc
Om ämnet
NATURVETENSKAP
NATURVETENSKAP
och Data och informa ...
och Datavetenskap
Artiklar i publikationen
2016 IEEE 57th A ...
Av lärosätet
Kungliga Tekniska Högskolan

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