9 citations · 13 across the 8 of their papers we have counts for
Showing 2023Show all
2 papers · 1 filter
cs.CC2023
Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases
Massimo Lauria, Jakob Nordström
We consider the graph -colouring problem encoded as a set of polynomial equations in the standard way over -valued variables. We prove that there are bounded-degree graphs…
cs.CC2023
Hardness of Approximation in PSPACE and Separation Results for Pebble Games
Siu Man Chan, Massimo Lauria, Jakob Nordström +1
We consider the pebble game on DAGs with bounded fan-in introduced in [Paterson and Hewitt '70] and the reversible version of this game in [Bennett '89], and study the question of…