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.
Breaking the Exponential Barrier: The First Polynomial-Time Algorithm for the Győri-Lovász TheoremResearch Paper
Partitioning a graph into connected pieces of prescribed sizes, each containing a designated root, is a basic primitive in network design, districting and load balancing, and in the analysis of confluent flows. The Győri–Lovász theorem says when this is always possible. Győri proved it for undirected k-connected graphs (Győri 1976), and Lovász gave a…
Monadically Dependent Graph Classes Have Almost Bounded Merge-WidthResearch Paper
First-order model checking asks, given a graph G and a first-order sentence φ, whether φ holds in G. A central conjecture states that this problem is fixed-parameter tractable on every monadically dependent graph class: a class that cannot encode all graphs through a fixed formula over vertex-colored members. Planar graphs, classes of bounded…
Smoothed Analysis for Distributed MISResearch Paper
A maximal independent set (MIS) is a basic symmetry-breaking object in distributed computing. Luby's algorithm (Luby 1986) finds one in O(logn) rounds, and for decades no substantially faster algorithm for general graphs was known. Khoury and Schild (arXiv:2610.18215) showed that Ω(logn/loglogn) rounds are necessary on some graphs in the LOCAL…
The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is TightResearch Paper
Quantum algorithms for linear algebra access a dense matrix A through quantum random access memory and prepare a state proportional to the solution of a linear system (Harrow, Hassidim, Lloyd 2009; Kerenidis, Prakash 2017; Gilyén, Su, Low, Wiebe 2019). Their cost depends on the normalized Frobenius normρ=∥A∥F/∥A∥ and the condition number …
Fitting Ultrametrics under any ℓp ObjectiveResearch Paper
An ultrametric is a distance in which, in every triangle, the two largest sides are equal. Equivalently, it is the leaf-to-leaf distance of a rooted tree whose leaves are all at the same depth, so an ultrametric is the same data as a hierarchical clustering. Fitting one to noisy pairwise measurements is a basic problem of numerical taxonomy: Cavalli-Sforza…
Marton's conjecture in polynomial timeResearch Paper
A finite set A⊆F2n has doubling constantK when ∣A+A∣≤K∣A∣. Marton's conjecture, also called the polynomial Freiman–Ruzsa (PFR) conjecture, asserts that such a set is essentially a subspace up to polynomial losses: there is a subspace V with ∣V∣≤∣A∣ such that A is covered by KO(1) translates of V. It was proved by Gowers, Green,…
Cube-Root Soundness Is Optimal for the Line–versus–Point TestResearch Paper
The Reed–Muller codeRMq(m,d) consists of the evaluation tables of polynomials Q∈Fq[X1,…,Xm] of total degree at most d. Restricted to an affine line, such a polynomial becomes a univariate polynomial of degree at most d. The line–versus–point test checks exactly this local property. It is a two-query consistency test: given a…
Weighted and Unweighted Online Connectivity Augmentation via Geometric Hitting SetResearch Paper
In the weighted connectivity augmentation problem (WCAP) one is given a k-edge-connected graph G=(V,E) and a set of candidate linksL⊆(2V) with nonnegative costs, and buys a cheapest set of links whose addition makes the graph (k+1)-edge-connected. Its special cases, tree augmentation and cactus augmentation, are central problems of network…
The spectrum of a quantum state (the eigenvalues of its density matrix) is the part of the state that does not depend on a choice of basis. Purity, von Neumann entropy and all Rényi entropies are functions of it, and in many-body physics and quantum chemistry the spectra of reduced density matrices are used to quantify entanglement and electron correlation.…
Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and TreewidthResearch Paper
Many inference problems on random structures show a gap between what is statistically possible and what known polynomial-time algorithms achieve. The low-degree method is the most widely used heuristic for predicting such gaps: it compares a planted law P with a null law Q only through polynomials of bounded degree in the observed coordinates, and treats a…
Sparse Discrepancy Beyond Additive Functions: Acyclic, Bounded-Degree and Degenerate Sparsity PatternsResearch Paper
In combinatorial discrepancy one colours the elements of a ground set red and blue so that every set of a given system is split as evenly as possible. The Beck–Fiala theorem (Beck–Fiala 1981) bounds the discrepancy of a system in which every element lies in at most t sets by 2t−1, independently of the number of sets and elements. Its proof, like Spencer's …
Dimension-Independent Anti-Concentration Certificates for Log-Concave DistributionsResearch Paper
A random vector X∈Rd is anti-concentrated if no hyperplane slab captures much of its mass: for every unit vector v, P[∣⟨X,v⟩∣≤δ]≤O(δ). Anti-concentration is the hypothesis that makes robust and list-decodable regression, clustering of mixtures and related estimation problems possible in high dimension.…
The Karp–Lipton theorem says that if every NP problem has polynomial-size circuits, the polynomial hierarchy collapses. Karp and Lipton proved the collapse to Σ2P (KL80); every later improvement replaced Σ2P by a smaller class C with
Counting Paths in Time O∗(2k), with Extensions to Counting Bounded Treewidth Graphs and Multilinear MonomialsResearch Paper
Deciding whether a directed graph contains a path on k vertices (k-Path) is a central problem of parameterized complexity. Williams' algebraic method gives a randomized 2knO(1) algorithm for the decision problem (2009), and base 2 remains the best known exponential dependence on k. Counting the paths approximately has been harder. Koutis and Williams…
Canonical Graph Decompositions via Local SeparationsResearch Paper
Tree-decompositions describe the global, tree-like connectivity of a graph: the Robertson–Seymour tree-of-tangles theorem gives, for every graph, a canonical tree-decomposition that efficiently distinguishes all its tangles. Many graphs, though, are tree-like only locally: road networks, Cayley graphs of finite groups, locally chordal graphs. Their…
Pseudorandom Functions in NC¹ from LWE/LPN/CDH (Or: How to Build Low-Depth PRFs, Generically)Research Paper
A pseudorandom function (PRF) is a keyed family {Fk} that no small circuit with oracle access can distinguish from a truly random function, even when the circuit chooses its queries adaptively. PRFs are the basic object of symmetric cryptography: encryption, message authentication and many protocols are built from them. Their circuit depth, the parallel…
Dynamic Edge Orientation on Low-Arboricity Graphs: Breaking the log n BarrierResearch Paper
Many dynamic graph algorithms (maximal and approximate matching, colouring, densest subgraph, spanners, adjacency queries) run on graphs that stay sparse while edges are inserted and deleted. Their common subroutine is dynamic edge orientation: keep every edge directed so that each vertex has few out-edges, and redirect ("flip") as few edges as possible…
Efficient thermalization of one-dimensional noncommuting Hamiltonians via system-bath interactions with Θ(n) ancilla qubitsResearch Paper
Preparing the Gibbs stateρβ=e−βH/Tre−βH of a many-body Hamiltonian is a basic task of quantum simulation: it is the input to thermal expectation values, to quantum algorithms for optimization and sampling, and to studies of quantum phases at finite temperature. One family of algorithms mimics physical thermalization.…
Quasipolynomial Trace ReconstructionResearch Paper
A deletion channel with retention probabilityp takes a binary string x∈{0,1}n, keeps each bit independently with probability p, and outputs the kept bits in order; the output is a trace. The trace reconstruction problem asks how many independent traces are needed to recover an unknown x with probability at least 2/3. It is a basic question about…
Effective Horizons for Prophet Inequalities with Discounted I.I.D. RewardsResearch Paper
A prophet inequality compares a gambler, who sees rewards one at a time and must accept or reject each irrevocably, with a prophet who knows all rewards in advance. For n i.i.d. rewards, a threshold rule with per-stage acceptance probability about 1/n guarantees a fraction 1−1/e of the prophet's expected reward, and for independent non-identical rewards the…
Many sequential decision systems already run a recommendation algorithm: a pricing heuristic, a statistical model trained on private data, a Q-learning agent. A downstream learner who receives its advice in each round may want two things at once. First, the learner should never regret having followed the advice blindly: whatever consistent re-mapping of the…
Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal ApproximationResearch Paper
When every player of a game has regret o(T), the empirical distribution of play converges to the set of coarse correlated equilibria, at a rate governed by the largest average regret. This link is why the dependence of regret on the horizon T has been studied closely. Against an adversary the rate Tlogn cannot be improved, but a player in a game…
Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex CaseResearch Paper
Gradient descent (GD) with a predetermined stepsize scheduleH=(h1,…,hn)∈[0,∞)n runs xt=xt−1−ht∇F(xt−1) with stepsizes fixed before the optimization starts. It is the simplest first-order method, and the question of how fast it can be made to converge by choosing H well, without momentum, line search or adaptivity, has been…
Pareto-optimal Non-Clairvoyant Scheduling with PredictionsResearch Paper
Non-clairvoyant scheduling asks how to run n jobs on one machine, preemptively, so as to minimize the sum of their completion times, when the size of a job is learned only when it completes. If the sizes were known, running the jobs in increasing order of size (Shortest Processing Time first, Smith's rule) would be optimal. Without them, Round-Robin, which…
Matrix Lewis Weights: Solving Semidefinite Programs in Square Root Constraints IterationsResearch Paper
A semidefinite program with m variables and an n×n matrix constraint asks to minimize c⊤x subject to ∑i=1mxiAi−C⪰0. Interior point methods follow the central path of a self-concordant barrierf for the feasible region; the classical analysis of Nesterov and Nemirovskii (1994) takes O(Kνlog(1/ε)) iterations…