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.
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 …
Softmax Attention with Any Temperature in Fixed Dimension: Matching the Best Known Maximum-Inner-Product BoundsResearch Paper
Softmax attention is the basic operation of Transformers (Vaswani et al., 2017). Direct evaluation compares every query with every key, so a context of length n costs n2 exponentials even when the dimension is fixed. A question for theory is whether this quadratic cost is necessary, and how attention relates to the classical batch maximum inner product prob…
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…
When Does Private Data Collection Need Interaction? Online Selection under Local Differential PrivacyResearch Paper
Platforms that select contributions under limited resources increasingly see their users only through randomized reports. Federated learning systems choose participants for each round from signals of local utility, crowdsourcing assigns arriving workers to tasks of limited capacity, and large telemetry deployments run client-side randomization as the…
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…
Randomness-Efficient Robust Locally Testable Codes in the Low-Acceptance Regime from HDXsResearch Paper
A locally testable code (LTC) is an error-correcting code C⊆Σn with a randomized test that reads few coordinates of a word f and rejects with probability that grows with the distance of f from C. LTCs are a core ingredient of probabilistically checkable proofs and of property testing. The usual guarantee is in the high-acceptance regime: if…
The Competitive Ratio of Online Budgeted Allocation is Strictly Smaller than 1-1/eResearch Paper
Online budgeted allocation models the sale of ad slots to advertisers with budgets. Items (queries) arrive one at a time, each advertiser bids on each item, and the algorithm must assign every item irrevocably, before it sees the next one. The quality of an online algorithm is its competitive ratio: the worst case, over inputs, of its expected revenue…
Online Graph Coloring: Competitive Ratios Separating Randomized and Deterministic AlgorithmsResearch Paper
In online graph coloring the vertices of a graph arrive one at a time, each with its edges to the vertices that arrived earlier, and an algorithm must give every new vertex a color immediately and irrevocably, different from the colors of its neighbours. The problem models resource assignment under uncertainty (register allocation, frequency assignment,…
Unconditional Boolean Dynamic Lower Bounds from DisjointnessResearch Paper
Lower bounds for dynamic data structures are proved in the cell-probe model of Yao, which charges only for memory accesses: memory consists of w-bit cells, each read or write costs one probe, and computation is free. A lower bound in this model holds for every implementation on a word RAM, so it is unconditional. For dynamic problems with Boolean answers,…
Characterizing Local Breadth in Language GenerationResearch Paper
An algorithm sees an unknown language one string at a time and must produce new strings of that language. Language generation in the limit, introduced by Kleinberg and Mullainathan (2024), models this as a game. The target is any member of a countable candidate family, an adversary enumerates it, and the algorithm must eventually output only unseen strings…
The Binary Tree Mechanism is Optimal for Differentially Private Continual CountingResearch Paper
A continual counting mechanism watches a stream of bits x1,…,xn and releases at every step the running count ∑j≤ixj, while the contribution of any one individual stays hidden. The task was introduced by Dwork, Naor, Pitassi and Rothblum (STOC 2010) and by Chan, Shi and Song (ICALP 2010). It is a subroutine of private online learning, private…