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.
Polynomial-time Tensor Decomposition under the Kruskal Condition and the Lovitz–Petrov GeneralizationResearch Paper
A tensor decomposition expresses a multidimensional array as a sum of outer products of vectors. Its factors describe separate contributions in each coordinate direction. In applications such as latent-variable estimation and spectral data analysis, a decomposition is useful when those contributions can be distinguished from other explanations of the same…
Non-Interactive Network Sum-Secure ComputationResearch Paper
Several users may need a server to compute an aggregate while protecting the aggregate from an observer of the communication network. Here the confidential object is the sum itself. The users' individual inputs are arbitrary deterministic values; there is no prescribed probability distribution on those inputs. Bai, Guang and Wang formulate this task with…
Comparison is All You Need: Settling the t-wise independence of AESResearch Paper
A block cipher maps fixed-length plaintext blocks to ciphertext blocks using a secret key. One way to study its statistical behavior is to fix several distinct plaintexts and ask whether their ciphertexts resemble the outputs of a uniformly random permutation. This is approximate t-wise independence: it controls every test of the joint outputs at those…
Settling the Approximability of Submodular Facility LocationResearch Paper
Submodular facility location asks how to assign clients to facilities when the cost of serving a group has diminishing marginal increments. All facilities share the same cost function. This homogeneous setting distinguishes the question from variants with a different function at each facility. It allows economies of scale while retaining the geometric…
A General Technique for Metrical Task Systems with Action PredictionsResearch Paper
An online movement problem reveals requests one at a time. A decision maker must serve the current request without seeing the remaining requests, and moving between possible decisions has a cost. In caching, the decision records the contents of a cache; in server problems, it records server locations. Predictions can recommend the next decision, but an…
Existence of the Core in Approval-Based Committee ElectionsResearch Paper
In an approval-based committee election, each of n voters reports the set of candidates she approves, and a committee of k candidates must be chosen. Proportional representation asks that every group of voters large enough to "deserve" some seats, and united enough to agree on candidates, gets them. The strongest standard axiom of this kind is the core: no…
Decentralized Dynamic Stable MatchingResearch Paper
Two-sided matching markets with stable outcomes — students and schools, workers and firms, users and servers — are classically solved by a central clearinghouse running deferred acceptance (Gale and Shapley, 1962). Many markets have no such clearinghouse: participants act on local information, and the population changes over time without announcement. A…
Replicable Mean Estimation via Random Lattice RoundingResearch Paper
A randomized algorithm is ρ-replicable if two runs on independent samples, sharing their random seed, return the same output with probability at least 1−ρ (Impagliazzo–Lei–Pitassi–Sorrell 2022). Many replicable algorithms (PAC learning, bandits, hypothesis testing) reduce to replicable mean estimation in Rd. Hopkins, Impagliazzo, Kane, Liu and…
The Space Complexity of Property TestingResearch Paper
Property testing asks for randomized algorithms that query a Boolean function f:{0,1}n→{0,1} at a few points and decide, with probability at least 2/3, whether f has a property P or is ε-far from it, meaning that at least an ε fraction of its values must change to land in P. The classical resource is the number…
Memory-Sample Tradeoffs for Agnostically Learning HalfspacesResearch Paper
Agnostic learning of halfspaces asks for a linear classifier whose error is within ε of the best halfspace, with no assumption on how labels are generated. Statistically the problem is easy: O(d/ε2) samples suffice in dimension d. Computationally it is not: the best known algorithms run in time dpoly(1/ε) or …
Towards Asymptotically Optimal Pseudorandom Functions: Linear-Size Circuits with Exponentially Small BiasResearch Paper
A keyed function familyFK:{0,1}n→{0,1}n is the basic object of symmetric cryptography. Two goals pull against each other: the function should be cheap to evaluate, ideally by a circuit of size O(n), and it should resist attacks running in time 2Ω(n). Whether both are possible at once is open in general. Dinur and Ishai settle the half that…
Fractional colorings of Kr-free graphs with local demandsResearch Paper
Lower bounds on the independence number in terms of degrees are among the oldest themes of extremal graph theory. For triangle-free graphs, Ajtai, Komlós and Szemerédi proved α(G)=Ω(nlogd/d) for average degree d, and Shearer sharpened this to α(G)≥nf(d) with the explicit function f(d)=(dlogd−d+1)/(d−1)2 (Shearer 1983), later to the…
The Gap Between Average-Case and Worst-Case ComplexityResearch Paper
Impagliazzo's "five worlds" ([Imp95], Structure in Complexity Theory 1995) separate two questions that complexity theory cannot yet tell apart. Is NP hard in the worst case, and is it hard on average, for instances drawn from an efficiently samplable distribution? In the world called Heuristica, every problem in NP is easy on average, yet…
Sharp Second-Order Thresholds for Random Algebraic CoverageResearch Paper
From k elements of an abelian group one obtains 2k indexed subset sums; in a noncommutative group the analogous objects are products taken in the original input order. A basic all-target question is when these representations reach every element of the group. Erdős and Rényi studied this model for arbitrary finite groups, including noncommutative ones, and…
Incremental Open Addressing Has No Time-Space TradeoffResearch Paper
Open addressing is the hash-table framework behind linear probing, quadratic probing, double hashing, Robin Hood hashing and cuckoo hashing. In the incremental (insert-only) setting, keys are inserted one after another into an initially empty array of n slots until a target load factor (fraction of occupied slots) is reached. For more than half a century…
Improved Algorithms in the Random-Order Model: Knapsack, GAP, and BeyondResearch Paper
Online services allocate limited resources to requests arriving over time. Accepting a request earns value but uses capacity a later, more valuable request might have needed, and decisions cannot be revised. The simplest such model is online knapsack; the generalized assignment problem (GAP) extends it to several machines on which an item may have different…
From Bilateral Trade to Matching Markets: Sharp Gains from TradeResearch Paper
In a matching market, unit-demand buyers and unit-supply sellers with privately known values and costs are connected by a compatibility graph, and a platform or market maker must decide who trades with whom and at what prices. Myerson and Satterthwaite (MS83) showed that incentive compatibility, voluntary participation and budget balance already rule out…
Tight Information-Theoretic Threshold for Decoded Quantum Interferometry with Local Quantum DecodersResearch Paper
Decoded quantum interferometry (DQI) is a quantum algorithm for sparse constraint problems such as Max-k-XORSAT: it prepares a state whose amplitudes favour good assignments by reducing optimization to the decoding of a classical linear code (Jordan et al., Nature 2025). How well DQI does is therefore governed by how well that code can be decoded from the…
Multiplying matrices via polynomials: operational asymptotic spectrum barrierResearch Paper
The exponent of matrix multiplicationωF is the least τ such that n×n matrices over a field F can be multiplied with O(nτ+o(1)) arithmetic operations; equivalently, it measures the growth of the tensor rank of the matrix multiplication tensor ⟨n,n,n⟩. In October 2026 OpenAI announced a proof that …
Precedence-Constrained Decision Trees and CoveringsResearch Paper
In the Optimal Decision Tree problem an unknown target hypothesis h∗ from a finite set H of n hypotheses must be identified by adaptively performing tests from a family T of m tests; each test partitions H and its reply reveals the block that contains h∗. The problem goes back to Garey and Graham (1974) and appears in medical diagnosis, troubleshooting…
Otter: A Provably MEV-Resilient Automated Market Maker via Surplus RedistributionResearch Paper
An automated market maker (AMM) is a smart contract that holds reserves of two tokens X and Y and trades with anyone along a fixed pricing curve. On a blockchain the trades of one block are sequenced by a builder, who may also insert trades of its own. Ordering power yields maximal extractable value (MEV): in a sandwich attack the builder buys before a…
Inside the Critical Window of Random 2-SATResearch Paper
Random 2-SAT is the one case of random k-SAT whose satisfiability threshold and scaling window are both known. With n Boolean variables and m random 2-clauses, a formula is satisfiable with probability tending to one when m/n<1 and unsatisfiable with probability tending to one when m/n>1, a result proved independently by Chvátal and Reed (FOCS 1992), Goerdt…
Better Bounds for Semi-Streaming Maximum Matching via Load BalancingResearch Paper
Graphs too large to store are often processed as a stream: the edges arrive one at a time, in an order nobody controls, and an algorithm may read the stream a few times (passes) while keeping only a small summary in memory. The semi-streaming model of Feigenbaum, Kannan, McGregor, Suri and Zhang (FKM+05) allows O~(n)=O(n⋅polylogn) bits…
Eliminating Ongoing Interaction in Long-Running Verification AgentsResearch Paper
A long-running verification agent completes a chain of tasks, each of which must be submitted exactly, and it can consult a human expert along the way. Every consultation is paid, and every experiment the agent runs on its own tools is paid. A basic design question is whether the expert must stay available throughout the run, answering questions as they…
In online bipartite matching, m offline vertices are known in advance and online vertices arrive one at a time, each revealing its neighbourhood; every arrival must be rejected or irrevocably matched to an unmatched neighbour, and the goal is a large matching. Under adversarial arrivals the Ranking algorithm of Karp, Vazirani and Vazirani is optimal with…