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.
Quantum Copy Complexity of Testing Monotonicity and Other PropertiesResearch Paper
Property testing asks whether a small amount of information about an unknown object suffices to decide if it has a property or is far from having it. Monotonicity of Boolean functions on the hypercube is the standard test case of the field, studied with classical samples, classical queries and quantum queries (Goldreich et al. 2000; Khot–Minzer–Safra 2018; B…
The Power of Test-Time Training for Approximate SamplingResearch Paper
A language model generates a sequence one token at a time, and a common way to improve it at inference time is to steer generation with a learned value function that scores partial sequences. Golowich, Moitra and Rohatgi model this as sampling: an unknown target distribution μ⋆ on strings of length n is accessible only through an oracle μ^ that…
The Exact Welfare Guarantee of Fixed-Price Bilateral TradeResearch Paper
A seller owns one item and a buyer may want it; their values are private and independent. Myerson and Satterthwaite showed that no mechanism is at once efficient, incentive compatible, individually rational and budget balanced (MS83). The simplest mechanism that keeps every property but efficiency is a fixed price: post one price, and trade happens if both…
Keeping data in order while it changes is a basic algorithmic task. In online sorting, introduced by Aamand, Abrahamsen, Beretta and Kleist (AABK23), real numbers arrive one at a time and must be placed immediately into an array of n cells; the aim is to keep the sum of absolute differences between neighbouring stored elements small compared with the sorted…
Burnside Problems for Matrix Semigroup Quotients with Applications to Border ComplexityResearch Paper
In 1902 Burnside asked whether a finitely generated group in which every element has finite order must be finite. The answer is negative in general (Novikov and Adian, 1968), but positive for groups of complex invertible matrices (Schur), for invertible matrices over any field (Kaplansky), and for finitely generated matrix semigroups over any field…
Contextual Search and Bilateral Trade with a Trace-Square-Root PotentialResearch Paper
Contextual search models a seller who quotes a price for a product described by a feature vector and learns only whether the customer bought: a hidden vector determines a target value along each observed context, and the learner sees one bit per round, whether its guess was too high or too low. The problem arose from feature-based pricing and auctions…
A dichotomy theorem for approximating CSPs in random-order streamsResearch Paper
A constraint satisfaction problem asks for an assignment of letters to variables satisfying as many given constraints as possible. In the single-pass streaming model, constraints arrive one at a time and an algorithm keeps limited memory between them. Classification results describe how approximation quality trades against memory when an adversary chooses…
Optimal High Probability Bounds for Random Order Online SortingResearch Paper
An online sorting algorithm receives n real numbers one at a time and must place each immediately and irrevocably into an empty cell of an array with exactly n cells. The objective is the total variation of the completed array. Offline, sorting gives the input range, so the natural measure is the competitive ratio. Related work allows more output cells than…
A Dichotomy for Boolean Complex Holant Problems with Conjugate-Closed Signature SetsResearch Paper
Computing output probabilities of a quantum circuit exactly, known as exact strong simulation, is a contraction of a tensor network that contains each gate tensor together with its entrywise complex conjugate. The natural counting framework for such contractions is the Holant problem: a signature grid assigns a tensor to each vertex of a graph, and the…
Real-to-Integer Reduction for All-Pairs Shortest PathsResearch Paper
All-Pairs Shortest Paths (APSP) asks, for a directed edge-weighted graph on n vertices with no negative cycles, for the length of a shortest path between every pair of vertices. The textbook Floyd–Warshall algorithm runs in time O(n3) (Floyd 1962). APSP is one of the central problems of fine-grained complexity, and many problems are equivalent to it under…
Byzantine Agreement with Signature TokensResearch Paper
Byzantine agreement (BA) asks n parties, up to f of them under an adversary's control, to decide a common bit. It is the core problem of fault-tolerant distributed systems and of blockchain consensus. In the partially synchronous model of Dwork, Lynch and Stockmeyer (JACM 1988), messages may be arbitrarily delayed until an unknown stabilization time, and…
Near-Optimal Almost-Ramsey Spanning Tree Covers, via Layered ClusteringsResearch Paper
A tree cover of a weighted graph replaces its shortest-path metric by a small collection of trees, so that every pair of vertices is well served by at least one of them. Tree covers underlie compact routing schemes, distance oracles and spanners, because a tree is far easier to store and to route on than a graph. The hardest variant asks for spanning trees,…
Arbitrarily Slow Polynomial Convergence of Fictitious PlayResearch Paper
Fictitious play (Brown, 1951) is one of the oldest dynamics for computing a Nash equilibrium of a two-player zero-sum game: at each step, each player best responds to the empirical distribution of the opponent's past actions. Robinson (1951) proved that the empirical strategies converge to the equilibrium set, and Shapiro (1958) extracted the upper bound …
Connectivity in a New Bounded-Space Dynamic ModelResearch Paper
Undirected s–t connectivity is a central test case for time–space tradeoffs on a read-only input. Breadth-first search takes linear time and Θ(n) words. The random walk of Aleliunas et al. (1979) takes O(logn) bits and much longer. Feige (1997) and others charted the range in between, and Reingold (2008) showed that the problem is in deterministic…
Symmetric Circuits for Matrix MultiplicationResearch Paper
Fast matrix multiplication algorithms beat the n3 operations of the schoolbook method by treating different parts of the input matrices differently. The schoolbook method, and the recursive four-block algorithm that splits each matrix into 2×2 blocks, are instead invariant under simultaneously permuting the columns of A and the rows of B, or at least…
Gross Substitutes Welfare in Random OrderResearch Paper
In the secretary problem a decision maker sees items one at a time in uniformly random order and must accept or reject each on arrival, irrevocably. Dynkin's rule (observe until a 1/e fraction has passed, then take the first record) selects the best of n items with probability 1/e, and no rule does better as n→∞. The matroid secretary problem of…
Composable Content-Oblivious Leader Election on Eulerian GraphsResearch Paper
In a content-oblivious network every message may be corrupted arbitrarily, so a message carries no information beyond its arrival: communication reduces to pulses, and a node's behaviour may depend only on the ports at which pulses arrive. Censor-Hillel, Cohen, Gelles and Sela showed that any asynchronous algorithm can still be simulated on a…
Optimal Dynamic Strings in Compressed SpaceResearch Paper
Many applications store large collections of highly repetitive strings: versioned documents, genome collections of one species, logs. Grammar compression represents a string by a small context-free grammar that derives only that string, and a dynamic strings data structure keeps a whole collection in such a form while supporting concatenation, splitting and…
A Walk from Free Probability to Matrix Discrepancy I: Matrix SpencerResearch Paper
Given real symmetric m×m matrices A1,…,An of operator norm at most one, how small can ∥∑iσiAi∥ be made by a choice of signs σ∈{−1,1}n? Random signs give 2nlog(2m) by the noncommutative Khintchine inequality. For diagonal matrices, which encode ordinary vector discrepancy, Spencer's theorem gives O(n) when …
An Exponential Top Fan-In Hierarchy for Border Depth-4 CircuitsResearch Paper
A central question about constant-depth algebraic circuits is what one additional summand at the output gate buys. Deterministic identity testing for depth-3 circuits of top fan-in k runs in time polynomial in the size with an exponent that grows with k (Kayal and Saxena, 2007), so it is natural to ask whether the power of these circuits grows with k.…
Counting and Sampling by Local Repair: From the Lovász Local Lemma to Random k-SATResearch Paper
The Lovász local lemma (Erdős–Lovász 1975) gives a condition under which rare, weakly dependent bad events can all be avoided: with probability at most p per event and at most D dependencies, ep(D+1)≤1 suffices. Existence is governed by the first-neighbourhood scale pD.
Splay trees are almost dynamically optimalResearch Paper
Binary search trees maintain an ordered set under membership and predecessor queries. A balanced tree answers each query in Θ(logn) time, which is optimal in the worst case, but on many access sequences far less time suffices: repeated, sequential or local accesses can be served at nearly constant cost per access. Dynamic optimality asks for a single…
A New Characterization of Streaming Decidability of Boolean CSPs Under DeletionsResearch Paper
A constraint satisfaction problemCSP(Γ) asks whether n Boolean variables can satisfy a multiset of constraints drawn from a fixed finite set Γ of relations. In the streaming model, constraints arrive one at a time and an algorithm keeps limited memory. With insertions only, the one-pass space of satisfiability is governed by…
On the Cost of Set-Multilinearisation in Positive CharacteristicResearch Paper
An algebraic circuit computes a polynomial from variables and constants with additions and multiplications. Proving superpolynomial lower bounds against arbitrary circuits is the algebraic version of the central question of complexity theory, and depth reduction makes low-depth circuits a meaningful target: a strong enough bound for depth four would…
Lifting Sherali-Adams Degree to Unary Sherali-Adams over Parities SizeResearch Paper
Proving superpolynomial lower bounds for AC0[2]-Frege, bounded-depth Frege with parity gates, is a long-standing open problem in proof complexity. Weaker systems that reason about parities are studied as steps towards it. Resolution over parities, Res(⊕), reasons with disjunctions of linear equations over F2. Until recently its lower…