research
∙
05/31/2023
Graph Colouring is Hard for Algorithms Based on Hilbert's Nullstellensatz and Gröbner Bases
We consider the graph k-colouring problem encoded as a set of polynomial...
share
research
∙
05/30/2023
Hardness of Approximation in PSPACE and Separation Results for Pebble Games
We consider the pebble game on DAGs with bounded fan-in introduced in [P...
research
∙
12/30/2021
Verification and generation of unrefinable partitions
Unrefinable partitions are a subset of partitions into distinct parts wh...
research
∙
12/17/2020
Clique Is Hard on Average for Regular Resolution
We prove that for k ≪√(n) regular resolution requires length n^Ω(k) to e...
research
∙
02/14/2018