activity
20082023
most citedFrom Small Space to Small Width in Resolution

9 citations · 15 across the 11 of their papers we have counts for

collaborators
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…