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...
- 1 av 1
- Föregående post
- Nästa post
- Till träfflistan
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
- Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science... (Sök värdpublikationen i LIBRIS)
Till lärosätets databas
- 1 av 1
- Föregående post
- Nästa post
- Till träfflistan
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
- Sök vidare i:
- Google Book Search
- Google Scholar
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.
- Copyright © LIBRIS - Nationella bibliotekssystem
- LIBRIS.kb.se
