In the Max-2Lin(2) problem you are given a system of equations on the form xi + xj ≡ b (mod 2), and your objective is to find an assignment that satisfies as many equations as possible. Let c ∈ [0.5, 1] denote the maximum fraction of satisfiable equations. In this paper we construct a curve s(c) such that it is NP-hard to find a solution satisfying at least a fraction s of equations. This curve either matches or improves all of the previously known inapproximability NP-hardness results for Max-2Lin(2). In particular, we show that if c ≥ 0.9232 then 1−1−s(cc) > 1.48969, which improves the NP-hardness inapproximability constant for the min deletion version of Max-2Lin(2). Our work complements the work of O’Donnell and Wu that studied the same question assuming the Unique Games Conjecture. Similar to earlier inapproximability results for Max-2Lin(2), we use a gadget reduction from the (2k − 1)-ary Hadamard predicate. Previous works used k ranging from 2 to 4. Our main result is a procedure for taking a gadget for some fixed k, and use it as a building block to construct better and better gadgets as k tends to infinity. Our method can be used to boost the result of both smaller gadgets created by hand (k = 3) or larger gadgets constructed using a computer (k = 4).

A linearly ordered (LO) k-colouring of a hypergraph assigns to each vertex a colour from the set {0,1,…,k−1} in such a way that each hyperedge has a unique maximum element. Barto, Batistelli, and Berg conjectured that it is NP-hard to find an LO k-colouring of an LO 2-colourable 3-uniform hypergraph for any constant k≥2 [STACS'21] but even the case k=3 is still open. Nakajima and Živný gave polynomial-time algorithms for finding, given an LO 2-colourable 3-uniform hypergraph, an LO colouring with O∗(n−−√) colours [ICALP'22] and an LO colouring with O∗(n−−√3) colours [ACM ToCT'23]. Very recently, Louis, Newman, and Ray gave an SDP-based algorithm with O∗(n−−√5) colours [FSTTCS'24]. We present two simple polynomial-time algorithms that find an LO colouring with O(log2(n)) colours, which is an exponential improvement. 

A Boolean predicate A is defined to be promise-useful if PCSP(A B)  is tractable for some non-trivial B and otherwise it is promise-useless. We initiate investigations of this notion and derive sufficient conditions for both promise-usefulness and promise-uselessness (assuming P is not equal to NP ). While we do not obtain a complete characterization, our conditions are sufficient to classify all predicates of arity at most 4 and almost all predicates of arity 5. We also derive asymptotic results to show that for large arities a vast majority of all predicates are promise-useless.

Our results are primarily obtained by a thorough study of the ``Promise-SAT'' problem, in which we are given a k-SAT instance with the promise that there is a satisfying assignment for which the literal values of each clause satisfy some additional constraint.

The algorithmic results are based on the basic LP + affine IP algorithm of Brakensiek et al.~(SICOMP, 2020) while we use a number of novel criteria to establish NP-hardness.