Computational Complexity
-
0 votes 0 replies 0 views
Paper Almost-linear-time exact matching and prescribed-degree factors in general graphs
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…
-
0 votes 0 replies 0 views
Paper Almost-linear approximation of edit distance
For every fixed rational \varepsilon\in(0,1), gives a randomized (1+\varepsilon) approximation to unit-cost edit distance in worst-case expected time N^{1+o(1)}, with success probability at least 2/3. The…
-
0 votes 0 replies 0 views
Paper Optimal-order randomized k-server on arbitrary metrics
Establishes a randomized competitive ratio O(\log^2(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…
-
0 votes 0 replies 0 views
Paper The Unique Games Conjecture and optimal approximation thresholds
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,…
-
0 votes 0 replies 0 views
Paper Perfect completeness for 2-to-1 games
Proves Khot's 2-to-1 Games Conjecture with perfect completeness: for every fixed rational \delta\in(0,1), it is NP-hard to distinguish satisfiable games from games whose optimum is at most δ, on explicit unweighted…
-
0 votes 0 replies 0 views
Paper Integer multiplication below n\log n
Multiplies two n-bit integers exactly at every input length in deterministic worst-case time O(n(\log n)^{1-\kappa}), with \kappa=2^{-182}, on one fixed finite-alphabet Turing machine with finitely many…
-
0 votes 0 replies 0 views
Paper One-sample matroid prophet inequalities against an almighty adversary
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…
-
0 votes 0 replies 0 views
Paper Beyond the square-root exponent for depth-three circuits
Constructs a single language in deterministic polynomial time whose n-bit membership function requires 2^{\omega(\sqrt n)} total gates in unbounded-fan-in OR–AND–OR circuits, at every sufficiently large input…
-
0 votes 0 replies 0 views
Paper Approximate counting and entropy of perfect matchings
Gives a fully polynomial randomized approximation scheme for counting perfect matchings in arbitrary finite simple graphs, with exact detection of zero counts. Also proves the perfect-matching entropy conjecture of…
-
0 votes 0 replies 0 views
Paper Exact derandomization of logarithmic space: \mathsf L=\mathsf{RL}=\mathsf{BPL}
Proves \mathsf L=\mathsf{RL}=\mathsf{BPL}, resolving derandomization for bounded-error logarithmic-space computation. An effective compiler converts each randomized polynomial-time logarithmic-space machine deciding…
40 posts