Unique Games Conjecture, Bin Packing and 8 More in Theoretical Computer Science

Proves Khot's Unique Games Conjecture. Independent direct reductions also establish NP-hardness, on unweighted graphs, of approximation beyond the Goemans–Williamson ratio for Max-Cut, below factor two for Vertex Cover, and within any fixed constant factor for Min-UnCut and directed feedback vertex set. These direct proofs use established PCP and Label Cover hardness results. (Lean)

Proves Khot's 2-to-1 Games Conjecture with perfect completeness: for every fixed rational δ ∈ (0,1), it is NP-hard to distinguish satisfiable games from games whose optimum is at most δ, on explicit unweighted instances. The alphabet depends only on δ, and every right-hand label has exactly two preimages under each constraint map. (Lean)

It is NP-hard to color a three-colorable graph using any fixed number c ≥ 3 of colors. More strongly, for every fixed 0 < δ < 1/3, a deterministic polynomial-time reduction from 3SAT produces simple unweighted graphs that are three-colorable in the satisfiable case and have no independent set of size δ n otherwise, where n is the number of vertices. (Lean)

Proves an Ω(n³) lower bound for the border determinantal complexity of the n× n permanent over ℂ. Even coefficientwise limits of determinants of affine-linear matrices require matrix size at least cn³, for an absolute c > 0 and all sufficiently large n; the same bound therefore holds for exact representations. (Lean)

Establishes a randomized competitive ratio O(log²(k+1)) for k-server on every metric space, matching the worst-case lower-bound order. One policy serves every finite oblivious request sequence, including on infinite unbounded metrics. On finite rational metrics, a uniform implementation has polynomial preprocessing and per-request bit cost in the input length and log(t+1) at request t, with a finite instance-dependent additive movement constant. (Lean)

For every finite matroid known in advance, gives a distribution-independent online rule using one independent sample per element and earning a universal constant fraction of the expected offline optimum. Values are independent and nonnegative, with finite expected optimum. The guarantee holds even when the arrival-order adversary sees all samples, values, and the rule's entire random seed; no polynomial-time implementation is asserted. (Lean)

For each characteristic, constructs in deterministic polynomial bit time a polynomial-dimensional matrix tuple detecting every nonzero division-free noncommutative formula of bounded size over any field of that characteristic. Rational formulas over ℚ also admit polynomial-size hitting lists whenever they have a defined rational-matrix evaluation. (Lean)

Disproves the modified integer round-up conjecture of Scheithauer and Terno: the integral bin-packing optimum can exceed its configuration linear-programming value by an arbitrarily large additive constant. Approximating the optimum within any fixed additive constant is also NP-hard, even when every item exceeds 1/6 and each bin holds at most five items. (Lean)

Gives a randomized algorithm finding an exact maximum-cardinality matching in any simple undirected graph in (n+m)^1+o(1) word time, with success probability at least 2/3. The time bound holds on every computation path. The same guarantees apply to finding a spanning subgraph with prescribed admissible vertex degrees, or deciding that none exists.

For every fixed rational ε ∈ (0,1), gives a randomized (1+ε) approximation to unit-cost edit distance in worst-case expected time N^1+o(1), with success probability at least 2/3. The strings have total length N and polynomially bounded integer symbols. This is an asymptotic guarantee at fixed accuracy. (Lean)