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.
A Unified and Simplified Framework for Dynamic Distance-Based Graph ProblemsResearch Paper
Distance problems on graphs that change over time sit behind many algorithms for flows, cuts and routing. A data structure that answers approximate distance queries while edges are deleted can replace repeated shortest-path computations inside iterative methods. Deterministic structures are of special interest, since they withstand an adaptive adversary by…
A Near-Optimal Space Lower Bound for Euclidean Diameter Estimation in Dynamic StreamsResearch Paper
A massive set of points in high-dimensional Euclidean space arrives as a sequence of insertions and deletions, and a small-memory algorithm must estimate how far apart the two farthest surviving points are. This is one of the basic questions of geometric streaming, a model introduced by Indyk (STOC 2004), in which the data is a dynamic multiset rather than…
Path Decompositions of Sparse Graphs via Gaussian Sweeps and Faster Exponential AlgorithmsResearch Paper
How large can the pathwidth of a sparse graph be? For graphs of maximum degree 3 the question matters in two places. Structurally, pathwidth, bisection width and cutwidth of such graphs are tied together by classical relations, so an upper bound on one transfers to the others. Algorithmically, many exact exponential algorithms for sparse instances run a…
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…