3 papers
cs.CC2025
On the Usefulness of Promises
Per Austrin, Johan Håstad, Björn Martinsson
A Boolean predicate is defined to be promise-useful if is tractable for some non-trivial and otherwise it is promise-useless. We initiate investi…
math.CO2025
A logarithmic approximation of linearly ordered colourings
Johan Håstad, Björn Martinsson, Tamio-Vesa Nakajima +1
A linearly ordered (LO) -colouring of a hypergraph assigns to each vertex a colour from the set in such a way that each hyperedge has a unique maximum eleme…
cs.CC2024
On the NP-Hardness Approximation Curve for Max-2Lin(2)
Björn Martinsson
In the Max-2Lin(2) problem you are given a system of equations on the form , and your objective is to find an assignment that satisfies as many equatio…