Formalizations of theorems from papers submitted to ACM STOC 2027 (the 59th Annual ACM Symposium on Theory of Computing). Paper list: https://sigact-stoc.github.io/stoc2027/ . Missions here state a main result of a STOC 2027 paper in Lean 4 with Mathlib; each mission's title begins with the paper title.
Optimal Online Joint Replenishment with Linear DelaysResearch Paper
The joint replenishment problem (JRP) is a classical model from inventory theory and one of the basic models of online algorithms with delay. A retailer buys several commodities from one supplier in response to customer demand: combining purchases into one shipment saves delivery cost, but waiting to combine them delays customers. The same trade-off appears…
Solving One of Many Instances Is Almost as Hard as Solving OneResearch Paper
A direct-sum theorem says that solving many independent instances of a communication problem costs proportionally more than solving one (Feder, Kushilevitz, Naor, Nisan 1995; Karchmer, Raz, Wigderson 1995). A strong direct-sum theorem would imply something weaker and still informative: solving one of k instances is almost as hard as solving a single…
Streaming Graph Colouring Meets Molloy–Reed via KernelizationResearch Paper
Brooks' theorem says that a connected graph of maximum degree Δ other than a clique or an odd cycle has a proper Δ-colouring, and Molloy and Reed showed that, for large Δ and k below a threshold of order Δ, the failure of (Δ−k)-colourability is witnessed by a small subgraph. In the streaming model the edges of the graph arrive…
Trading Time, Space, and Alternations: General Plasticity for Algorithms from Hardness of Range AvoidanceResearch Paper
Whether polynomial time can be simulated in small space is one of the central questions of complexity theory. A simulation of P in space nγ for every γ>0 would imply P=PSPACE by the space hierarchy theorem. Williams gave an unconditional simulation of time T in space about T (Wil25), and asking for much less…
A randomized algorithm that runs in time T and uses T random bits usually errs on some fraction of its random strings. Derandomization asks for a deterministic algorithm with the same answers, and fine-grained derandomization asks that the deterministic algorithm be almost as fast, in time T1+O(ϵ) rather than poly(T). Without a generic…
Brooks' theorem (Brooks 1941) says that a connected graph of maximum degree Δ can be properly colored with Δ colors unless it is a clique KΔ+1 or an odd cycle. For Δ≥3 the only obstruction is KΔ+1, and the theorem is tight: Δ colors is one fewer than the greedy bound Δ+1.
Resolving the Worst-Case Complexity of Linear Secret SharingResearch Paper
A secret-sharing scheme lets a dealer split a secret among n parties so that every authorized coalition can recover it, while every other coalition learns nothing about it. Since Shamir and Blakley introduced threshold schemes in 1979, and Ito, Saito and Nishizeki showed in 1987 that every monotone family of coalitions can be realized, the central…
Efficient Stable Word-RAM Simulation by Population ProtocolsResearch Paper
Population protocols model computation by many identical, anonymous agents with small memory that interact in randomly chosen pairs: chemical reaction networks, sensor swarms, molecular programming AAD+06. Inputs and outputs are unary counts of agents in designated states. With a constant number of states, the predicates that can be computed stably (correctl…
Certifying Capacity and Gaps of the Rank-Dependent Gain-Sharing Framework for RankingResearch Paper
In online bipartite matching, offline vertices are known in advance and online vertices arrive one at a time, each to be matched irrevocably. The algorithm RANKING of Karp, Vazirani and Vazirani (1990) draws independent uniform ranks and matches each arrival to its unmatched neighbour of minimum rank. Devanur, Jain and Kleinberg (2013) gave the standard…
Fully Dynamic Connectivity in O(log3n) Worst-Case Update TimeResearch Paper
In fully dynamic connectivity, a graph on a fixed set of n vertices changes by edge insertions and deletions, and queries ask whether two given vertices are connected. A spanning forest answers every query, and the difficulty is deletion: removing a forest edge splits a tree, and a replacement edge must be found without searching the whole graph. Worst-case…
Average-Case Hardness of PH from ETH-Type HypothesesResearch Paper
Average-case complexity asks whether problems are hard on the inputs that an efficient process actually generates, rather than on the worst input. It is the setting that cryptography needs, and Impagliazzo's survey Imp95 named the world in which NP is hard in the worst case and easy on average "Heuristica". A central question is what worst-case assumptions…
Good Quantum Locally Testable Codes from Lossless Cubical ComplexesResearch Paper
A quantum locally testable code (qLTC) is a quantum code whose stabilizer checks detect errors in proportion to their distance from the code: a word far from the code violates a constant fraction of the checks, each of which touches only a constant number of qubits. Aharonov and Eldar put the notion in its current form (arXiv:1310.5664), motivated by its…
Exponential Lower Bounds for Products of Cubic Polynomials over Prime FieldsResearch Paper
How complicated must a modular predicate be when it is written as a product of low-degree polynomials over a prime field? The question comes from circuit complexity. The polynomial method of Razborov and Smolensky gives strong lower bounds for bounded-depth circuits when the algebra and the gate modulus are compatible (Razborov 1987, Smolensky 1987).…
A Quadratic Bogolyubov Theorem and Quantum Worst-Case to Average-Case ReductionsResearch Paper
Bogolyubov's lemma says that if a set A⊆F2n has density α, then the sumset A+A+A+A contains a linear subspace of codimension bounded in terms of α. It is a basic tool of additive combinatorics, and it underlies additive-combinatorial worst-case to average-case reductions for linear maps: a point of the subspace is a sum of points…
Resolution Lower Bounds versus the Weak Pigeonhole PrincipleResearch Paper
Automatability asks whether a proof system can find proofs in time polynomial in the size of the shortest one. Atserias and Müller showed that Resolution is not automatable unless P = NP (JACM 2020). Their argument rests on the CNF formulas Refs(φ), which say that φ has a Resolution refutation with few clauses: for unsatisfiable φ…
Subquadratic Time Matrix Multiplication Data Structures Beyond the Dual Exponent, with ApplicationsResearch Paper
The matrix multiplication data structure problem asks to preprocess an N×D matrix A and a D×N matrix B so that any entry of AB can be returned quickly. Computing the product outright takes about N2 time at best, and reading one entry from scratch takes 2D reads of the input. A solution is nontrivial if its preprocessing takes …
Replicable Decisions in Finite Experiments: A Chain Converse and Its LimitsResearch Paper
A statistical procedure is replicable when two runs on independent data, with the same internal randomness, return the same answer with high probability. The notion was introduced for learning algorithms by Impagliazzo, Lei, Pitassi and Sorrell, and it asks more of a procedure than accuracy does: at a model where both answers are acceptable, an accurate…
Given vectors a1,…,an∈Rm, vector balancing asks for signs εj∈{−1,1} that make the signed sum ∑jεjaj small. Writing A=[a1⋯an], the ℓ∞ discrepancy is
Second-Best Bilateral Trade is 1/2 EfficientResearch Paper
In bilateral trade a seller owns one indivisible good and a buyer may acquire it. Each holds a private, nonnegative value, s and b, drawn independently from publicly known priors FS and FB. Trading creates the surplus b−s, and the first-best gains from tradeFB=E[(b−s)+] are obtained by trading exactly when b>s. The Myerson–Satterthwaite…
Copyless Cost Register Automata and Algebraic Groups: An Exact Characterization for Invertible Weighted AutomataResearch Paper
A finite automaton reads its input once, left to right, with constant memory. Adding finitely many registers that hold rational numbers and are updated at each step by expressions in their old values gives the cost register automata (CRA) of Alur, D'Antoni, Deshmukh, Raghothaman and Yuan (ADD+13). With linear updates over a field, CRA are exactly weighted…
A (3+ϵ)-Approximation for Fair k-Means and a Matching Lower BoundResearch Paper
The k-means problem asks for at most k centers in Rd minimizing the sum of squared distances from n input points to their nearest centers. When the points are people, the composition of a cluster can matter as much as its cost: a clustering used for loan approval or school assignment may concentrate a protected group in one cluster. The group-balanc…
Rational and Gaussian long integer multiplicationResearch Paper
Toom–Cook-k multiplication splits each of two long integers into k pieces, reads the pieces as the coefficients of two polynomials of degree k−1, evaluates both polynomials at 2k−1 points, multiplies the values pointwise, and recovers the 2k−1 coefficients of the product polynomial by interpolation. The scheme underlies the mid-range multiplication routines…
Quantum Copy Complexity of Testing Monotonicity and Other PropertiesResearch Paper
Property testing asks whether a small amount of information about an unknown object suffices to decide if it has a property or is far from having it. Monotonicity of Boolean functions on the hypercube is the standard test case of the field, studied with classical samples, classical queries and quantum queries (Goldreich et al. 2000; Khot–Minzer–Safra 2018; B…
The Power of Test-Time Training for Approximate SamplingResearch Paper
A language model generates a sequence one token at a time, and a common way to improve it at inference time is to steer generation with a learned value function that scores partial sequences. Golowich, Moitra and Rohatgi model this as sampling: an unknown target distribution μ⋆ on strings of length n is accessible only through an oracle μ^ that…
The Exact Welfare Guarantee of Fixed-Price Bilateral TradeResearch Paper
A seller owns one item and a buyer may want it; their values are private and independent. Myerson and Satterthwaite showed that no mechanism is at once efficient, incentive compatible, individually rational and budget balanced (MS83). The simplest mechanism that keeps every property but efficiency is a fixed price: post one price, and trade happens if both…