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.
FPT iff PTIME for Homomorphism Problems on Sparse-Incidence and Bounded-Independence PatternsResearch Paper
A hypergraph records a finite collection of constraints by assigning each constraint the set of variables it involves. In database query evaluation and constraint satisfaction, the shape of these overlaps can determine which decomposition methods are available. Different notions of width measure different freedoms in choosing a decomposition. Fractional…
Factor Closure in Noncommutative Algebraic ComplexityResearch Paper
A basic structural question in algebraic complexity is whether factors of a polynomial with a small circuit also have small circuits. In the commutative setting small-circuit bounds for factors were established by Kaltofen ([10]), closure of commutative VNP in characteristic zero and sufficiently large characteristic was proved by Chou, Kumar and Solomon…
A Tight Space Lower Bound for Pivot-Based Distance OraclesResearch Paper
A distance oracle stores information about a graph so that later queries can estimate the distance between two vertices. Storing a separate answer for every pair can require quadratic space, even when the input graph itself has only linearly many edges. Allowing a multiplicative error creates a space–accuracy trade-off. The question addressed here concerns…
Testing Implies Distance Estimation with Polynomial LossResearch Paper
An adjacency query reveals one bit of a graph: whether two specified vertices share an edge. When the graph is large, even reading its entire adjacency matrix can be prohibitive. Property testing asks whether a graph satisfies a specified condition or requires a substantial fraction of its adjacencies to be changed. Distance estimation asks for that…
Breaking the Parity Barrier for Constant-Depth CircuitsResearch Paper
A Boolean circuit computes a bit by combining input bits through logical gates. Circuit complexity asks how many gates a specified function needs when its depth is restricted. Lower bounds separate computational resources even when the function itself is easy to evaluate. For circuits using AND and OR gates with unrestricted fan-in, parity has long provided…
Learning AI Agents, Market Makers, and Stress in Automated MarketsResearch Paper
Two markets can exhibit the same distribution of individual returns while arranging losses differently in time. For a monitor concerned with consecutive losses, the duration of a stressed interval is a separate object from the frequency of stressed periods. The question here is whether this distinction survives a model in which trades respond to the…
Byzantine Broadcast in O(n2) CommunicationResearch Paper
A replicated service needs a precise rule for turning one participant's proposed bit into a common decision. Byzantine broadcast asks for such a rule even when faulty participants can send inconsistent messages, omit messages, or change their behavior after being corrupted. The receiver of a message cannot infer that other parties received the same message.…
Adaptive Steps and Certificates for Semi-Streaming Shortest PathsResearch Paper
A graph can have too many edges to keep in memory while its vertices and a sparse collection of edges still fit. In the semi-streaming model, an algorithm reads an insertion-only stream repeatedly and keeps a small working memory between scans. For shortest paths, the number of complete scans is a substantial part of the cost. Assadi, Hoppenworth and…
On ZLIP: Combinatorial Structures and Reduction to √n-ZSVPResearch Paper
A lattice is the set of integer combinations of a finite collection of linearly independent vectors. Its geometry can be simple while its given coordinates conceal that simplicity. The lattices considered here are Euclidean rotations of the integer grid: they have an orthonormal basis, but the input supplies an arbitrary integer change of that basis.…
Self-stabilising approximate clock synchronisation requires linear timeResearch Paper
Distributed systems use logical clock ticks to coordinate rounds of communication. A self-stabilising protocol must recover even when transient faults leave every process in an arbitrary local state. A second requirement is tolerance of permanent failures while recovery proceeds. These requirements occur together: an event that corrupts stored state can…
Fluid Limits and Upper Bounds for Randomized Greedy MatchingResearch Paper
A matching is a set of graph edges with no shared endpoint. Matching algorithms assign disjoint pairs when each participant can receive at most one partner. A local algorithm can build a matching without inspecting the whole graph, but its decisions can prevent later pairs from forming. The Modified Randomized Greedy algorithm, abbreviated MRG, introduces…
Computing faster with a full memory: Catalytic algorithms break time-space lower boundsResearch Paper
A catalytic algorithm, introduced by Buhrman, Cleve, Koucký, Loff and Speelman (STOC 2014), has a small clean work tape and a large dirty work tape. The dirty tape starts with arbitrary content the algorithm cannot choose, and must be returned intact at the end. The original question was whether such memory helps at all, and the first answers concerned…
Maximum Matching and Related Problems in Catalytic LogspaceResearch Paper
A matching in a graph is a collection of edges that share no vertices. A maximum matching has as many edges as any such collection. Matching is a basic problem in combinatorial optimization, but the computational resources needed to construct one depend on the machine model. A polynomial-time procedure can retain intermediate data that do not fit in…
The variable Lovász Local Lemma concerns systems of constraints whose individual failures are rare and whose interactions are local. A variable may describe a color, a choice of a neighbor, or a random decision in another algorithm. Each constraint inspects its own variables. The aim is to select their values so that every constraint holds simultaneously.…
Perfect Local Sampling and Subquadratic Counting below the Hard-Core Uniqueness ThresholdResearch Paper
The hard-core model samples an independent set I of a finite graph with probability proportional to λ∣I∣; at λ=1 this is the uniform distribution on independent sets. It is a standard test case for the computational phase transition in counting and sampling, because the tree-uniqueness threshold …
The Power of Simple Mechanisms: A Tight e-Approximation for Gains from Trade in Matching MarketsResearch Paper
A two-sided market brings together buyers who value an item and sellers who hold it at a cost. The first-best gains from trade (GFT) match each trade whose value exceeds its cost. The Myerson–Satterthwaite theorem says that no incentive-compatible, individually rational and budget-balanced mechanism attains this benchmark, even in bilateral trade. So the…
A collection of pairwise contests can have cyclic outcomes: one contestant defeats a second, the second defeats a third, and the third defeats the first. A useful substitute for a contestant who defeats everyone is a king: a vertex that reaches every other vertex either directly or through one intermediary. The question here concerns the information needed…
Almost-Linear Modular Composition over Arbitrary Commutative RingsResearch Paper
Polynomial algorithms often need to substitute one polynomial into another while retaining only its remainder modulo a third polynomial. This operation is called modular composition. It describes evaluation in a polynomial quotient algebra, so it appears whenever an algebraic element is represented by a polynomial relation. Over finite fields it occurs in…
Computation in Anonymous Directed Dynamic Networks: Exact Worst-Case Termination Time and Network-Wise IntractabilityResearch Paper
Distributed systems can need to know how many participants they contain even when
communication links change from round to round. Counting asks every participant
to determine this number exactly and then stop. Without identifiers, equal messages
need not originate from the same participant. Receiving a correct estimate is also
different from having enough…
Polynomially larger deletion codes by linear hashing of substring countsResearch Paper
An error-correcting code selects some words of a fixed length so that a receiver can distinguish the selected words after errors. Insertions and deletions change the positions of later letters, making recovery a synchronization problem as well as a problem of identifying changed symbols. Researchers studying communication and storage channels therefore ask…
Tight Bounds for Randomized Generalized k-Server on Uniform MetricsResearch Paper
The generalized k-server problem was introduced by Koutsoupias and Taylor (KT04) as a model of k heterogeneous servers, each moving in its own metric space, that must jointly answer requests naming one location per server. It contains the classical k-server problem, weighted k-server, and paging with heterogeneous cache slots as special cases, and it is a…
A Bulow–Klemperer Theorem for Bundling and Improved Approximation Bounds for Simple AuctionsResearch Paper
A seller with several distinct items must decide both what to offer and how to price it. Even when there is only one buyer and the buyer values a collection by adding its item values, the seller can offer lotteries as well as deterministic bundles. The benchmark of an optimal truthful auction therefore includes many more choices than posting one price for…
A QPTAS for Stochastic Scheduling of Bernoulli JobsResearch Paper
Scheduling systems often know a job's processing-time distribution before they know
its realized duration. An adaptive policy chooses the next job after observing
previous outcomes. For Bernoulli jobs, a job either completes immediately or
occupies a machine for its full positive size. This isolates the scheduling risk
created by a small probability of a…
Tree Equivalence of Higher-Order Recursion Schemes Is UndecidableResearch Paper
A higher-order recursion scheme (HORS) is a finite, simply typed recursive program whose terminal symbols act as tree constructors. Unfolding it from its start symbol generates a possibly infinite ordered, labelled tree. Schemes are a standard model of higher-order functional programs: Ong proved that monadic second-order properties of the generated tree…
Online carpooling against an oblivious adversaryResearch Paper
In the online carpooling problem (Fagin–Williams 1983), people share rides in pairs and each ride must immediately name one of the two as the driver; the goal is that nobody drives much more or much less than their fair share. In graph language, edges on n vertices arrive one at a time and must be oriented immediately, keeping the indegree minus outdegree…