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.
Low Soundness Linearity Testing on Subsets of the HypercubeResearch Paper
A linearity test reads a function f:F2n→F2 at a few random points and accepts or rejects. It is perfectly complete if it always accepts linear functions. It has low soundness if, whenever it accepts with probability at least (1+δ)/2, f agrees with an affine function on at least a (1+s(δ))/2 fraction of inputs, with s(δ)>0…
The Price of Anarchy in Markets for LemonsResearch Paper
Trade in a market for lemons can fail even when trade is efficient: when the seller knows more than the buyer about the quality of the good, a price at which the seller is willing to sell signals bad news to the buyer, and adverse selection can unravel the market (Akerlof 1970). Securities markets, used-asset markets and insurance all share this structure.…
Random tensor isomorphism under orthogonal and unitary actions: Smoothed and average-case analysisResearch Paper
Two 3-tensors A,B∈Cn×n×n are unitarily isomorphic when a change of orthonormal basis in each of the three modes turns one into the other. Deciding this, and its robust version (is B close to some basis change of A?), is the tensor analogue of comparing two matrices up to unitary equivalence. It arises in quantum information, where a…
Finding Hypercliques Faster Than Brute ForceResearch Paper
A hypergraph is a collection of subsets of a vertex set, called edges. In a (k−1)-uniform hypergraph, every edge contains exactly k−1 vertices. A k-hyperclique consists of k vertices for which every (k−1)-subset is an edge. Checking each possible selection gives a running time of order nk. The algebraic question behind this mission asks whether the…
Estimating a Transition Point from Gibbs and Ground StatesResearch Paper
Learning a phase transition from a finite quantum system involves two independent choices: how many state copies to observe and how large a system each copy contains. A transition is defined by an infinite-volume limit, whereas every available density matrix belongs to a finite cube with a specified boundary. More copies refine information about that finite…
A Tight Ω(m) Information-theoretic Lower Bound for Randomized Online Set CoverResearch Paper
Online set cover asks how many sets must be purchased when the elements requiring coverage arrive one at a time. It is relevant to the analysis of algorithms that make irrevocable covering decisions before learning which demands will occur. Knowing the available sets does not reveal the future demands. The mathematical question is how much this missing…
Multi-Party Error Resilience beyond n1Research Paper
An information dissemination task asks every participant in a communication network to learn every participant's input. This is a useful benchmark for adversarial communication: once a participant knows the full input vector, it can evaluate any specified function of those inputs locally. The distinction between learning all inputs and learning only the…
Small classes have linear neighbourhood complexityResearch Paper
A graph class can be studied by counting how many of its graphs exist on a fixed set of labels. It can also be studied by counting the different adjacency patterns visible on a chosen vertex set inside one graph. These are different measurements: the first concerns a collection of whole graphs, while the second concerns local observations within an…
Tight Release Schedules under Distribution ShiftResearch Paper
A deployed predictor can remain unchanged while its owner collects labels, retains observations and computes candidate replacements. A limit on replacing the deployed predictor therefore creates a statistical scheduling question: how much prediction error is unavoidable when only a few replacements are allowed? This differs from restricting access to labels…
Fine-Grained Proof Complexity for Elementary Arithmetic in Extended FregeResearch Paper
Extended Frege (EF) is the propositional proof system obtained from the textbook Frege system by adding the extension rule, which names a fresh variable as an abbreviation of a short formula (Cook–Reckhow 1979). Recent cryptographic constructions rely on EF proofs of correctness of concrete circuits, and the efficiency of those constructions is governed by…
Byzantine Partition Detection Under ChurnResearch Paper
Byzantine fault-tolerant protocols are proved correct under two separate assumptions: a bound t on the number of faulty processes, and enough vertex connectivity in the communication network (classically, connectivity above a multiple of t). The second assumption is usually taken for granted. Sengupta and Perrin ask whether the participants themselves can…
Optimal Semi-Honest Information-Theoretic Secure Multi-Party Computation with Servers and ErasuresResearch Paper
Secure multi-party computation lets parties compute a joint function of private inputs while revealing nothing beyond the output. In the client–server setting, a few clients with inputs delegate the work to n servers that have no inputs, and an adversary may corrupt one client and a fraction α of the servers. Oblivious transfer (OT) is the basic…
Near-Optimal One-Way Functions, Direct Product Hardness and Hash Functions from iO and NP versus coNPResearch Paper
A one-way function is an efficiently computable function f:{0,1}n→{0,1}m that no efficient algorithm can invert on a random image: given y=f(x) for uniform x, it is hard to find any x′ with f(x′)=y. One-way functions are the minimal assumption of private-key cryptography, and their quantitative strength, the best inversion probability an…
Pairwise Exchanges of Freely Replicable Goods with Negative ExternalitiesResearch Paper
Datasets, software and patents are freely replicable: giving a copy costs the giver nothing directly. Firms that hold such goods are often competitors, so each one gains from acquiring a good and loses when a rival acquires one. Data consortia and patent pools face this tension: every member wants access to the others' goods, and no member wants its rivals…
A Fast Algorithm for Subspace ConvolutionResearch Paper
Subset summation asks, given a value f(A) for every subset A⊆[n], for all sums (Zf)(B)=∑A⊆Bf(A). The fast zeta transform does this in O(n2n) additions, and with its inverse, the Möbius transform, it underlies the fastest known algorithms for chromatic number, Hamiltonian path and covering products (Björklund–Husfeldt–Koivisto 2009; Bj…
Initialization with Exponentially Fewer BitsResearch Paper
Wireless sensor networks and ad hoc radio networks often consist of mass-produced devices that start out indistinguishable: they carry no identifiers, run identical code, and share one radio channel. Many distributed algorithms assume that nodes have distinct IDs. So a basic first task is initialization: the n nodes must give themselves the distinct IDs …
An approximate cactus-decomposition for vertex-connectivityResearch Paper
The cactus theorem of Dinitz, Karzanov and Lomonosov (1976) states that the minimum edge-cuts of a connected graph are represented by a cactus: a connected graph in which any two cycles share at most one vertex. That representation underlies algorithms for enumerating minimum cuts, connectivity augmentation and dynamic minimum cuts. For vertex-connectivity…
An Algebraic Semantic Framework for Nondeterministic ComputationResearch Paper
Zheng, Zheng, Wang and Huang, in An Algebraic Semantic Framework for Nondeterministic Computation (July 2026, a STOC 2027 submission), propose to study nondeterminism through algebraic structure attached to tape symbols: two nondeterministic branches are regarded as genuinely independent when the algebraic numbers that encode them are linearly independent…
Multitask Contracts: Realizing the Value of BundlingResearch Paper
Delegating many tasks to one agent is the norm in practice: a contractor builds several components of a project, a crowd worker labels a batch of items, a manager runs several business lines. The principal cannot observe effort, only which tasks succeed, so she must pay for outcomes. A natural design question in the multitask principal–agent model of Zhao…
Demystifying Border of Structured Algebraic Circuits via Differential EquationsResearch Paper
Algebraic complexity theory asks how many additions and multiplications are needed to compute a polynomial. Next to exact computation it studies approximate computation: a polynomial f is in the border of a class of circuits if circuits from the class, with constants depending on a parameter ε, compute f+εg, so that f is their limit as …
Recursive Operator Localization and Spectral Gap Descent via the Geometry of Local Spectral ExpansionResearch Paper
Lower bounds on spectral gaps control the directions outside the kernel of a positive operator: the gap of a Hamiltonian above its ground-state energy, or the gap of a reversible Markov generator above its stationary subspace. For large systems such bounds are hard to obtain directly. Local-to-global methods combine tractable local estimates with control of…
An Exponential Succinctness Gap between Three-Variable Logic and the Calculus of RelationsResearch Paper
Tarski showed in the 1940s that, over binary relational signatures, three-variable first-order logic (FO3) and the calculus of relations (CoR), a variable-free algebra of binary relations, define the same binary queries (Tarski 1941; Tarski–Givant 1987). The two translations are lopsided: a CoR term T becomes an FO3 formula of size O(∣T∣)…
Global asymptotic stability of homogeneous polynomial vector fields is undecidableResearch Paper
A differential equation can have a simple finite description while its solutions have complicated long-term behavior. In control theory, one basic question is whether every state eventually approaches an equilibrium and whether starting close to it guarantees remaining close. An algorithm answering that question for every polynomial vector field would…
Deterministic Root-Finding over Finite Fields with Elliptic CurvesResearch Paper
Let Fq be a finite field with q=pe elements. Root-finding asks, given a polynomial f∈Fq[X] that is split (a product of linear factors) and separable (coprime with its derivative), for the set of its roots in Fq. Factoring arbitrary polynomials over Fq reduces to this problem in deterministic polynomial time (Berleka…