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.
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…
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…
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…
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…
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…
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…
Digital signatures are transferable: a party for which a signature verifies can pass it on, and it verifies for every other party too. This is what lets authenticated Byzantine agreement and broadcast tolerate a third or more faulty parties, which pairwise authentication cannot do (Lamport, Shostak, Pease 1982; Dolev, Strong 1983). Transient faults break…
Improved Bounds for Certifying Injective Norm of Sparse Random TensorsResearch Paper
The injective norm of a symmetric tensor is the largest value of its multilinear form on the unit sphere. For matrices it is the largest absolute eigenvalue and is computable in polynomial time; for tensors of order k≥3 computing it, or even approximating it, is NP-hard in the worst case (Hillar–Lim 2013). For random tensors the injective norm is small…
Convex optimization on moment polytopes: Hadamard mirror descent and efficient algorithms for quantum functionals and other tensor parametersResearch Paper
Strassen's asymptotic spectrum of tensors governs the asymptotic rank and subrank of tensors, and with them questions such as the exponent of matrix multiplication. The quantum functionals of Christandl, Vrana and Zuiddam (CVZ23) were the first explicit family of universal spectral points for complex tensors of arbitrary order. They are defined as maxima of…
The Price of Capacities for Clustering CoresetsResearch Paper
A coreset compresses a large data set into a small weighted set on which a family of clustering queries can be evaluated with relative error ε. Coresets for Euclidean (k,z)-clustering (k-median for z=1, k-means for z=2) are a standard tool for streaming, distributed and approximation algorithms, and their optimal size has been the subject of a…
Minimizing Key Schedules for Key-Alternating CiphersResearch Paper
A key-alternating cipher (KAC) encrypts a block m of a finite abelian group G by alternately adding round keys and applying fixed public permutations: x0=k0−m, xj=kj−πj(xj−1). Its provable security in the random permutation model is well understood when the t+1 round keys are independent and uniform (Hoang–Tessaro 2016), but real ciphers derive…
The Information-Theoretic Limits of Hiding Among Decoys in the Shuffle ModelResearch Paper
Hiding a genuine secret among plausible decoys is a recurring pattern in security and privacy. A honeyword system stores a user's real password together with n−1 fake ones and raises an alarm when a fake one is used (Juels–Rivest 2013). A computationally unbounded adversary who decrypts a ciphertext under every key of a small key space obtains one genuine…
Optimal Approximation for Constrained Correlation Clustering via RepulsionResearch Paper
Correlation clustering groups vertices when pairwise preferences can conflict: a positive pair prefers one cluster, and a negative pair prefers different clusters. The number of clusters is unrestricted. Must-links and cannot-links add requirements that every returned partition must satisfy. This distinction matters when a preference can be traded against…
Tight Variable-Occurrence Bounds and Exponential Separations for Moser–Tardos and WalkSAT on 3-CNFResearch Paper
WalkSAT and the Moser–Tardos algorithm (MT) are the two standard clause-driven local-repair procedures for satisfiability. Both keep a complete assignment and repeatedly pick an unsatisfied clause. WalkSAT flips one variable of it (Papadimitriou 1991, Schöning 1999); MT resamples all of its variables with fresh random bits, which is the algorithmic form of…
A multiplication table describes a binary operation on a finite labelled set. Reading the whole table requires quadratically many entries. Property testing instead asks for a decision from substantially fewer entries: accept a genuine group and reject an operation that requires many changes to become any group. This question concerns algorithms that receive…
A classical polynomial-time verifier interacting with an unrestricted prover can check every polynomial-time quantum computation: BQP⊆PSPACE=IP, the equality being Shamir's theorem. Whether this containment survives relative to an arbitrary oracle decides whether it can be proved by relativizing techniques. Bouland, Huang,…
Lotteries Protect Single-Item Sellers from Monopolist IntermediariesResearch Paper
A publisher can own an advertising impression while an exchange controls which advertiser reaches the publisher. A blockchain application can face a similar separation between the party selling an opportunity and the party selecting participating users. In such settings, optimizing an auction for direct interaction with buyers does not settle the seller's…