SwePub
Sök i SwePub databas

  Utökad sökning

Träfflista för sökning "WFRF:(Lauria Massimo) srt2:(2017)"

Sökning: WFRF:(Lauria Massimo) > (2017)

  • Resultat 1-2 av 2
Sortera/gruppera träfflistan
   
NumreringReferensOmslagsbildHitta
1.
  • Lauria, Massimo, et al. (författare)
  • The complexity of proving that a graph is Ramsey
  • 2017
  • Ingår i: Combinatorica. - : SPRINGER HEIDELBERG. - 0209-9683 .- 1439-6912. ; 37:2, s. 253-268
  • Tidskriftsartikel (refereegranskat)abstract
    • We say that a graph with n vertices is c-Ramsey if it does not contain either a clique or an independent set of size c log n. We define a CNF formula which expresses this property for a graph G. We show a superpolynomial lower bound on the length of resolution proofs that G is c-Ramsey, for every graph G. Our proof makes use of the fact that every c-Ramsey graph must contain a large subgraph with some properties typical for random graphs.
  •  
2.
  • Lauria, Massimo, et al. (författare)
  • Tight Size-Degree Bounds for Sums-of-Squares Proofs
  • 2017
  • Ingår i: Computational Complexity. - : SPRINGER BASEL AG. - 1016-3328 .- 1420-8954. ; 26:4, s. 911-948
  • Tidskriftsartikel (refereegranskat)abstract
    • We exhibit families of 4-CNF formulas over n variables that have sums-of-squares (SOS) proofs of unsatisfiability of degree (a.k.a. rank) d but require SOS proofs of size for values of d = d(n) from constant all the way up to for some universal constant . This shows that the running time obtained by using the Lasserre semidefinite programming relaxations to find degree-d SOS proofs is optimal up to constant factors in the exponent. We establish this result by combining NP-reductions expressible as low-degree SOS derivations with the idea of relativizing CNF formulas in Krajiek (Arch Math Log 43(4):427-441, 2004) and Dantchev & Riis (Proceedings of the 17th international workshop on computer science logic (CSL '03), 2003) and then applying a restriction argument as in Atserias et al. (J Symb Log 80(2):450-476, 2015; ACM Trans Comput Log 17:19:1-19:30, 2016). This yields a generic method of amplifying SOS degree lower bounds to size lower bounds and also generalizes the approach used in Atserias et al. (2016) to obtain size lower bounds for the proof systems resolution, polynomial calculus, and Sherali-Adams from lower bounds on width, degree, and rank, respectively.
  •  
Skapa referenser, mejla, bekava och länka
  • Resultat 1-2 av 2
Typ av publikation
tidskriftsartikel (2)
Typ av innehåll
refereegranskat (2)
Författare/redaktör
Lauria, Massimo (2)
Nordström, Jakob, 19 ... (1)
Thapen, Neil (1)
Pudlak, Pavel (1)
Rodl, Vojtch (1)
Lärosäte
Kungliga Tekniska Högskolan (2)
Språk
Engelska (2)
Forskningsämne (UKÄ/SCB)
Naturvetenskap (2)
År
2017 (2)Ta bort avgränsningen

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