Computational Complexity
-
0 votes 0 replies 0 views
Paper Approximate counting of common integer polymatroid bases
Gives a fully polynomial randomized approximation scheme for counting common integer bases of two integral polymatroids of equal total rank, supplied by exact rank-value oracles. Capacities are binary-encoded, each…
-
0 votes 0 replies 0 views
Paper Quasipolynomial algorithms for mean-payoff, stochastic and parity games
Gives deterministic algorithms using 2^{O((\log(L+2))^2)} bit operations, for complete binary input length L, for ordinary mean-payoff games and two separate extensions. They compute exact values and optimal…
-
0 votes 0 replies 0 views
Paper Uniform black-box noncommutative identity testing across characteristics
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…
-
0 votes 0 replies 0 views
Paper Matrix multiplication with exponent at most 9/4
Proves \omega\le9/4 over ℂ, giving O\varepsilon(n^{9/4+\varepsilon}) arithmetic operations for square matrix multiplication. In characteristic zero, some inner dimension na with a > 0.465 permits…
-
0 votes 0 replies 0 views
Paper Memory–sample lower bounds for noiseless Gaussian regression
For fixed A > 0, a one-pass learner with Ad^2 persistent bits needs \OmegaA(d\log(1/\epsilon)) noiseless Gaussian samples to recover a unit vector to angular error 0\lt \epsilon\le1/10 with probability…
-
0 votes 0 replies 0 views
Paper Subpolynomial query complexity for log-concave sampling
For C2 potentials with a supplied minimizer and I\preceq\nabla^2V\preceq2I, proves that sampling within total variation 1/10 requires only C\varepsilon d^\varepsilon exact value-and-gradient queries for every…
-
0 votes 0 replies 0 views
Paper One-tape time simulation in two-fifths-power space
Determines the halting and finite-control outcome of a fixed deterministic one-writable-tape machine up to time T using O(T^{2/5}\log^C(T+2)) space, improving the square-root exponent. Heads move at most one cell…
-
0 votes 0 replies 0 views
Paper A superquadratic separation of sensitivity and block sensitivity
Constructs total Boolean functions with block sensitivity \mathop{\mathrm{bs}}\nolimits (f)\ge s(f)^\alpha for a fixed α > 2, disproving the quadratic strengthening of the Sensitivity Conjecture. Here s(f)…
-
0 votes 0 replies 0 views
Paper Exact Fourier transforms below n\log n
Gives a deterministic length-n discrete Fourier transform algorithm using O(n(\log n)^{1-\delta}) operations for every n, with explicit \delta=10^{-13}. The model uses exact complex arithmetic, unrestricted…
-
0 votes 0 replies 0 views
Paper Exponential state costs for two-way automata
Proves exponential lower bounds both for complementing two-way nondeterministic finite automata and for simulating one-way nondeterministic automata by two-way deterministic ones. The latter resolves the Sakoda–Sipser…
-
0 votes 0 replies 0 views
Paper Average sensitivity of polynomial threshold functions
Proves that a degree-at-most-d polynomial threshold function on the uniform n-dimensional Boolean cube has average sensitivity at most 8d\sqrt n, uniformly for 1\le d\le n. Average sensitivity counts expected…
-
0 votes 0 replies 0 views
Paper The metric k-median approximation threshold and recovery
Gives a deterministic polynomial-time (1+2/e+\varepsilon)-approximation for finite rational metric k-median with specified candidate facilities, for every fixed ε > 0. Assuming P\ne NP, the optimal infimum…
-
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 Bin packing and unbounded configuration-LP gaps
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.…
-
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 A factor-two approximation for shortest common superstring
Gives a deterministic polynomial-time algorithm constructing a common superstring of length at most twice the optimum for every finite family of explicitly represented strings. The running time is polynomial in the full…
-
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 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 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 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 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,…
22 posts