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.
Computing Weighted Set Covers with Heterogeneous Stochastic Oracles: Deadline-Constrained Token ComplexityResearch Paper
A weighted set cover instance consists of a finite universe of elements, a family of subsets whose union contains the universe, and a positive weight for each subset. A cover is a subfamily containing every element; its weight is the sum of its subset weights. A service that proposes a cover can be useful even when its answer is uncertain: the proposed…
Anchoring the Security of Invariant Quantum MoneyResearch Paper
A public verifier lets anyone check a quantum banknote, while its security asks whether an efficient algorithm can turn one issued banknote into two accepted registers. For invariant quantum money, the banknote is a superposition of combinatorial objects sharing a public invariant. A classical description of one object therefore supplies useful information…
A quantum random access memory (QRAM) lets a quantum algorithm query classical data while its address is in superposition. Algorithms that assume such access need an implementation whose cost includes loading and retrieving the data. A device containing many components can still have a small cost per query: conventional memory changes only a small fraction…
Optimal Sparsification of Gaussian ProcessesResearch Paper
A Gaussian process is a family of random variables whose finite subfamilies are jointly Gaussian. Its supremum describes the largest fluctuation across a collection of correlated measurements. In finite-dimensional geometry, the same construction gives support functions of convex sets and many norm representations. Knowing the expectation of such a supremum…
Limits of Finite-Sample Dependence Measures under Data Processing InequalityResearch Paper
A dependence measure assigns a number F(U) to the joint distribution U of two finite-valued random variables X and Y. Two requirements are natural. The measure should vanish when X and Y are independent, and it should obey the data processing inequality (DPI): passing X through a noisy channel cannot increase its dependence on Y. Shannon mutual information…
Coordinating Boundaries: Improved Approximation Algorithms for Unweighted Non-Preemptive Throughput MaximizationResearch Paper
Nonpreemptive throughput maximization is a basic real-time scheduling problem: a set of jobs, each available only during a time window, must be placed on identical machines so that as many jobs as possible finish by their deadlines. It models admission control in real-time systems and allocation of communication resources (Bar-Noy, Guha, Naor and Schieber,…
Spatial Communication Complexity of Agnostic Halfspace LearningResearch Paper
Moving data costs energy, and in a circuit the cost grows with the distance a bit travels. Grover's bit-meter measure charges every transmitted bit by the length of the wire it crosses (Grover 2015); with it, Blake and Kschischang proved that decoding positive-rate codes over a binary erasure channel with exponentially small block error probability needs …
Hardness Amplification of Approximate Nash Equilibrium with Constantly Many PlayersResearch Paper
Computing a Nash equilibrium asks for a probability distribution over each player's actions such that no player benefits from changing its own distribution. An approximate equilibrium permits a specified additive improvement. The approximation parameter matters: when payoffs lie between zero and one, allowing improvement one makes every profile acceptable.…
Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint AssignmentResearch Paper
Local search is the oldest heuristic for the Traveling Salesman Problem (TSP): start from a tour and keep replacing it by a better neighboring tour until no neighbor is better. For the 2-opt neighborhood, studied by Croes in 1958, a move replaces two edges of the tour by two other edges. The method is used in practice, and the number of its iterations is…
The Spectral Cost of Sharpness: Fourier Truncation, the Gibbs Bend, and the Computability of ClassificationResearch Paper
A classifier that is a finite Fourier sum cannot jump. Sharpness, meaning how quickly a classifier passes from confidently negative to confidently positive across a decision boundary, therefore has a price in bandwidth, the largest frequency it uses. Wenwei Li's manuscript The Spectral Cost of Sharpness (STOC 2027 submission #122) puts a number on that…
On the Menu Complexity of Consumer Utility MaximizationResearch Paper
Allocating a scarce service can require a recipient to incur a cost without giving the provider revenue: waiting, paperwork and other costly participation requirements are examples. Consumer utility measures the value of an allocation after subtracting those costs. A designer maximizing it must consider both who receives a service and what recipients must…
A Tight Superlinear Lower Bound on the Sketching Dimension of Weighted Spectral SparsificationResearch Paper
A spectral sparsifier of a weighted graph is a matrix that approximately preserves every quadratic form of its Laplacian. Sparsifiers are used to compute cuts and flows, solve Laplacian systems and cluster graphs. In the linear sketching model the graph is accessible only through a small number of fixed linear measurements of its edge weights. This model…
Optimal girth-dependent bounds for the Bethe approximation of the permanentResearch Paper
The permanent of an n×n matrix, per(A)=∑σ∈Sym(n)∏iAi,σ(i), is the partition function of the weighted perfect-matching model, and computing it is #P-hard even for 0–1 matrices (Valiant 1979). Randomized approximation to any factor 1+ε is possible in polynomial time (Jerrum–Sinclair–Vigoda 2004),…
Convergent Dynamics in Second Price Autobidding GamesResearch Paper
Online advertising platforms sell impressions through repeated auctions in which advertisers do not bid by hand: an autobidder scales each value by a pacing multiplierαi∈[0,1] so that the advertiser's spending stays within its budget. When every advertiser paces at once, the multipliers interact, and the natural steady state is a second-price…
Adaptive Data Analysis and Adversarial Robustness on Insertion-Deletion StreamsResearch Paper
Statistical analyses are often adaptive: an analyst inspects earlier results on a data set before choosing the next test. When the tests are chosen this way, the empirical answers on a fixed sample can overfit, and a result that looks significant may only reflect the sample [HU14, SU15, DFH+15b]. Adaptive data analysis turns this into a question about…
A Hitting Set Lemma for HDX & ApplicationsResearch Paper
The hitting set lemma for expander graphs bounds the probability that a random walk stays inside a fixed set of vertices: for a graph whose normalized second singular value is at most λ and a set S of density μ, a (d−1)-step walk from a random vertex stays in S with probability at most μ(μ+λ)d−1. Results of this type underlie…
Distinguishability Threshold for Random Geometric GraphsResearch Paper
The binomial random graph G(n,p) joins every pair of n vertices independently with probability p. Many real networks are instead built from proximity: each vertex carries a hidden position, and nearby vertices are joined. The spherical random geometric graphG(n,d,p) is the high-dimensional version of this model. In high dimension the geometry should wash…
Fully Scalable MPC Algorithms for Euclidean Clustering: Constant Approximation in Constant RoundsResearch Paper
Power-z Facility Location is the Lagrangian relaxation of (k,z)-Clustering, the problem family that contains k-Median (z=1) and k-Means (z=2): instead of a hard limit of k centers, every opened center costs a uniform price λ>0. A solution of the relaxation is useful for clustering only if it is Lagrangian multiplier preserving (LMP): its connection…
A Near-Linear Element-Kernel for d-Hitting SetResearch Paper
d-Hitting Set is a central covering problem of parameterized complexity: many deletion problems whose obstructions have bounded size (Cluster Vertex Deletion, Feedback Vertex Set in Tournaments, Split Vertex Deletion, d-Path Vertex Cover) are instances of it. A kernel shrinks an instance in polynomial time to an equivalent one whose size depends on the…
Second-Best Gains from Trade in Matching MarketsResearch Paper
Two-sided markets match buyers with sellers: labor markets, ride-sharing, advertising exchanges, procurement. If every buyer's value and every seller's cost were public, a designer would choose the feasible set of trades with the largest total surplus, the first best. Values and costs are private, and the Myerson–Satterthwaite theorem (Myerson and…
A Complete Characterization of Central String Queries in Compact SpaceResearch Paper
Text indexes such as compressed suffix trees answer queries about a string T of length n over an alphabet [0..σ) while using space close to the nlogσ bits of the text itself. One of their standard components is the longest common prefix information of the sorted suffixes. Sadakane [Sad02] showed that the permuted LCP arrayPLCPT ca…
A Fixed Parameter Sublinear Time Approximation Scheme for Metric Min-Sum ClusteringResearch Paper
k-minsum clustering asks for a partition of a finite point set into k clusters minimizing the sum of all intra-cluster distances. It is a density-based clustering objective: unlike k-center, k-median or k-means, it charges every pair of points that share a cluster, so it has no notion of a cluster center. Its complement, the sum of inter-cluster distances,…
Sublinear Metric Distortion for MatchingResearch Paper
One-sided matching assigns n agents to n items, one item each. In many settings the cost an agent incurs from an item is a distance (a commute, a mismatch of skills, a travel time), but a mechanism can only ask agents to rank items, not to report distances. Metric distortion measures the price of this restriction: agents and items lie in an unknown metric…
Non-signaling PCPs as Algebraic Proofs, and Total Coefficients Lower Bounds for Sherali–AdamsResearch Paper
Succinct non-interactive arguments (SNARGs) for NP from standard cryptographic assumptions are a central open problem in cryptography. Devadas, Hopkins, Kalai, Kothari, Lombardi and Mathialagan (DHK+26) showed that non-signaling PCPs for NP whose completeness has short Extended Frege proofs yield SNARGs for NP from LWE. Chen and Jin (STOC 2027 submission)…
Towards a Doubly Efficient IP = PSPACEResearch Paper
An interactive proof lets a verifier with limited resources check a claim "x∈L" by exchanging messages with a prover. The theorem IP=PSPACE of Lund, Fortnow, Karloff and Nisan and of Shamir (1992) shows that every time-T, space-S computation can be checked by a poly(S,n)-time verifier. In those protocols the honest prover…