L = BPL, Matrix Multiplication Exponent, Integer Multiplication and 6 More

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 per step; finitely many read-only input heads are allowed. Initial contents are independent of T, and contents and input symbols have polylogarithmic-space access. Simulation time is unrestricted. (Lean)

For C2 potentials with a supplied minimizer and I ⪯ ∇²V ⪯ 2I, proves that sampling within total variation 1/10 requires only C_ε d^ε exact value-and-gradient queries for every fixed ε > 0. The bound holds on every run, with unrestricted computation between queries. A logarithmic lower bound also holds, so the optimal power-law exponent in this oracle model is zero. (Lean)

For fixed A > 0, a one-pass learner with Ad² persistent bits needs Ω_A(d log(1/ϵ)) noiseless Gaussian samples to recover a unit vector to angular error 0 < ϵ ≤ 1/10 with probability 2/3, uniformly in accuracy for large d. Computation and randomized updates are unrestricted, but output uses only the terminal state, stopping index and fresh randomness. (Lean)

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 polynomials are specified by arithmetic circuits.

Proves L=RL=BPL, resolving derandomization for bounded-error logarithmic-space computation. An effective compiler converts each randomized polynomial-time logarithmic-space machine deciding a language with one-sided or two-sided error into a deterministic logarithmic-space decider with explicit polynomial running-time bounds. (Lean)

Proves ω ≤ 9/4 over ℂ, giving O_ε(n^9/4+ε) arithmetic operations for square matrix multiplication. In characteristic zero, some inner dimension na with a > 0.465 permits n^2+o(1) rectangular multiplication. Further square bounds give ω < 2.258 outside finitely many positive characteristics and ω < 2.371054886006746 over every fixed field. (Lean)

Multiplies two n-bit integers exactly at every input length in deterministic worst-case time O(n(log n)^1-κ), with κ=2^-182, on one fixed finite-alphabet Turing machine with finitely many one-dimensional tapes. This disproves the Schönhage–Strassen n log n optimality conjecture in the ordinary multitape bit model.

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 Anari, Oveis Gharan, and Vinzant, bounding the maximum entropy of a matching law at every feasible edge-marginal vector in a loopless labelled multigraph, including boundary points. (Lean)

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 integer vector counts once, and oracle calls and bit operations outside the oracles are polynomial on every execution. For matroids presented by independence oracles, the results also cover common independent sets of prescribed, unrestricted, or maximum cardinality, even when the ranks differ. (Lean)