Theoretical computer science

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 minimum Vertex Cover is NP-hard to approximate within every fixed factor below two, even on simple unweighted graphs.

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

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

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 \(\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 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 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 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.

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

— secondary writeup 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 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 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 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 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 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 (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 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, 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 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 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 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 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.

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\).

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\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.

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 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.

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 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 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\).

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.

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.

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 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.

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.

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 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.

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.

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.

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.

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.

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 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 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 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.