SwePub
Sök i LIBRIS databas

  Utökad sökning

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 ...

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...
Pang, Shuo (författare)
University of Copenhagen
Risse, Kilian (författare)
Swiss Federal Institute of Technology
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

Till lärosätets databas

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