onr:"swepub:oai:lup.lub.lu.se:b3ba0485-3634-49d7-bb21-adccca03701d"
Sökning: onr:"swepub:oai:lup.lub.lu.se:b3ba0485-3634-49d7-bb21-adccca03701d" > Graph Colouring Is ...
- 1 av 1
- Föregående post
- Nästa post
- Till träfflistan
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
-
- Conneryd, Jonas (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
-
- 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
-
- 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...
- visa färre...
- (creator_code:org_t)
- 2023
- 2023
- Engelska 11 s.
- Ingår i: Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. - 0272-5428. - 9798350318944 ; , s. 1-11
- Konferensbidrag (refereegranskat)
Abstract
Ämnesord
Stäng
- We prove that polynomial calculus (and hence also Nullstellensatz) over any field requires linear degree to refute that sparse random regular graphs, as well as sparse Erdős-Rényi random graphs, are 3-colourable.
Ämnesord
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Nyckelord
- average-case complexity
- polynomial calculus
- Proof Complexity
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...
- Conneryd, Jonas
- De Rezende, Susa ...
- Nordstrom, Jakob
- Pang, Shuo
- Risse, Kilian
- Om ämnet
-
- NATURVETENSKAP
- NATURVETENSKAP
- och Data och informa ...
- och Datavetenskap
- 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
