SwePub
Sök i LIBRIS databas

  Utökad sökning

onr:"swepub:oai:lup.lub.lu.se:693be8c5-3a8f-4dec-9b36-8798a2fda2bc"
 

Sökning: onr:"swepub:oai:lup.lub.lu.se:693be8c5-3a8f-4dec-9b36-8798a2fda2bc" > Clique Is Hard on A...

Clique Is Hard on Average for Unary Sherali-Adams

De Rezende, Susanna F. (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
Potechin, Aaron (författare)
University of Chicago
Risse, Kilian (författare)
Swiss Federal Institute of Technology
 (creator_code:org_t)
2023
2023
Engelska 14 s.
Ingår i: Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. - 0272-5428. - 9798350318944 ; , s. 12-25
  • Konferensbidrag (refereegranskat)
Abstract Ämnesord
Stäng  
  • We prove that unary Sherali-Adams requires proofs of size nΩ(d) to rule out the existence of an nΘ(1)-clique in Erdős-Rényi random graphs whose maximum clique is of size d ≤ 2 log n. This lower bound is tight up to the multiplicative constant in the exponent. We obtain this result by introducing a technique inspired by pseudo-calibration which may be of independent interest. The technique involves defining a measure on monomials that precisely captures the contribution of a monomial to a refutation. This measure intuitively captures progress and should have further applications in proof complexity.

Ämnesord

NATURVETENSKAP  -- Matematik -- Diskret matematik (hsv//swe)
NATURAL SCIENCES  -- Mathematics -- Discrete Mathematics (hsv//eng)

Nyckelord

Clique
Proof Complexity
Unary Sherali Adams

Publikations- och innehållstyp

kon (ämneskategori)
ref (ämneskategori)

Hitta via bibliotek

Till lärosätets databas

Hitta mer i SwePub

Av författaren/redakt...
De Rezende, Susa ...
Potechin, Aaron
Risse, Kilian
Om ämnet
NATURVETENSKAP
NATURVETENSKAP
och Matematik
och Diskret matemati ...
Artiklar i publikationen
Proceedings - 20 ...
Av lärosätet
Lunds universitet

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