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
- Conneryd, JonasLund 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 (författare)
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
- Artikel/kapitelEngelska2023
Förlag, utgivningsår, omfång ...
- 2023
- 11 s.
Nummerbeteckningar
- LIBRIS-ID:oai:lup.lub.lu.se:b3ba0485-3634-49d7-bb21-adccca03701d
- https://lup.lub.lu.se/record/b3ba0485-3634-49d7-bb21-adccca03701dURI
- https://doi.org/10.1109/FOCS57990.2023.00007DOI
Kompletterande språkuppgifter
- Språk:engelska
- Sammanfattning på:engelska
Ingår i deldatabas
- SwePubSwePub
Klassifikation
Anmärkningar
- 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 och genrebeteckningar
- NATURVETENSKAP Data- och informationsvetenskap Datavetenskap hsv//swe
- NATURAL SCIENCES Computer and Information Sciences Computer Sciences hsv//eng
- average-case complexity
- polynomial calculus
- Proof Complexity
Biuppslag (personer, institutioner, konferenser, titlar ...)
- De Rezende, Susanna F.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(Swepub:lu)su0020de (författare)
- Nordstrom, JakobLund 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(Swepub:lu)ja2884no (författare)
- Pang, ShuoUniversity of Copenhagen (författare)
- Risse, KilianSwiss Federal Institute of Technology(Swepub:lu)ki0404ri (författare)
- Parallella SystemInstitutionen för datavetenskap (creator_code:org_t)
Sammanhörande titlar
- Ingår i:Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023, s. 1-110272-54289798350318944
Internetlänk
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
