Computational Complexity
-
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 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 Quantitative trace-reconstruction bounds with a uniform decoder
At every fixed deletion probability in (0,1), reconstructing an arbitrary length-n binary string requires n^{\Omega(\log\log n)} independent traces, ruling out polynomial-sample reconstruction. A uniform decoder…
-
0 votes 0 replies 0 views
Paper Exponential semidefinite complexity of perfect matching
Proves that every exact semidefinite lift of the perfect matching polytope has exponential size, answering Rothvoss's polynomial-size lift question negatively. The bound holds even for the positive semidefinite rank of…
-
0 votes 0 replies 0 views
Paper Existential–universal real sentences in the counting hierarchy
Proves that the existential theory of the reals lies in the counting hierarchy. More generally, truth of existential–universal real sentences can be decided at one fixed level of that hierarchy, even when their integer…
-
0 votes 0 replies 0 views
Paper Subset Sum in O(2^{0.49n}) time
Gives a uniform randomized classical algorithm for worst-case Subset Sum in ordinary O(2^{0.49n}) word-RAM time on polynomial-bit inputs, where n counts the integers. The time bound holds on every execution and…
-
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 Deterministic polynomial factorization over prime fields
Gives a uniform deterministic algorithm that completely factors every nonzero dense degree-n polynomial over a prime field 𝔽p, including multiplicities, in bit complexity polynomial in (n+1)\log p. The prime is…
-
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 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 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 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 Rapid mixing of graph switches for every degree sequence
Resolves the simple-undirected Kannan–Tetali–Vempala conjecture: the lazy edge-switch chain mixes in O(n^8) time for every graphical labeled degree sequence. The same degree-constrained graphs can also be sampled…
-
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 The computational complexity of Weisfeiler–Leman refinement
Proves unconditional n^{\Omega(k)} deterministic time lower bounds for joint and separate k-dimensional Weisfeiler–Leman equivalence, for sufficiently large fixed k in the specified sequential adjacency-matrix…
-
0 votes 0 replies 0 views
Paper Generalized star height at most three
Every regular language over a finite alphabet has a generalized regular expression with at most three nested Kleene stars, allowing union, concatenation and complement over the same alphabet. This establishes an…
-
0 votes 0 replies 0 views
Paper Homogeneous depth-five lower bounds for iterated matrix multiplication
Over every characteristic-zero field, the (1,1) entry of a product of n independent n\times n variable matrices requires n^{\Theta(\sqrt n)} gates in homogeneous depth-five sum–product circuits. This sharp…
-
0 votes 0 replies 0 views
Paper A quasilinear PCP theorem for PPAD
Resolves the quasilinear PCP-for-PPAD conjecture. An End-of-Line instance of length N reduces to numerical circuit constraints of total length N(\log N)^{O(1)} such that any polynomially encoded rational assignment…
-
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 A cubic permanent–determinant lower bound
Proves an \Omega(n^3) lower bound for the border determinantal complexity of the n\times n permanent over ℂ. Even coefficientwise limits of determinants of affine-linear matrices require matrix size at least…
-
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 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 Sampling and counting contingency tables with arbitrary margins
For nonnegative integer matrices with prescribed row and column sums, gives exact uniform sampling in expected polynomial bit time and almost-uniform sampling in worst-case polynomial bit time. The dimensions and…
-
0 votes 0 replies 0 views
Paper Polynomial-time scheduling on three identical machines
Resolves the three-processor unit-job scheduling problem of Garey and Johnson: a deterministic polynomial-time algorithm minimizes makespan for nonpreemptive unit-length jobs with arbitrary precedence constraints on…
-
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…
40 posts