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.
Monotone circuit lower bounds were first proved by Razborov's approximation method (Razborov 1985): every gate of a small circuit is replaced by an approximating gate, and one shows that every approximator is far from the target function. Razborov also showed that the method, in a natural general form, cannot prove more than linear lower bounds for…
Counting Square Tilings with a Fixed Set of Polyominoes Is #EXP-CompleteResearch Paper
Exact counting asks for the number of solutions rather than whether a solution exists. A tiling problem makes this distinction concrete: a region can admit tilings whose number is difficult to compute even when tileability has an efficient criterion. Restricting the pieces to one fixed family and the region to an ordinary square leaves only one varying…
Random-Order Online Facility Location Beyond Uniform Opening CostsResearch Paper
A facility-location decision trades a one-time setup cost against repeated travel or service costs. In the online facility-location problem, demand points arrive one at a time, and an arriving point must immediately receive service from a facility that has already opened. An expensive facility may be worthwhile for many nearby requests, but those future…
Deterministic Spectral Sparsification in Almost-Linear Time for Dense GraphsResearch Paper
A spectral sparsifier of a weighted graph G is a reweighted subgraph H with few edges whose Laplacian quadratic form approximates that of G for every vector. It preserves every cut approximately and also the linear-algebraic structure used by electrical flows, random walks and Laplacian solvers, so an algorithm whose cost grows with the number of edges can…
The Limits of Posted Prices in Random-Order Combinatorial AuctionsResearch Paper
In a combinatorial auction a seller allocates m items M=[m] among n bidders, bidder i holding a private valuation vi:2M→R+, and wants an allocation (S1,…,Sn) of pairwise disjoint bundles with large welfare∑ivi(Si). Truthful mechanisms that need little communication are a central topic at the boundary of economics and computing.…
Sublinear Approximations for Spanning Tree CongestionResearch Paper
A spanning tree connects every vertex of a graph while retaining no cycle. Trees provide a routing structure in which every pair of vertices has exactly one simple path. This removes routing choices, but can concentrate many demands on a few tree edges. Spanning tree congestion measures that concentration when the original graph's edges are the demands.…
Shortest Disjoint Paths in Planar GraphsResearch Paper
This mission contains the full arbitrary-position search goal, all seventeen
numbered milestones, thirteen local definition items and a published
planarity reference. The theorem proofs are open Lean declarations.
Polylogarithmic Approximation for Packing Convex PolyhedraResearch Paper
Three-dimensional packing occurs when a collection of parts must share a container and its
volume determines a cost. In additive manufacturing, the orientation of a part can be chosen
before its position because orientation affects surface quality, support requirements, and
production time. A mathematical version therefore keeps each shape's orientation…
Efficient Quantum State Identity TestingResearch Paper
Given n unknown pure quantum states, the quantum state identity problem asks whether they are all the same. The Permutation Test decides this with one copy of each state under the exact promise that every pair is identical or orthogonal (Kada, Nishimura and Yamakami; Buhrman et al.). In practice states are only approximately identical or approximately…
The sum-of-squares complexity of linear-algebraic principlesResearch Paper
A real matrix of rank greater than r cannot be a product of an n×r matrix and an r×n matrix. This elementary obstruction becomes a different question when the permitted certificate is a polynomial identity of bounded degree. Researchers studying algebraic proof complexity ask how much degree a specified certificate system needs to express such…
Algorithms for Sparse LWE and LPN with Small SecretsResearch Paper
Learning with errors (LWE) asks to tell noisy linear equations b=As+emodq apart from uniformly random right-hand sides; its hardness underlies most lattice-based cryptography (Regev 2005). Sparse LWE, where every row of A has only k nonzero entries, was introduced by Jain, Lin and Saha (2024) as a source of efficient primitives, and the modulus-q ana…
Adversarially Robust Streaming Algorithms for (k,z)-ClusteringResearch Paper
k-Median and k-Means are among the most studied clustering problems. Both are cases of (k,z)-clustering in Rd: given a dataset P, find at most k centers that minimise the sum of the z-th powers of the Euclidean distances from the points to their nearest center. In the dynamic geometric stream model of Indyk (2004), the data arrive as insertions and…
Catalan Hashing: Efficient Linear Probing for Variable-Length ItemsResearch Paper
Linear probing stores each key in the first free cell at or after its hash position, so a query is a single forward scan over a contiguous region of memory. That locality is why linear probing is the default hash table in practice and in external memory, and its analysis goes back to Knuth's 1963 note and its many refinements (Knuth, The Art of Computer…
The Higher-Order Identifiability Paradox: Learning and Certifying Hypergraph OrderResearch Paper
Predictors built on coarse views of a hypergraph — features that keep only interactions up to some order and discard the rest — are cheaper and more stable than full-order models, but discarding the higher-order part is safe only when that part carries little signal. Zhang, Yan, Qiao and Yu (The Higher-Order Identifiability Paradox: Learning and Certifying…
Rapid mixing of quantum spin chains at any finite temperatureResearch Paper
Thermal (Gibbs) states describe quantum systems in equilibrium, and preparing them on a quantum computer is a basic task for quantum simulation. A common route is a quantum Gibbs sampler: a Lindbladian whose dynamics converges to the Gibbs state σβ=e−βH/tre−βH from any initial state, the quantum analogue of a Markov…
A Numerical Refinement of an Exact Discrete Fourier Transform BoundResearch Paper
The discrete Fourier transform of length n maps x∈Cn to (DFTnx)j=∑k=0n−1ζnjkxk, ζn=exp(2πi/n). The Cooley–Tukey factorization computes it with O(nlogn) arithmetic operations, and Bluestein's chirp reduction extends that order of growth to every length (Cooley–Tukey 1965; Bluestein 1970). Later work…
Gain-Sharing Optimization in Randomized Primal–Dual Analysis: Structure and CertificationResearch Paper
Randomized primal–dual analysis is the standard way to prove competitive ratios for online matching and allocation: the algorithm's gain is split between dual variables, and a uniform expected dual-feasibility factor γ certifies a γ-competitive guarantee by weak duality (Devanur, Jain, Kleinberg 2013). The split is governed by a gain-sharing…
The Sample Complexity of Multi-Class OmnipredictionResearch Paper
A predictor of class probabilities is often used by many downstream decision makers, each with its own loss. Omniprediction (Gopalan, Kalai, Reingold, Sharan, Wieder, 2022, arXiv:2109.05389) asks for one predictor whose best-response post-processing competes, for every loss in a class simultaneously, with every rule in a benchmark class. For binary labels…
Tensor Decomposition Beyond the Spectral ThresholdResearch Paper
Tensor decomposition asks, given all entries of an order-k tensor T=∑i=1mvi⊗k, to recover the rank-one components vi up to the symmetries of the problem. It underlies algorithms for dictionary learning, topic models and mixtures of spherical Gaussians. For general tensors it is intractable: computing the rank of a third-order tensor is…
Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local UniformityResearch Paper
Counting the proper k-colorings of a graph approximately, and sampling one nearly uniformly, are equivalent problems, and both are classical test cases for Markov chain Monte Carlo. The simplest sampler is the Glauber dynamics, which recolors one vertex at a time. Jerrum (Jer95) showed that it mixes in O(nlogn) steps whenever k>2Δ, where Δ is…
One Trap Is Enough: The Structure and Complexity of Robust Contracts for Sequential SearchResearch Paper
In research and development, procurement and delegated experimentation, an agent tries costly options with random outcomes one at a time, keeps the best outcome found, and decides when to stop; the principal sees only the outcome that is finally submitted and pays a wage that depends on it. Without an incentive problem this is Pandora's box problem (Weitzman…
Space-Optimal Algorithms for Spanning Forests in Dynamic Streams at Every Confidence Level: With and Without Deletion ConstraintsResearch Paper
Connected components underlie single-linkage clustering, record linkage and many graph analyses. When a graph is too large to store and its edges arrive as insertions and deletions, one asks for a compact summary from which a spanning forest can be recovered: one tree spanning each connected component, built from edges currently present. A forest on v vertic…
An Information Hierarchy of Privacy Filters and OdometersResearch Paper
Differential privacy is usually analysed for a fixed sequence of releases, but in practice an analyst queries a database adaptively, choosing each request after seeing earlier answers, and the privacy cost of the next answer may itself depend on what has been released. Two kinds of procedures control the cumulative privacy loss of such an interaction: privac…
Order-selection Prophet Inequality (Almost) Goes I.I.D.Research Paper
In the prophet inequality a gambler sees independent nonnegative values V1,…,Vn with known distributions one at a time and may accept at most one, irrevocably, when it is revealed; the benchmark is the prophet's E[maxiVi]. In an adversarial order the best ratio is 1/2 (Krengel–Sucheston 1977; Samuel-Cahn 1984). In the order-selection varian…