OpenAI Math Collection: Theoretical Computer Science, Combinatorics, Logic and Related Results

We prove the Unique Games Conjecture. For every fixed \(\varepsilon,\delta\in(0,1/2)\), we give a deterministic polynomial-time reduction from 3SAT to Unique Games over a fixed finite alphabet, with completeness at least \(1-\varepsilon\) and soundness at most δ.

We prove that approximating Max-Cut on simple unweighted graphs within any fixed factor greater than the Goemans–Williamson constant is NP-hard.

We prove that minimum Vertex Cover is NP-hard to approximate within every fixed factor below two, even on simple unweighted graphs.

For every fixed C > 1, approximating Min-UnCut within factor C is NP-hard, even on simple undirected unweighted graphs.

Approximating minimum directed feedback vertex set within any fixed constant factor is NP-hard, even on unweighted digraphs.

We prove \(\mathsf L=\mathsf{RL}=\mathsf{BPL}\), resolving the derandomization problem for polynomial-time randomized logarithmic space.

We give a uniform deterministic quasipolynomial-time algorithm for finite turn-based stochastic mean-payoff games with signed integer rewards and rational chance-transition probabilities encoded in binary. It computes exactly the vertices of nonnegative value, including value zero, for the expectation of the pathwise liminf mean payoff. The algorithm uses exact rational arithmetic and \(2^{O((\log(L+2))^2)}\) bit operations, where L is the complete binary input length.

We give a uniform deterministic quasipolynomial-time algorithm for mean-payoff parity games. It computes all vertices from which a player can enforce both nonnegative liminf mean payoff and the parity condition, with arbitrary signed binary rewards and unrestricted binary priorities. The running time is \(2^{O((\log(L+2))^2)}\) bit operations, where L is the complete input length.

We give a deterministic algorithm that computes the complete zero-threshold winning set of a finite mean-payoff game with arbitrary signed integer edge weights encoded in binary. For total explicit input length L, it uses \(2^{O((\log(L+2))^2)}\) bit operations. A reduction also computes the exact rational value at every vertex and globally optimal positional strategies for both players within the same quasipolynomial bound.

We give a randomized algorithm that computes the complete zero-threshold winning set of a finite mean-payoff game with arbitrary signed integer edge weights encoded in binary. For total explicit input length L, it uses \(2^{O((\log(L+2))^2)}\) bit operations on every random tape and is correct with probability at least 7/8. A polynomial-time check certifies the winning regions and positional strategies for both players or reports failure. Independent repetition therefore gives an always-correct algorithm with the same expected quasipolynomial bit bound.

We prove the 2-to-1 Games Conjecture with perfect completeness. For every fixed rational \(\delta\in(0,1)\), it is NP-hard to distinguish satisfiable 2-to-1 games from games of value at most δ, with a fixed alphabet and an explicitly listed unweighted multiset of constraints.

We prove that, for every fixed \(0\lt \delta\lt 1/3\), it is NP-hard to distinguish three-colorable graphs from graphs in which every independent set has fewer than δ times the number of vertices. Consequently, for every fixed integer c ≥ 3, finding a proper c-coloring of a three-colorable graph is NP-hard.

We prove that the exponent of matrix multiplication over the complex numbers is at most 9/4.

Over every field of characteristic zero, we prove that the square matrix-multiplication exponent satisfies ω < 2.258, the dual exponent satisfies α > 0.465, and \(\omega(1,0.709,1)\lt 2.092\). The strict square and k = 0.709 rectangular bounds also hold over every field except possibly in one finite set of positive characteristics, in the arithmetic-operation model.

We prove that the arithmetic exponent of square matrix multiplication over every fixed field satisfies ω < 2.371054886006746. This includes every positive characteristic.

We prove that the complex border determinantal complexity of the \(m\times m\) permanent is \(\Omega(m^3)\), allowing arbitrary affine-linear determinant representations and coefficientwise limits. It also gives cubic lower bounds for exact determinantal complexity and for the numbers of vertices and edges in affine-linear algebraic branching programs, including coefficientwise limits with a fixed vertex or edge budget.

We give a deterministic algorithm that multiplies two n-bit integers in \(O(n(\lg n)^{1-\kappa})\) worst-case time, with \(\kappa=2^{-182}\), on one fixed finite-alphabet Turing machine with a fixed finite number of one-dimensional tapes. The algorithm is exact for every input length and disproves the \(n\log n\) optimality conjecture of Schönhage and Strassen in this model.

We prove that randomized k-server has competitive ratio \(O((\log(k+1))^2)\) on every metric space against oblivious request sequences, matching the known worst-case lower bound. For each metric and initial configuration, one policy works for all finite request sequences, including on infinite and unbounded spaces. When the initial server positions are distinct, no additive term is needed.

We construct a uniform randomized k-server algorithm on finite rational metrics with competitive ratio \(O(\log^2(k+1))\) against oblivious request sequences. Preprocessing is polynomial in the input length, and per-request bit complexity is polynomial in that length and the binary request-counter length. The additive movement constant is finite and instance-dependent, but may be enormous. The construction uses the companion squared-logarithmic existence theorem.

We prove that one independent sample per element suffices for a constant-competitive prophet inequality on every finite matroid. The guarantee holds even when the arrival-order adversary observes all samples, all online values, and the algorithm's entire random seed. The rule needs no description of the value distributions and achieves the absolute competitive ratio \(2^{-310}\).

We construct a language in deterministic polynomial time whose n-bit membership function requires \(2^{\omega(\sqrt n)}\) gates in an unbounded-fan-in OR–AND–OR circuit. The bound holds at every sufficiently large input length and counts all gates, including the bottom layer.

We give a fully polynomial randomized approximation scheme (FPRAS) for counting perfect matchings in arbitrary finite simple undirected graphs, resolving the general-graph perfect-matching approximation problem. The algorithm returns zero with certainty when no perfect matching exists. Otherwise, it achieves relative error ε with failure probability at most δ in worst-case bit time polynomial in the input length, \(\varepsilon ^{-1}\), and \(\log\delta^{-1}\).

We prove the perfect-matching entropy conjecture of Anari, Oveis Gharan, and Vinzant. For every feasible vector x of perfect-matching edge marginals in a loopless labelled multigraph on \(2m\ge2\) vertices, the maximum entropy \(H(x)\) of a matching law with marginals x satisfies \(\displaystyle F(x)-(2-2/m)B(x)\le H(x)\le F(x),\) where \(F(x)=-\sum_e x_e\log x_e\) and \(B(x)=-\sum_e(1-x_e)\log(1-x_e)\). This bound holds throughout the polytope, including its boundary. We also prove the sharp bound \(|\mathop{\mathrm{supp}}\nolimits x|-\dim F_x\le3m-2\), where F_x is the minimal face of the perfect-matching polytope containing x.

We give a fully polynomial randomized approximation scheme for counting common integer bases of two polymatroids with the same total rank, supplied by exact rank-value oracles. The total rank and capacities are encoded in binary, and each integer vector is counted once. On every execution, the number of oracle calls and the bit work outside the oracles are bounded by a fixed polynomial in the ground-set size, the binary input length, the inverse relative-error tolerance, and the logarithm of the inverse failure probability. The algorithm handles binary capacities directly, without expanding them into labelled copies.

We give a fully polynomial randomized approximation scheme for counting the common bases of two arbitrary matroids of the same rank, supplied by independence oracles. The algorithm requires no explicit representation of either matroid and has polynomial bounds on both oracle calls and bit operations on every execution.

We give an exact uniform sampler for nonnegative integer contingency tables with arbitrary prescribed margins. It terminates almost surely and has expected bit complexity polynomial in both dimensions and the binary length of the margins. No positivity, balance, sparsity, or fixed-dimension assumption is required.

We give a fully polynomial randomized approximation scheme for counting nonnegative integer matrices with prescribed row sums, column sums, and individual entry bounds. Both dimensions vary, all numerical data are encoded in binary, and zero bounds are allowed. The algorithm uses only unbiased random bits and has a polynomial bound on its bit operations on every execution.

We construct a single matrix substitution that detects every nonzero size-s division-free noncommutative formula in n variables over every field of a given positive characteristic. One deterministic machine, given a promised prime p in binary and n, s in unary, outputs matrices over 𝔽_p of dimension \(O(n^3s^6)\) in polynomial bit time. The same tuple works with arbitrary extension-field coefficients, including in characteristic two. The construction also applies to the stated acyclic algebraic path programs.

We construct, in deterministic polynomial bit time, one tuple of rational matrices that detects every nonzero polynomial computed by a noncommutative division-free formula of a prescribed size. The matrices have dimension \(O(ns^2)\) for n variables and formula size s, and the same tuple works over every field of characteristic zero.

We construct, in deterministic polynomial bit time, a polynomial-size list of rational matrix tuples for noncommutative rational formulas over ℚ of bounded tree size. Every nonzero admissible formula has a defined, invertible value at one tuple, with no separate bounds on inverse nesting or rational constant heights. Matrix dimensions, entry bit lengths, and total output length are polynomially bounded.

We prove that, for every fixed C > 1, approximating Uniform Sparsest Cut within factor C is NP-hard. The output graphs have nonnegative rational capacities and unit demand between every pair of distinct vertices.

We construct uniform sparsest-cut instances whose Goemans–Linial semidefinite integrality gap is at least \(c\sqrt{\log n}/(\log\log n)^3\) along a sequence \(n\to\infty\). The demand is one between every pair of distinct vertices, and the capacities are nonnegative real numbers. This matches the Arora–Rao–Vazirani upper bound up to a power of \(\log\log n\).

We disprove the Modified Integer Round-Up Conjecture for bin packing by constructing instances with arbitrarily large additive gaps between the configuration-LP value and the integral optimum. We also prove that, for every fixed nonnegative integer c, distinguishing instances that fit in B bins from those requiring more than \(B+c\) bins is NP-hard. Both results hold with rational item sizes greater than 1/6, so each bin contains at most five items.

We prove sharp contraction of the information carried by a binary channel under independent symmetric noise on a uniform discrete cube. At fixed initial information, a noisy coordinate retains the most information. The Boolean specialization resolves the Courtade–Kumar conjecture and gives an output-entropy refinement. We also establish a stronger mean-dependent entropy-production bound. The proof combines an explicit three-point optimizer for the local joining problem, two entropy capacities, and a common-output thinning inequality, followed by dimension induction and integration along the noise semigroup.

We prove the Hellinger conjecture for Boolean functions on the uniform discrete cube, with arbitrary output bias. For a Boolean function of mean m and every \(\rho\in[-1,1]\), the loss \(\sqrt{1-m^2}-\mathbb E\sqrt{1-(T_\rho f)^2}\) is at most \(1-\sqrt{1-\rho^2}\), with equality for signed coordinates. The proof combines asymmetric dimension induction, a calibrated noise-semigroup energy estimate, and finite exact arithmetic certificates. The Hellinger inequality also yields the Courtade–Kumar information bound.

We prove that maximum-cardinality matching in a simple undirected graph with n vertices and m edges can be found by one uniform randomized algorithm in \((n+m)^{1+o(1)}\) time. The bound holds on every computation path in a logarithmic-word model, and the algorithm returns an explicit maximum matching with probability at least 2/3. An explicit reduction gives the same time and probability guarantees for deciding whether a simple host graph has a spanning subgraph with prescribed valid vertex degrees, and for finding one when it exists.

We give a uniform randomized approximation scheme for unit-cost edit distance. For every fixed rational \(\varepsilon\in(0,1)\), it estimates the distance between arbitrary explicitly stored strings of total length N within a factor \(1+\varepsilon\) with probability at least 2/3, in worst-case expected time \(N^{1+o(1)}\) on a logarithmic-word RAM. The algorithm supports polynomially bounded integer alphabets and returns zero deterministically on equal strings.

We give a uniform algorithm that reconstructs every binary string from independent deletion traces when its length and rational retention probability are known. For each fixed retention probability, both the number of traces and the bit complexity are quasipolynomial in the string length. More generally, we give an explicit sample bound uniform over all rational retention probabilities, with running time polynomial in the sample budget and the binary input length. If the deletion probability is at most \(n^{-\varepsilon}\) for fixed ε > 0, the sample and running-time bounds are polynomial. Reconstruction succeeds with probability at least 2/3 for each input string.

We give an improved worst-case sample bound for reconstructing a string from independent deletion traces, with its length and retention probability known. For each fixed retention probability, the number of traces is quasipolynomial: the logarithm of the sample budget is \(O((\log n)^3(1+\log\log(2n))^6)\). If the deletion probability is at most \(n^{-\varepsilon}\) for fixed ε > 0, polynomially many traces suffice. These bounds apply to binary strings and to strings of general symbols observed exactly. They concern sample complexity and do not assert an efficient reconstruction algorithm or matching optimality.

Exact worst-case reconstruction of a binary word from independent deletion traces requires \(n^{\Omega(\log\log n)}\) samples for every fixed deletion probability \(q\in(0,1)\), even with unrestricted computation and any fixed positive success probability. This gives a negative answer to the polynomial-sample question for binary trace reconstruction. More generally, when \(q^3\log n\to\infty\), we prove a lower bound of \(n^{c\log(q^3\log n)}\) samples for every fixed \(0\lt c\lt 1/(4\log2)\). Here q is the known deletion probability, and all logarithms are natural.

We give a uniform deterministic polynomial-time algorithm for scheduling unit-length jobs with arbitrary precedence constraints on three identical parallel machines. The algorithm constructs a schedule of minimum makespan and decides exactly whether all jobs can finish by a specified deadline. The proof reorganizes feasible schedules into intervals whose job sets have descriptions of bounded size. A dynamic program searches a family containing polynomially many such descriptions. Global boundary conditions and simplification of inherited information keep the descriptions bounded throughout the decomposition.

We give an exact-budget recovery algorithm for metric k-median with single-exponential dependence on the number of comparison clusters without accurate, distinct proxies in a supplied anchor solution. On positive integral metrics of polynomially bounded diameter, a sufficiently small total proxy error and logarithmically many such clusters yield a \((1+2/e+\varepsilon)\) approximation in polynomial time with arbitrarily high success probability. We also prove bounded-price strictness for one compatible execution of the logarithmic-surplus construction. Together the recovery and payment arguments give a randomized \((2-\sigma)\) approximation, for an absolute σ > 0, on arbitrary finite rational metrics, both with high probability and in expectation, while opening at most k facilities on every output.

For every fixed ε > 0, we give a deterministic polynomial-time \((1+2/e+\varepsilon)\)-approximation for finite rational metric k-median with specified candidate facilities, opening at most k facilities. Under \(P\ne NP\), the infimum approximation factor in this model is therefore \(1+2/e\).

For every fixed \(0\lt \rho\lt 1\), the matrix indexed by odd vertex sets U and perfect matchings M of K_n, with entries \(|M\cap\delta(U)|-1+\rho\), has real positive semidefinite rank \(2^{\Omega(n)}\) as even n tends to infinity. Here \(\delta(U)\) is the edge cut of U. Consequently, every exact semidefinite lift of the perfect matching polytope has exponential size.

For every n ≥ 1 and \(1\le d\le n\), we prove that a polynomial threshold function of degree at most d on the uniform Boolean cube has average sensitivity at most \(8d\sqrt n\). This proves the asymptotic form of the Gotsman–Linial conjecture. The bound is uniform in both parameters and uses the convention \(\mathop{\mathrm{sgn}}\nolimits (0)=1\).

We give a deterministic algorithm that, for every finite family of explicitly represented ordinary strings, outputs a common superstring of length at most twice the optimum in time polynomial in the total encoded input size, including symbol labels. The guarantee applies to the algorithm constructed here, not the classical maximum-overlap Greedy procedure.

We prove that two-way nondeterministic finite automata cannot be complemented with a polynomial number of states independent of the alphabet. For each n ≥ 4 we construct an n-state automaton over a finite alphabet whose complement requires at least \(\tfrac12 2^{\lfloor(n-4)/127\rfloor}-1\) states.

One-way liveness on h points accepts a word of binary relations when their ordered product is nonempty. For every h ≥ 2, it has a nondeterministic automaton with \(h+3\) states and no left moves, whereas every equivalent s-state two-way deterministic automaton satisfies \(4(s+2)^2\ge2^{\lfloor(h-2)/31\rfloor}\). Partial transition rules, stay moves, and nonaccepting infinite computations are allowed. The alphabets are finite and grow with h, so the result rules out an alphabet-independent polynomial state bound for deterministic two-way simulation, already for one-way nondeterministic sources.

We give a deterministic algorithm that computes the discrete Fourier transform at every length n in \(O(n(\log n)^{1-10^{-13}})\) operations. The model uses exact complex arithmetic, unrestricted coefficients, specified Fourier roots, and unit-cost logarithmic-size indexing; scalar preparation and array organization are included.

We construct exact nonuniform Fourier circuits of size \(o(n\log n)\) along an unbounded sequence of lengths, counting every addition, subtraction, and scalar multiplication. This refutes the \(\Omega(n\log n)\) lower bound in the unrestricted complex linear-circuit model. The construction uses a finite tensor saving: a tensor power of some invertible nonmonomial complex matrix can be computed with fewer matrix calls than the standard tensor-axis algorithm on the same coordinates, when invertible monomial maps are allowed freely between calls.

We prove the simple-undirected form of the Kannan–Tetali–Vempala conjecture: the switch chain on simple undirected graphs mixes in polynomial time for every graphical degree sequence. For a lazy chain that proposes switches uniformly on four vertices, the total-variation mixing time at distance 1/4 is at most \(2n^8\). We also give an exactly uniform sampler for every graphical labeled degree vector. It uses unbiased random bits, terminates almost surely, and has expected polynomial bit running time.

We disprove the quadratic strengthening of the Sensitivity Conjecture by constructing nonconstant total Boolean functions whose block sensitivity grows faster than any constant multiple of sensitivity squared. In fact, for some fixed α > 2, our examples have unbounded block sensitivity and satisfy \(\mathop{\mathrm{bs}}\nolimits (f)\ge s(f)^\alpha\).

For k ≥ 4, we construct two uncolored graphs that are k-dimensional Weisfeiler–Leman equivalent exactly when a prescribed finite-domain choice system has no compatible choice. The system has \(k+1\) domains for joint refinement and k for separate-coordinate refinement. A successful choice is detected after two joint rounds or one separate round. Applied to sparse satisfiability, the reduction gives fixed-dimension \(n^{\Omega(k)}\) time exclusions under positive-rate ETH, even for deciding equality of these early histograms.

We prove that deciding whether Weisfeiler–Leman refinement of an input dimension identifies a given graph is EXPTIME-complete. The input is a nonempty finite simple uncolored graph in adjacency-matrix form and a positive binary-encoded dimension. Identification quantifies over every comparison graph.

For every sufficiently large fixed k, deciding whether two n-vertex graphs are k-Weisfeiler–Leman equivalent requires \(n^{\Omega(k)}\) deterministic sequential time in the worst case. The bound holds at every sufficiently large graph order, even for simple connected uncolored graphs of diameter at most two, without a complexity assumption. Inputs are explicit adjacency matrices; the models are multitape Turing machines and sequential logarithmic-word RAMs with fixed polynomial-bit-time instructions. Both joint and separate replacement conventions are covered.

Deciding joint-update k-dimensional Weisfeiler–Leman equivalence is \(\mathsf{EXPTIME}\)-complete when the two graphs are given by explicit adjacency matrices and k ≥ 2 is encoded in binary. The result holds even for connected simple uncolored graphs of equal positive order and maximum degree at most three.

Every regular language over a finite alphabet has a generalized regular expression of star height at most thirteen over that same alphabet. We prove this uniform bound by representing finite monoid computations as affine updates and recovering them through twelve successive split constructions.

Every regular language over a finite alphabet has generalized star height at most four over that same alphabet. We give a complete construction using an affine correction that hides one interval product, a finite clock, and several scales for moving boundaries through periodic words.

Every regular language over a finite alphabet has generalized star height at most three, with complement taken in the same free monoid. We express finite-monoid computations using a prefix code of word pieces.

Let \(\mathop{\mathrm{IMM}}\nolimits _{n,n}\) be the \((1,1)\) entry of a product of n independent \(n\times n\) matrices of variables. Over every field of characteristic zero, every syntactically homogeneous \(\Sigma\Pi\Sigma\Pi\Sigma\) circuit computing \(\mathop{\mathrm{IMM}}\nolimits _{n,n}\) has at least \(n^{\sqrt n/400}\) gates for all sufficiently large n, with an absolute threshold independent of the field. Bottom linear forms may have arbitrary support, and arbitrary finite fan-in, fan-out, and gate sharing are allowed. Over every field, a block expansion gives such circuits with at most \(n^{\sqrt n+4}\) gates for n ≥ 2. Thus the gate complexity over characteristic-zero fields is \(n^{\Theta(\sqrt n)}\).

We prove the quasilinear-size PCP-for-PPAD conjecture of Babichenko, Papadimitriou, and Rubinstein. There are fixed positive rational constants ε and δ and a deterministic polynomial-time reduction that transforms an End-of-Line instance of binary length N into a generalized circuit of total binary length \(N(\log N)^{O(1)}\). From any rational assignment of polynomial encoding length that ε-satisfies all but a δ fraction of the gates, a solution to the original End-of-Line instance can be recovered in polynomial time, regardless of which gates fail. Such assignments always exist, with one fixed polynomial bound on their encoding length.

We show that a fixed deterministic Turing machine with one writable tape and head can be simulated in \(O(T^{2/5}\mathop{\mathrm{polylog}}\nolimits (T+2))\) work-space bits when a binary time cap T ≥ 2 is supplied. The simulator computes the finite-control and halting outcome by time T; its running time is unrestricted. The result allows a fixed number of read-only input heads and requires a fixed accessor that supplies every initial writable and read-only symbol within distance T of the relevant head origin in polylogarithmic space. This improves the square-root space exponent for one-tape machines, answering Williams's question for this model.

We give a uniform randomized classical algorithm for Subset Sum with bounded error and worst-case running time \(O(2^{0.49n})\) on polynomial-bit inputs in a word-RAM model, where n is the number of input integers. The time bound holds on every random execution.

We give a uniform classical randomized decision algorithm for worst-case Subset Sum. Under every fixed polynomial bound on input-integer bit length, it uses \(\mathop{\mathrm{poly}}\nolimits (n)2^{n/2}\) time and ordinary \(O(2^{n/5})\) writable words of \(O(n+b)\) bits, where b is the largest input bit length. Both resource bounds hold on every execution. The error is one-sided: the algorithm always rejects unsolvable instances and accepts each solvable instance with probability at least 2/3.

For every fixed ε > 0, we give a sampling algorithm using at most \(C_\varepsilon d^\varepsilon\) exact first-order queries on every execution for C² potentials on ℝ^d with a known minimizer and Hessian between I_d and \(2I_d\). The output has total-variation distance at most 1/10 from the target Gibbs law. Computation between queries is unrestricted. We also prove an \(\Omega(\log d)\) query lower bound for arbitrary randomized adaptive algorithms, determining the optimal dimension exponent to be zero.

For every fixed A > 0, a learner that retains at most \(Ad^2\) bits between fresh exact Gaussian linear measurements needs \(\Omega_A(d\log(1/\epsilon))\) measurements to estimate a uniformly random unit vector to angular error at most ϵ, for any \(0\lt \epsilon\le 1/10\), with probability at least 2/3. The constant is absolute for \(o(d^2)\) memory.

For a signal with density bounded by L relative to uniform probability on \(S^{d-1}\), we bound the information in a finite message W formed from exact Gaussian measurements, conditional on an independent projection revealed only to the analyst. For explicit row counts proportional to d, the bound is \(O(H(W)/d+d+\log(2+\log L))\). Consequently, a finite-state learner with \(o(d^2)\) persistent bits and a deterministic sample horizon needs \(\Omega(d\log(1/\epsilon))\) fresh noiseless Gaussian measurements for constant-probability angular accuracy \(0\lt \epsilon\le1/10\) under the uniform spherical prior.

For the image of a uniform cube under a spherical coordinate map, we prove that finite messages from t blocks of \(\Theta(d)\) exact Gaussian measurements reveal only \(O_A(dt)\) information when each message has at most \(\exp(Ad^2)\) values, for fixed A. The same bound holds when each message is supplemented with a nested cell that restores the required geometric spread.

We prove moment estimates for exact random projections of finite measures whose mass is controlled on Euclidean balls, and derive positive domination by countable sums of spherical cap measures. For learners with \(M=o(d^2)\) bits of memory, these estimates give three proofs that uniform-sphere average success at least 2/3 at angular accuracy \(0\lt \epsilon\le1/10\) requires \(\Omega(d\log(1/\epsilon))\) noiseless Gaussian observations. The three proofs keep their different stopping and accuracy costs explicit.

Replacing the Gaussian rows used to select a finite message by independent rows increases the remaining conditional information by at most \(Cd\), for a uniform spherical signal, message entropy at most d², and the specified row dimensions proportional to d. As an application, we prove that learners with \(M=o(d^2)\) persistent bits need \(T=\Omega(d\log(1/\epsilon))\) exact observations to attain uniform-sphere angular success at least 3/5, for \(0\lt \epsilon\le1/10\) and a deterministic finite horizon.

Let a finite-state streaming learner estimate a uniformly random unit vector from independent exact Gaussian linear measurements. We prove that \(o(d^2)\) bits of persistent memory and angular success probability at least 2/3 require at least \(2^{-16}d\log_2(1/\epsilon)\) samples for all sufficiently large d, uniformly for \(0\lt \epsilon\le1/10\). The proof conditions each batch on its observed projection and controls the resulting random residual subsphere.

We prove that the existential theory of the reals lies in the counting hierarchy. More generally, we show that the truth of existential–universal sentences over the reals can be decided in a fixed level of the counting hierarchy, even when the integer polynomials are given by arithmetic circuits.

We give a uniform deterministic polynomial-time algorithm for complete factorization over prime fields. For a prime p in binary and a nonzero polynomial \(f\in\mathbf F_p[x]\) given by its dense coefficient list, the algorithm computes the irreducible factors and their multiplicities using a number of bit operations polynomial in \((\deg f+1)\log p\). The proof uses the uniform Hecke zero-free theorem from the companion paper Primitive roots for every admissible integer base.

We construct a finite translational tile in ℤ³ that admits tilings but no fully periodic tiling. Its unit-cube thickening has the same property in ℝ³, even when arbitrary real translations are allowed. This gives a negative resolution of the periodic tiling conjecture in dimension three.

The compact set of rank-one orthogonal projectors on ℝ⁴, with the Frobenius metric, cannot be covered by ten sets of strictly smaller diameter. It therefore gives a counterexample to Borsuk's conjecture in dimension nine.

We disprove Hadwiger's conjecture by constructing arbitrarily large graphs whose chromatic number exceeds their Hadwiger number. The examples have independence number at most two, and even their ordinary fractional chromatic number exceeds their Hadwiger number. Thus they also disprove the fractional-coloring weakening discussed by Reed and Seymour.

We disprove the Colin de Verdière chromatic conjecture by constructing graphs whose chromatic number exceeds their Colin de Verdière invariant by more than one. The examples have independence number at most two. In fact, their ordinary fractional chromatic number also exceeds their Colin de Verdière invariant by more than one.

We prove that every finite nonempty graph G satisfies \(\chi_{\mathrm{list}}(G)\le C h(G)\) for an absolute integer C, where \(h(G)\) is the largest order of a clique minor. This resolves the Linear List Hadwiger conjecture affirmatively.

We prove that every coloring of the Euclidean plane with five colors has a monochromatic unit-distance pair, with no regularity assumption on the color classes. Consequently, the chromatic number of the plane is either six or seven.

We prove Erdős's conjecture that every set of positive integers with divergent reciprocal sum contains arithmetic progressions of every finite length. More quantitatively, for every fixed k ≥ 3, we show \(\displaystyle r_k(N)\le C_kN\exp\bigl(-c_k(\log N)^{\varepsilon_k}\bigr)\) with \(C_k,c_k,\varepsilon_k\gt 0\), where \(r_k(N)\) is the largest size of a subset of \(\{1,\ldots,N\}\) with no nonconstant k-term arithmetic progression.

We prove that there are absolute constants c > 0 and K₀ such that \(W_r(k)\gt k^{ck\lfloor\log_2 r\rfloor}\) for every \(k\ge K_0\) and r ≥ 2. Consequently \(W_r(k)^{1/k}\to\infty\) for each fixed r ≥ 2, giving a quantitative positive resolution of Erdős's superexponential-growth question, including the two-color case.

We disprove Sidorenko's conjecture with a bipartite graph on 35 vertices and 66 edges: its homomorphism density in some finite simple graph is smaller than the conjectured lower bound. The same connected graph also disproves the forcing conjecture: at one fixed density, asymptotically matching the edge and pattern densities does not imply quasirandomness.

For every sufficiently large prime q, we construct a finite intersecting \((q+1)\)-partite \((q+1)\)-uniform hypergraph with covering number \(q+1\) and exactly \(q+1\) nonisolated vertices in each part. This disproves Ryser's covering conjecture, even for intersecting hypergraphs with equally sized parts.

For every sufficiently large prime \(s\equiv2\pmod3\) and every sufficiently large odd integer n, with the threshold depending on s, we construct an intersecting \((s^n+1)\)-partite \((s^n+1)\)-uniform hypergraph with covering number \(s^n+1\). This disproves Ryser's covering conjecture in its intersecting case.

We prove Hindman's finite sums and products conjecture: for every finite coloring of the positive integers and every positive integer k, there is a k-element set whose nonempty subset sums and nonempty subset products all have the same color.

We prove the Harary–Hill conjecture: for every positive integer n, the ordinary crossing number of the complete graph K_n is \(\displaystyle \frac14\left\lfloor\frac n2\right\rfloor \left\lfloor\frac{n-1}{2}\right\rfloor \left\lfloor\frac{n-2}{2}\right\rfloor \left\lfloor\frac{n-3}{2}\right\rfloor.\)

We prove the Zarankiewicz crossing-number conjecture, resolving Turán's brickyard problem. For all positive integers m, n, the ordinary crossing number of the complete bipartite graph \(K_{m,n}\) is \(\displaystyle \left\lfloor\frac m2\right\rfloor \left\lfloor\frac{m-1}{2}\right\rfloor \left\lfloor\frac n2\right\rfloor \left\lfloor\frac{n-1}{2}\right\rfloor.\)

For every fixed integer d ≥ 3, we prove that every set of n ≥ 2 distinct points in ℝ^d determines at least \(c_d n^{2/d}\) distinct distances, where \(c_d\gt 0\) depends only on d. This resolves the higher-dimensional Erdős distinct-distances conjecture positively.

We prove the weak pinned Erdős distinct-distance conjecture. For every fixed ε > 0, all but \(o(n)\) points of any n-point planar set determine at least \(n^{1-\varepsilon}\) distinct nonzero distances.

We prove a power saving for the planar unit-distance problem: for some absolute \(\beta\lt 4/3\), every set of n points in the Euclidean plane determines \(O(n^\beta)\) unordered pairs at unit distance.

We prove that an isomorphism of Bruhat intervals in arbitrary Coxeter systems preserves their equal-parameter Kazhdan–Lusztig polynomials. This resolves the full combinatorial invariance conjecture positively.

We prove that the chromatic quasisymmetric function of every natural unit interval graph is elementary-positive over \(\mathbb N[q]\). This resolves the elementary-positivity part of the Shareshian–Wachs conjecture.

We determine the sharp logarithmic exponent of the off-diagonal Ramsey number \(r(5,t)\): \(\displaystyle r(5,t)=\frac{t^4}{(\log t)^{3+o(1)}} \qquad (t\longrightarrow\infty).\)

For every fixed integer s ≥ 6, we determine the sharp logarithmic exponent of the off-diagonal Ramsey number: \(\displaystyle r(s,t)=\frac{t^{s-1}}{(\log t)^{s-2+o(1)}} \qquad (t\longrightarrow\infty).\)

We prove that the two-color Ramsey number of the n-dimensional binary cube is at most \(C2^n\), where C is an absolute constant. This resolves positively the hypercube Ramsey conjecture of Burr and Erdős.

We classify finite Euclidean Ramsey configurations by a necessary and sufficient tensor condition over their coordinate fields. The Ramsey property here concerns monochromatic congruent copies at the original scale under arbitrary finite colorings. The criterion shows that every nonempty subtransitive set and every nonempty set of at most five points on a circle is Ramsey. In particular, some Ramsey cyclic quadrilaterals are not subtransitive, disproving the necessity direction of the Leader–Russell–Walters conjectured characterization.

We prove that every nonempty finite oriented graph has a vertex with at least as many vertices at directed distance two as at directed distance one. This resolves Seymour's second neighborhood conjecture positively.

We prove that every finite loopless k-edge-connected multigraph on at least two vertices, with k ≥ 1, has a spanning tree meeting each cut in at most \(C/k\) times the size of the cut, where C is a universal constant. This resolves the strong thin tree conjecture.

We give a deterministic polynomial-time construction of strong thin trees. Given a finite k-edge-connected loopless multigraph on at least one vertex, the algorithm constructs a spanning tree meeting every cut in at most a \(C/k\) fraction of its edges, for a universal constant C. The running time is polynomial in the binary input length, including when parallel-edge multiplicities are encoded in binary.

We prove the graph-decomposition conjecture of Ascoli, He, Park, and Talagrand. Every graph admits a partition into a universally bounded number of fixed edge pieces, each having ordinary containment threshold at most a universal constant times the original graph's integral expectation threshold. The partition is chosen before sampling the random host, and the separate embeddings of the pieces need not agree on shared vertices.

We prove Talagrand's conjecture that integral and fractional expectation thresholds are within a universal constant factor, with the same covering budget.

We prove Talagrand's discrete-convexity conjecture. There is a universal integer k such that, whenever an arbitrary family has Bernoulli product measure at least \(1-1/k\), the sets not contained in a union of k members admit a cover of total cost at most 1/2 at the same density.

We prove the second Kahn–Kalai conjecture. For every finite simple graph H with h ≥ 1 edges and at most n vertices, the threshold for \(G(n,p)\) to contain an ordinary copy of H is at most \(C p_{\mathrm E}(n,H)(1+\log_2 h)\), where C is universal. Here \(p_{\mathrm E}(n,H)\) is the least density at which every subgraph of H has expected copy count at least one half.

For every integer d ≥ 3, we construct arbitrarily large finite d-dimensional simplicial complexes with uniformly bounded vertex degrees and uniform 𝔽₂ coboundary expansion in every degree below d. Together with the known graph and two-dimensional cases, this establishes the existence of bounded-degree 𝔽₂ coboundary expanders in every positive dimension.

For every fixed integer d ≥ 3, we give a deterministic algorithm that constructs a simple nonbipartite d-regular Ramanujan graph on every sufficiently large even number n of vertices. It outputs the full adjacency list in polynomially many bit operations, with an exponent that may depend on d. Every nonconstant adjacency eigenvalue lies strictly between \(-2\sqrt{d-1}\) and \(2\sqrt{d-1}\).

We prove the circulant Hadamard conjecture: a real circulant Hadamard matrix has order 1 or 4. As a consequence, Barker sequences of length greater than one exist exactly at lengths 2, 3, 4, 5, 7, 11, 13, proving the Barker-sequence conjecture.

We prove Barnette's conjecture: every finite simple cubic bipartite planar 3-vertex-connected graph has a Hamiltonian cycle.

We prove that every finite simple undirected graph on n vertices has an edge partition into at most \(Cn\) simple cycles and single edges, for an absolute constant C. This resolves the Erdős–Gallai cycle decomposition conjecture positively.

An integer polynomial is intersective if it has a root modulo every positive integer. For each degree k ≥ 2, we prove that there is an exponent \(c_k\gt 0\) such that every set \(A\subseteq\{1,\ldots,N\}\) whose differences avoid all nonzero values \(h(1),h(2),\ldots\), where h is an intersective polynomial of degree k with positive leading coefficient, satisfies \(|A|=O_h(N^{1-c_k})\). The implied constant may depend on h, but the power-saving exponent depends only on its degree.

Let h be a fixed integer polynomial of degree at least two with positive leading coefficient, having a unit root modulo every positive integer. We prove that any set \(A\subseteq\{1,\ldots,N\}\) whose differences avoid all nonzero values \(h(p)\) at primes satisfies \(|A|\le C_hN^{1-c_h}\), where \(c_h\gt 0\) and \(C_h\ge1\) depend only on h. Thus the local unit-root condition gives a fixed power saving even when polynomial arguments are restricted to primes. The proof uses the companion zero-free half-plane theorem for Dirichlet L-functions to obtain the required prime-distribution estimates.

We prove that there are absolute constants c > 0 and C < ∞ such that every set \(A\subseteq\{1,\ldots,N\}\) with no nonzero square difference satisfies \(|A|\le C N^{1-c}\). This answers the fixed-power question posed by Green and Sawhney.

There are absolute constants ε > 0 and C such that every sufficiently large even n-point set in the plane with no three collinear has at most \(Cn^{4/3-\varepsilon}\) unordered halving pairs. This gives a power saving over the classical \(O(n^{4/3})\) bound for planar halving lines. The proof is nonquantitative and does not supply explicit constants.

For every fixed integer r ≥ 4, we prove that every K_r-free graph of sufficiently large maximum degree Δ has correspondence chromatic number \(O_r(\Delta/\log\Delta)\). This resolves the Alon–Krivelevich–Sudakov coloring conjecture in the stronger correspondence-coloring form. The same bound, with a constant depending on F, holds when any fixed graph F is excluded as an ordinary subgraph. Ordinary and list coloring satisfy the same bounds.

For every fixed integer r ≥ 4, every K_r-free graph on n vertices with average degree d ≥ 2 has an independent set of size at least \(c_r n\log d/d\), where \(c_r\gt 0\) depends only on r. This proves the fixed-clique-size independence conjecture of Ajtai, Erdős, Komlós and Szemerédi.

We construct in ZFC two self-dual partitional matroids on a countably infinite common ground set that admit neither a packing/covering partition nor an intersection witness. This disproves the unrestricted infinite matroid packing/covering and intersection conjectures and answers Joó's question for two partitional matroids negatively. The examples are neither finitary nor cofinitary.

For every fixed integer r ≥ 3, we prove that every relabeling-invariant Boolean property of simple r-uniform hypergraphs on n vertices satisfies \(\mathop{\mathrm{Var}}\nolimits _p(f)\le C_r I_p(f)/(\log n)^{r/(r-1)}\). The constant depends only on r, and the bound holds uniformly for all \(0\lt p\lt 1\) without a monotonicity assumption. For increasing properties, it gives the corresponding threshold-width bound with exponent \(r/(r-1)\), proving the hypergraph threshold-width conjecture of Friedgut and Kalai.

We prove the Friedgut–Kalai sharp-threshold conjecture. For every integer n ≥ 2, every nontrivial increasing family of graphs on n vertices invariant under all vertex permutations, and every \(0\lt \varepsilon\lt 1/2\), the edge probabilities at which its probability equals ε and \(1-\varepsilon\) differ by at most \(C\log(1/(2\varepsilon))/(\log n)^2\), for a universal constant C.

We prove that Maker can achieve the Snaky hexomino within 21 actual Maker moves against arbitrary legal Breaker play on the initially empty infinite square board. The same bound holds on a \(17\times17\) square; in fact, Maker can confine its claims to a fixed 251-cell board.

Starting from the complete graph on n vertices, repeatedly remove the three edges of a uniformly chosen remaining triangle. We prove that the number of edges left at termination, divided by n^3/2, converges in L² to \(1/(2\sqrt2)\). This proves the triangle case of the sharp-constant conjecture of Joos and Kühn. In particular, the same limit holds in probability and for the normalized expectation.

We prove that \(R(C_m,K_n)=(m-1)(n-1)+1\) for every pair of integers \(m\ge n\ge3\) other than \((m,n)=(3,3)\), for which \(R(C_3,K_3)=6\). This establishes the cycle–clique conjecture of Erdős, Faudree, Rousseau and Schelp. The proof combines expansion in a minimal counterexample with a large-clique lemma and an optimization of paths joining clique vertices. These arguments reduce the remaining cases to \(3{,}099\) finite parameter-pattern instances, which are excluded by two exact implementations of proved inference rules. Complete programs and deduction traces accompany the paper.

We construct a fixed \(66\times66\) binary matrix for which ordered matrix removal has no polynomial bound. This disproves the polynomial ordered binary matrix-removal conjecture. Ordered copies preserve the separate row and column orders and match both zeros and ones; removal permits changing entries in either direction.

There are absolute constants \(\eta,c_1\gt 0\) such that, for every sufficiently large integer n, one can choose n points in the unit square so that every triangle they determine has area at least \(c_1n^{-2+\eta}\). Thus the almost n⁻² upper-bound formulation of Heilbronn's triangle problem is false. The exponent η is fixed but extremely small.

We disprove the Gopalan–Servedio square-root conjecture, even up to an arbitrary constant factor. For every real C > 0, there is a nonconstant Boolean function \(f:\{-1,1\}^n\to\{-1,1\}\) on a finite sign cube such that \(\displaystyle \sum_{i=1}^n \widehat f(\{i\})\gt C\sqrt{\deg(f)}.\) Here \(\widehat f(\{i\})\) is the linear Fourier coefficient associated with the ith input, and \(\deg(f)\) is the degree of the real multilinear polynomial representing f.

Assuming the continuum hypothesis, we construct an abstract elementary class with Löwenheim–Skolem number ℵ₀ that is categorical in every sufficiently large cardinal but has at least two nonisomorphic models of cardinality \(\beth_{\omega_2}\). Thus categoricity does not transfer down to the proposed bound \(\beth_{(2^{\aleph_0})^+}\), which equals \(\beth_{\omega_2}\) under CH. Consequently, if ZFC is consistent, the prescribed-threshold form of Shelah's categoricity conjecture is not provable in ZFC.

We prove Shelah's eventual categoricity conjecture for abstract elementary classes in ZFC. For each infinite bound on the Löwenheim–Skolem number there is a uniform threshold such that categoricity in any one cardinal at or above that threshold implies categoricity in every cardinal at or above the same threshold.

We prove that every order automorphism of the full partial order of Turing degrees is the identity, resolving the rigidity conjecture for the Turing degrees positively.

Every recursively enumerable set of natural-number tuples has a polynomial Diophantine representation with exactly one complete auxiliary tuple for each member. This proves the single-fold conjecture and, consequently, the finite-fold conjecture.

We prove that choiceless polynomial time with counting does not capture polynomial time on unordered finite structures, confirming the noncapture conjecture of Blass, Gurevich and Shelah. A linear-consistency query over 𝔽₃ in a fixed binary vocabulary is decidable in polynomial time but not in the full counting formalism.

We prove that witnessed symmetric choice strictly increases the expressive power of choiceless polynomial time with counting. A fixed sentence with one witnessed-choice occurrence defines a Boolean query on every finite input that is not definable in the original counting formalism.

We prove that the Partition Principle does not imply the Axiom of Choice: if ZF is consistent, then so is ZF with the Partition Principle, Choice for ordinal-indexed families, and the negation of the Axiom of Choice. Separately, over every countable transitive model of ZFC, we construct a transitive symmetric model of this theory with the same ordinals and no new countable sequences of ground elements.

We prove that every weakly β-normalizing pure type system is strongly β-normalizing. Both properties quantify over all legal expressions in all valid contexts, and reduction acts inside type annotations. No functionality hypothesis is required. This resolves the β-Barendregt–Geuvers–Klop conjecture.

We give a negative answer to Hilbert's tenth problem over the rational numbers: no algorithm decides whether a polynomial with integer coefficients has a rational zero. The number of variables is part of the input.

We prove a pointwise 2-converse for elliptic curves over \(\mathbf Q\) with nonzero rational two-torsion: if the \(2^\infty\)-Selmer corank is zero or one, then the analytic rank and Mordell–Weil rank equal that corank, and the Shafarevich–Tate group is finite. The result allows arbitrary reduction at 2.

We give an explicit colored-graph characterization of the finite nonempty lattices that occur as full congruence lattices of finite algebras, and prove that deciding this representation property is undecidable. In particular, the finite lattice representation problem has a negative answer. We also prove that recognition of full subgroup intervals in finite groups is undecidable.

We give a negative solution to the finite lattice representation problem. We prove that there is a finite nonempty lattice that is not the full congruence lattice of any finite nonempty algebra of any finite signature.

We realize finite reciprocal affine instruction maps by smooth incompressible shear flows on a flat three-torus. Applied to a reversible one-head recorder with a finite transition table, this gives a complete machine-to-fluid construction: a fixed particle enters a fixed open strip exactly when a given machine halts, with zero initial velocity, zero pressure, and a solenoidal mean-zero force that is periodic after initialization. The construction acts on full closed rectangles and controls every intermediate trajectory. Separate heights resolve overlap between sources and targets, and an endpoint-size estimate controls all excursions independently of the reciprocal scaling factor.

We construct smooth external forces for incompressible Navier–Stokes flow on a fixed flat three-torus at any fixed positive computable viscosity, from zero initial velocity, such that a fixed particle enters a fixed open set exactly when a prescribed Turing machine halts. Every mixed derivative of the force and velocity is bounded and square-integrable in time in spatial supremum norm. The construction uses the machine's ordinary instructions, records their history in a third coordinate, and compensates for finer spatial gates by longer time steps.

At every fixed positive computable viscosity, we construct smooth mean-zero forces on the flat three-torus that become stationary after time one and make a fixed particle, initially in a fluid at rest, enter a fixed open set exactly when a prescribed Turing machine halts. The force has bounded derivatives of every order and a finite effective description. A reversible recording table is realized on whole planar rectangles by Hamiltonian motions, then driven by a mean-zero spatial clock. Separate choices give periodic forcing from time zero or a force whose derivatives are square-integrable in time.

We construct smooth solenoidal mean-zero forces, periodic from time zero, for which a fixed particle on a flat three-torus reaches a fixed open strip exactly when a given machine halts. The initial fluid velocity and the pressure are zero. We also realize positive diagonal maps on coding sheets by incompressible shears, with explicit normal compensation for changes of planar area, and reciprocal maps on whole boxes of positive thickness. Complete local inverses, initialization rules, and intermediate trajectory bounds connect these geometric constructions to finite computations.

Finite prefix instructions may change area and erase information. We give explicit history processors and smooth incompressible motions that retain that information and realize every instruction on its full domain. A first application assigns each machine and finite input a smooth mean-zero force on the flat unit three-torus, at any fixed positive computable viscosity. The solution starts from rest; a fixed particle enters a fixed open strip exactly when the machine halts. The force repeats with period one after an initial loading interval. We then prove alternative realizations using full boxes, normal compensation, invariant planes, and a spatial clock. The constructions specify their initialization, comparison class, derivative bounds, and continuous-time observation. Exact formulas and effective cutoffs provide finite descriptions of the fields and all their derivatives.

At any fixed positive computable viscosity, smooth forces can make a fixed fluid particle detect the halting of an arbitrary machine, starting from rest, while every mixed derivative of the force and velocity decreases faster than every inverse power of time. We give three complete memory constructions: compact moving curls, alternating fractional coordinates, and a periodic lattice on the flat three-torus. Each machine step takes one unit of physical time. The constructions retain earlier records at separated spatial scales and use an exact open detector with a shrinking signal.

We construct smooth forces for three-dimensional incompressible Navier–Stokes flow, from rest at any fixed positive computable viscosity, whose velocity field detects whether a prescribed machine halts. On the unit flat torus, a pointwise test of the third velocity component uses successively shorter stirring intervals in a fixed spatial region. On \(\mathbb R^2\times\mathbb T\), an integral test uses an expanding array of translation regions and a force with globally bounded mixed derivatives. The vertical velocity solves an advection–diffusion equation: short bursts control its pointwise error in the first construction, and a moving cutoff controls the total escaped mass in the second.

We construct smooth forces of fixed compact spatial support for three-dimensional incompressible Navier–Stokes flow from rest whose particle at the origin detects halting by entering a fixed half-space. Every mixed derivative of the force and velocity decays at rate \(O((1+t)^{-1-j})\) for time order j. Three scalar potentials lift a coded rectangle, perform its instruction, and lower its image; an unbounded logarithmic clock supplies the decay. We also realize area-changing prefix instructions on an invariant torus plane, and construct a planar Hamiltonian processor admitting periodic forcing, stationary forcing after startup, and a velocity-field detector through a companion diffusion theorem.

We realize finite positive diagonal affine maps of determinant one by effective smooth incompressible flows on neighborhoods of entire closed rational solid boxes. The source and target families are each disjoint, but may overlap each other. The construction uses localized curls, evacuation to storage and obstacle detours. A balanced three-stack recorder then assigns every machine and finite input a smooth Navier–Stokes force with one compact spatial support, periodic after a loading interval, at any fixed positive computable viscosity. The fluid starts at rest, and one fixed particle enters one fixed open cube exactly when the machine halts. Further constructions give fixed torus charts, periodicity from time zero, alternative history guards and bounded or slab observers. Onto slow clocks yield separate decaying forces. Each construction includes an all-time observation proof, effective derivative bounds and a stated pressure comparison class.

We prove that constant-depth quantum circuits with arbitrary one-qubit and unbounded-arity Toffoli gates cannot compute parity with any fixed positive worst-case advantage using polynomially many qubits. Ancillas start in zero, only one output qubit is measured, and all final garbage is unrestricted. This resolves Moore's parity conjecture in the measured-output model.

We prove that constant-depth quantum circuits with arbitrary one-qubit gates and unbounded-arity Toffoli gates cannot compute parity with any fixed positive worst-case advantage using polynomially many total qubits. Ancillary qubits are initialized to \(|0\rangle\), one output qubit is measured, and all other final registers may be discarded without restriction. This resolves Moore's parity conjecture in the measured-output model.

We construct total Boolean functions with a nearly quartic separation between bounded-error randomized and quantum query complexity. Writing these complexities as \(\mathrm R(f)\) and \(\mathrm Q(f)\), the examples rule out every universal bound \(\mathrm R(f)=O((1+\mathrm Q(f))^\alpha)\) with α < 4. Thus the known quartic upper bound has the optimal exponent, disproving the conjectured cubic bound. Both complexities count worst-case bit queries with error at most 1/3 on every input.

We give a positive answer to the constant-error formulation of the Aaronson–Kuperberg unitary synthesis problem. For every n, a quantum oracle circuit generated in polynomial time from n alone can approximate the channel of every n-qubit unitary to full diamond-norm error at most 1/2, after a suitable Boolean oracle is chosen. Using the fixed gates \(H,T,T^\dagger,\mathrm{CNOT}\), the circuit has polynomially many qubits, elementary gates, and oracle calls, and its oracle queries have polynomial length. The oracle may depend on the target unitary; the theorem does not give an efficient classical procedure for constructing it.

We give a polynomial-time uniform quantum circuit family that outputs the complete prime factorization of every integer N ≥ 2 with probability one. A fixed finite set of bounded-arity gates suffices, and both the gate count and the number of qubits have polynomial worst-case bounds in the input length.

For every finite two-player game with entangled value v < 1, we prove exponential decay for the probability of winning at least a \(v+\delta\) fraction of k independent repetitions, uniformly over all finite-dimensional joint strategies. The result allows arbitrary correlated question distributions and holds for every \(0\lt \delta\lt 1-v\) and k ≥ 1. Its universal rate is proportional to \(\delta^5/(1+\log(|\mathcal A||\mathcal B|))\), where \(\mathcal A,\mathcal B\) are the answer alphabets. For each fixed question distribution, we also obtain an explicit cubic rate in δ.

We prove that approximating the electronic Coulomb spectral infimum in three-dimensional space is QMA-hard when positive integer nuclear charges are encoded in binary. The nuclei have distinct rational positions, the electron number is unary, and the energy is minimized over all antisymmetric continuum states and spin sectors. A deterministic classical polynomial-time reduction produces instances with threshold separation at least one. The nuclear charges may be exponentially large, but every output has polynomial bit length.

We prove that approximating the electronic ground-energy infimum for clamped unit-charge nuclei is QMA-hard on the full spinful fermionic continuum space. A deterministic classical polynomial-time reduction produces polynomially many nuclei at distinct rational positions and polynomially many electrons, with polynomial rational bit lengths and threshold separation at least one. No orbital basis, magnetic field, or additional external potential is supplied, and no binding assumption is imposed.

We prove an entropy area law for the unique ground state of a finite-range Hamiltonian on any finite induced subgraph of the square lattice. A lower bound on the spectral gap of the full Hamiltonian and fixed bounds on the local dimension, interaction range, and interaction strength suffice. For every set of sites, its entanglement entropy is bounded by a constant times the number of edges crossing its boundary, independently of the size and shape of the domain.

We prove that the unique ground state of a uniformly gapped nearest-neighbor Hamiltonian on an \(L\times L\) square lattice admits a projected entangled-pair state approximation with bond dimension polynomial in L and global vector error at most L⁻¹ after normalization. Only the gap of the full Hamiltonian is assumed. The result is an existence theorem, with constants uniform over Hamiltonians of fixed local dimension, interaction strength, and gap.

We prove that the Quantum Approximate Optimization Algorithm (QAOA) approaches the ground-state energy per spin of the Gaussian zero-field Sherrington–Kirkpatrick model when system size tends to infinity first and circuit depth then increases. For every accuracy, some finite depth and deterministic angles, independent of system size and disorder, achieve that accuracy in the limiting expected energy per spin using the standard cost Hamiltonian and transverse-field mixer. This proves the eventual Parisi-optimality conjecture of Basso, Farhi, Marwaha, Villalonga, and Zhou in its fixed-parameter thermodynamic formulation. We give no quantitative bound on the required depth or efficient angle-selection procedure.

We prove that every admissible integrable minimizer of the zero-temperature Parisi functional for the pure, zero-field Sherrington–Kirkpatrick model has full relative Stieltjes support on \([0,1)\). Thus its support has no gaps at any overlap scale below one. We use the covariance normalization \(\xi(t)=t^2/2\).

We prove that every finite connected planar graph with arbitrary positive real edge lengths embeds into real L₁ with a universal distortion bound. This resolves the planar embedding conjecture positively.

For every fixed treewidth bound, the shortest-path metrics of finite connected graphs with arbitrary positive real edge lengths embed into real L₁ with uniformly bounded distortion. This resolves the bounded-treewidth case of the Gupta–Newman–Rabinovich–Sinclair conjecture positively.

We determine the exponential scale of the least ℓ₁ distortion of unit-cost edit distance on all strings of length at most d. For every sufficiently large d, uniformly over finite alphabets of size at least two, the distortion lies between \(\exp(c\sqrt{\log d\,\log\log d})\) and \(\exp(C\sqrt{\log d\,\log\log d})\) for absolute constants \(c,C\gt 0\). The lower bound already holds on binary strings of one common length. Thus the order of logarithmic distortion is sharp up to absolute constants.

We give two finite-circle constructions of binary strings whose least ℓ₁ distortion is \(\exp(\Omega(\sqrt{\log d\,\log\log d}))\), where d bounds their length. Both constructions supply words of one common length for every sufficiently large cap. Two direct binary coding arguments transfer the constructions with absolute distortion and logarithmic block width. We also develop the overlapping-substring method of Ostrovsky and Rabani into a complete finite histogram embedding at the same exponential scale, uniformly over all finite alphabets and all words of length at most d, including the empty word.

We give two independent constructions of binary words of one length at most d whose ordinary edit-distance metrics require ℓ₁ distortion \(\exp(\Omega(\sqrt{\log d\,\log\log d}))\) for every sufficiently large d. We also prove a constant-distortion binary conversion for one prescribed input length. Together with the companion upper embedding theorem, these lower bounds determine the order of logarithmic distortion uniformly over finite alphabets with at least two symbols.

For every fixed \(1\lt p\lt \infty\) and D > 1, every n-point subset of a real L_p space embeds into \(\ell_p^d\) with distortion at most D and subpolynomial dimension \(d=n^{o(1)}\). The target has the same exponent p, and the embedding need not be linear.

We prove that not every hyperbolicity cone is a spectrahedral shadow: some closed hyperbolicity cones admit no finite affine semidefinite lift, even with arbitrary real coefficients and any finite number of auxiliary variables. This disproves the Projected Lax Conjecture and hence the generalized Lax conjecture.

We construct a homogeneous polynomial of degree 16 in 23 real variables whose hyperbolicity cone has no representation by a finite homogeneous real symmetric linear matrix inequality. This disproves the geometric Generalized Lax conjecture.

We construct an exact semidefinite lift of the explicit nonspectrahedral hyperbolicity cone in twenty-three variables defined in the companion paper. The lift is a homogeneous real symmetric pencil of size 100 with 307 auxiliary variables and represents the entire closed cone, including every point with singular X. Thus, although this cone has no semidefinite representation in its original coordinates, it admits one when auxiliary variables are allowed. The stated sizes are not claimed to be minimal.

For every fixed integer k ≥ 3, random k-SAT with independent uniformly signed clauses on distinct variables, sampled with replacement, has a finite positive limiting satisfiability threshold. We credit Gaia Carenini [5] with priority for resolving the satisfiability conjecture. This paper gives an alternative proof, using concentration of a capped last satisfiable index and a comparison between different system sizes.

For random 3-SAT on n Boolean variables, with independent uniformly signed clauses on three distinct variables sampled with replacement, we prove that the first unsatisfiable prefix has variance \(\Theta(n)\). The upper bound removes the logarithmic loss in the earlier variance estimate; the matching lower bound follows from Wilson's transition-width theorem.

Let H_n be the index of the first unsatisfiable prefix in random k-SAT on n variables, with independent uniformly signed clauses using k distinct variables and sampled with replacement. For every fixed k ≥ 4, we prove \(\mathop{\mathrm{Var}}\nolimits (H_n)=\Theta_k(n)\). For k = 3, the variance is bounded below by a positive multiple of n and above by a constant multiple of \(n\log n\); the companion paper on random 3-SAT sharpens this to \(\Theta(n)\). The same upper bounds proved here hold after clipping at any fixed positive multiple of n.

The limiting satisfiability threshold of uniform random 3-SAT is a computable real. We credit Gaia Carenini [4] with priority for resolving the satisfiability conjecture, which establishes the threshold's existence. We prove that one finite deterministic machine can approximate it to any prescribed accuracy. A deletion estimate gives explicit lower certificates, while a finite hierarchical approximation of the soft pressure gives upper certificates at every larger rational density. A fair search through these certificates halts without requiring a computable rate of finite-size convergence.

We establish the exact Kesten–Stigum reconstruction threshold for the ferromagnetic four-state Potts broadcast model on every regular d-ary tree with d ≥ 2 and every Poisson Galton–Watson tree of mean d > 0. Reconstruction occurs exactly when \(d\lambda^2\gt 1\); we prove nonreconstruction at and below the threshold, including equality. In the Poisson model the whole tree is observed and the reconstruction advantage is averaged without conditioning on survival. The proof uses reproducible exact-arithmetic verification of polynomial inequalities.

For the ferromagnetic four-state broadcast model with \(0\lt \lambda\lt 1\), we prove that reconstruction on a bounded-degree deterministic rooted tree occurs exactly when its L³ capacity with edge resistances \(\lambda^{-2|e|}\) is positive. This gives an exact criterion without regularity or growth-rate assumptions on the tree, including at the exponential critical boundary.

We determine the exact reconstruction threshold for the symmetric three-state broadcast process on every regular b-ary tree, b ≥ 2, and every observed Poisson Galton–Watson tree of mean d > 1. Reconstruction occurs exactly when \(d\lambda^2\gt 1\), with d = b in the regular model; there is non-reconstruction at equality for either sign of the channel parameter. The Poisson advantage is averaged over trees and spins without conditioning on survival. This resolves the all-degree three-state regular-tree prediction. Combining the Poisson theorem with known tree-to-graph and algorithmic results gives the exact weak-recovery threshold for the symmetric three-community sparse stochastic block model with independent uniform labels, fixed within- and between-community rates \(a,b\gt 0\), and mean degree \((a+2b)/3\gt 1\): recovery is possible exactly when \((a-b)^2\gt 3(a+2b)\). Above this threshold it is achievable in \(O(n\log n)\) time; at or below it, weak recovery is information-theoretically impossible.

We prove that the Thorp shuffle on \(2^d\) cards mixes in \(\Theta(d)\) complete shuffles. The full permutation law after \(1600d\) shuffles converges to uniform in total variation as \(d\to\infty\), uniformly over the initial deck, while a support count gives a lower bound of \(2d-O(1)\).

For the Thorp shuffle on \(2^d\) cards, we prove that the worst-start total-variation distance after \(32800d\) physical shuffles tends to zero as \(d\to\infty\). Combining our fixed-list estimate with the companion Fourier transfer improves this bound to \(512d\) shuffles. These results follow from bounds on partially observed permutation laws in random coordinate frames.

We show how information about partial permutations controls full permutation laws. Let n tend to infinity through multiples of eight. If the images of a uniformly chosen \(7n/8\) labels approach the uniform injection law in average total variation, and the sign mean tends to zero, then the product of two independent permutations with the given law converges to uniform on S_n.

We bound the information remaining after paths of specified cards in the Thorp shuffle on \(n=2^d\) cards have been observed. After a fixed number of deterministic coordinate sweeps, the joint endpoint law of further cards is close to uniform on the available positions, on average over the observed paths, provided a fixed positive fraction of labels lies outside both lists. Combined with a Fourier transfer, these bounds give full-deck mixing after \(2048d\) physical shuffles.

Fix half the labels in a Thorp shuffle on \(2^d\) positions and reveal their complete trajectories. We prove that, after an explicit absolute number of coordinate sweeps, the conditional permutation of the remaining labels approaches uniform in expected total variation as \(d\to\infty\), uniformly in the initial layout. The resulting constructions give full-deck mixing in a constant multiple of d physical shuffles.

For \(N=2^d\) cards, we prove that an absolute number of coordinate sweeps of the Thorp shuffle brings the full permutation law to total-variation distance tending to zero from uniform. The mixing time therefore has optimal order \(\Theta(\log N)\) in physical shuffles.

We prove that the Thorp shuffle on \(N=2^d\) labeled cards has full-permutation total-variation mixing time \(\Theta(\log N)\) in physical shuffles. An absolute number of coordinate sweeps suffices for the upper bound.

We prove that an absolute number of coordinate sweeps of the Thorp shuffle on \(n=2^d\) positions brings the full permutation to total-variation distance at most \(\frac12n^{-5}\) from uniform, uniformly over the initial deck. Thus \(O(d)\) physical shuffles suffice, which is optimal in order.

We prove that the Thorp shuffle on \(n=2^d\) cards mixes in \(\Theta(d)\) physical shuffles. After a sufficiently large fixed number of coordinate sweeps, the total-variation distance of the full permutation from uniform tends to zero as \(d\to\infty\).

We prove that a fixed number of coordinate sweeps of the Thorp shuffle on \(2^d\) cards makes the squared L² distance of the full permutation density from uniform tend to zero as \(d\to\infty\). In particular, the total-variation mixing time is \(\Theta(d)\) physical shuffles.

For coordinate sweeps with near-uniform line laws and line sizes among powers of two in a suitable fixed interval, we prove a Schatten-moment bound after conditioning on any feasible collection of prescribed card trajectories. An analytic transfer to binary sweeps then shows that a fixed number of sweeps mixes the Thorp shuffle on \(2^d\) cards in \(O(d)\) physical steps, matching the order of the support lower bound.

We prove a permanent inequality with exponent strictly below two for laws on S₄ sufficiently close to uniform and with exactly uniform coordinate marginals. Applied to a four-row recursion, it shows that an absolute number of coordinate sweeps brings the full permutation of the Thorp shuffle on \(N=2^d\) cards to total-variation distance tending to zero from uniform as \(N\to\infty\). Thus the mixing time has the optimal order \(O(\log N)\) in physical shuffles.

For every positive integer n other than 2, 4, and 9, we prove that some irreducible complex representation of S_n has a tensor square containing every irreducible representation. This resolves the tensor square conjecture for symmetric groups affirmatively.

For every staircase partition, we prove that the tensor square of the corresponding irreducible complex representation of the symmetric group contains every irreducible representation of that group. This proves Saxl's conjecture.

We prove the sixth-symmetric-power case of Foulkes' conjecture. For every integer b ≥ 6 and every finite-dimensional complex vector space V, there is a \(\mathop{\mathrm{GL}}\nolimits (V)\)-equivariant injection \(\mathop{\mathrm{Sym}}\nolimits ^6(\mathop{\mathrm{Sym}}\nolimits ^b V)\hookrightarrow\mathop{\mathrm{Sym}}\nolimits ^b(\mathop{\mathrm{Sym}}\nolimits ^6 V)\).

For every finite-dimensional complex vector space V, we prove that the canonical Foulkes–Howe map \(\mathop{\mathrm{Sym}}\nolimits ^b(\mathop{\mathrm{Sym}}\nolimits ^a V)\longrightarrow\mathop{\mathrm{Sym}}\nolimits ^a(\mathop{\mathrm{Sym}}\nolimits ^b V)\) is surjective whenever a ≥ 2 and \(b\ge a(a-1)\). This gives a quadratic stabilization bound independent of \(\dim V\).