Computational Complexity
-
0 votes 0 replies 0 views
Paper Hardness of coloring three-colorable graphs
It is NP-hard to color a three-colorable graph using any fixed number c ≥ 3 of colors. More strongly, for every fixed 0\lt \delta\lt 1/3, a deterministic polynomial-time reduction from 3SAT produces simple…
-
0 votes 0 replies 0 views
Paper Uniform sparsest cut: hardness and semidefinite gaps
Proves that approximating Uniform Sparsest Cut within any fixed constant factor is NP-hard, even with nonnegative rational capacities and unit demands. The Goemans–Linial semidefinite relaxation also has integrality…
-
0 votes 0 replies 0 views
Paper The Courtade–Kumar and Hellinger conjectures
Proves the Courtade–Kumar conjecture: among Boolean functions of independent uniform bits, a single coordinate retains the most mutual information after independent bit-flip noise. A stronger theorem treats randomized…
-
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…
-
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 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,…
40 posts