Search: L773:0272 5428 OR L773:9781728196213 OR L773:9781728196220
> (2020-2023) >
Graph Colouring Is ...
Graph Colouring Is Hard on Average for Polynomial Calculus and Nullstellensatz
-
- Conneryd, Jonas (author)
- 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. (author)
- 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 (author)
- 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
-
show more...
-
- Pang, Shuo (author)
- University of Copenhagen
-
- Risse, Kilian (author)
- Swiss Federal Institute of Technology
-
show less...
-
(creator_code:org_t)
- 2023
- 2023
- English 11 s.
-
In: Proceedings - 2023 IEEE 64th Annual Symposium on Foundations of Computer Science, FOCS 2023. - 0272-5428. - 9798350318944 ; , s. 1-11
- Related links:
-
http://dx.doi.org/10...
-
show more...
-
https://lup.lub.lu.s...
-
https://doi.org/10.1...
-
show less...
Abstract
Subject headings
Close
- 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.
Subject headings
- NATURVETENSKAP -- Data- och informationsvetenskap -- Datavetenskap (hsv//swe)
- NATURAL SCIENCES -- Computer and Information Sciences -- Computer Sciences (hsv//eng)
Keyword
- average-case complexity
- polynomial calculus
- Proof Complexity
Publication and Content Type
- kon (subject category)
- ref (subject category)
Find in a library
To the university's database