Showing cs.CCShow all
2 papers · 1 filter
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…
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…