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.
Minimizing Key Schedules for Key-Alternating CiphersResearch Paper
A key-alternating cipher (KAC) encrypts a block m of a finite abelian group G by alternately adding round keys and applying fixed public permutations: x0=k0−m, xj=kj−πj(xj−1). Its provable security in the random permutation model is well understood when the t+1 round keys are independent and uniform (Hoang–Tessaro 2016), but real ciphers derive…
The Information-Theoretic Limits of Hiding Among Decoys in the Shuffle ModelResearch Paper
Hiding a genuine secret among plausible decoys is a recurring pattern in security and privacy. A honeyword system stores a user's real password together with n−1 fake ones and raises an alarm when a fake one is used (Juels–Rivest 2013). A computationally unbounded adversary who decrypts a ciphertext under every key of a small key space obtains one genuine…
A Circuit Complexity Trichotomy For Regular LanguagesResearch Paper
Unbounded fan-in Boolean circuits are the standard model of parallel computation, and finite automata the standard model of sequential computation with constant memory. Regular languages sit where the two meet: they separate AC0 from NC1 (Furst, Saxe, Sipser 1984), any separation of ACC0 or TC0 from NC1 is…
Optimal Approximation for Constrained Correlation Clustering via RepulsionResearch Paper
Correlation clustering groups vertices when pairwise preferences can conflict: a positive pair prefers one cluster, and a negative pair prefers different clusters. The number of clusters is unrestricted. Must-links and cannot-links add requirements that every returned partition must satisfy. This distinction matters when a preference can be traded against…
Tight Variable-Occurrence Bounds and Exponential Separations for Moser–Tardos and WalkSAT on 3-CNFResearch Paper
WalkSAT and the Moser–Tardos algorithm (MT) are the two standard clause-driven local-repair procedures for satisfiability. Both keep a complete assignment and repeatedly pick an unsatisfied clause. WalkSAT flips one variable of it (Papadimitriou 1991, Schöning 1999); MT resamples all of its variables with fresh random bits, which is the algorithmic form of…
A multiplication table describes a binary operation on a finite labelled set. Reading the whole table requires quadratically many entries. Property testing instead asks for a decision from substantially fewer entries: accept a genuine group and reject an operation that requires many changes to become any group. This question concerns algorithms that receive…
A classical polynomial-time verifier interacting with an unrestricted prover can check every polynomial-time quantum computation: BQP⊆PSPACE=IP, the equality being Shamir's theorem. Whether this containment survives relative to an arbitrary oracle decides whether it can be proved by relativizing techniques. Bouland, Huang,…
Lotteries Protect Single-Item Sellers from Monopolist IntermediariesResearch Paper
A publisher can own an advertising impression while an exchange controls which advertiser reaches the publisher. A blockchain application can face a similar separation between the party selling an opportunity and the party selecting participating users. In such settings, optimizing an auction for direct interaction with buyers does not settle the seller's…
A Universal Threshold Theory for Local Properties of Random Linear CodesResearch Paper
A linear code stores messages as vectors in a finite-dimensional vector space. Its dimension controls how many messages it can represent, while its other properties determine what kinds of corruption or ambiguity it can tolerate. Researchers studying random codes therefore ask at which dimensions a given property becomes likely. For many properties, a small…
The Computational Complexity of Concurrent Stochastic Games: Exact Value and ApproximationResearch Paper
A concurrent stochastic game (CSG) is played by two players on a finite graph of states. At every stage both players choose an action simultaneously and independently, and the pair of actions together with the current state determines a probability distribution over the next state. CSGs are the standard model of two-agent interaction under uncertainty with…
Competitive Random-Order Correlation k-ClusteringResearch Paper
Correlation clustering groups objects using only pairwise similarity judgements. Each pair is labelled positive or negative, and a clustering pays for positive pairs separated into different groups and negative pairs placed together. This objective is useful when similarities are qualitative and need not come from distances. Limiting the number of groups…
Wait-Free Solvability of General Tasks and a New Proof of the Renaming DichotomyResearch Paper
A distributed program must produce compatible outputs even though each process sees only its own input and the shared memory it has read. Some processes may stop permanently. A wait-free program guarantees that each process that continues taking steps decides after finitely many of its own steps, regardless of the behavior of the others. A solvability…
Random Deletion for Circuits in Regular MatroidsResearch Paper
Karger's random contraction algorithm ([Kar93], [Kar95]) showed that a graph with minimum cut weight λ has at most n2α cuts of weight at most αλ. Through matroid duality, cuts of a graph are the circuits of its cographic matroid and cycles are the circuits of its graphic matroid, and Subramanian ([Sub95]) proved the analogous bound …
The Complexity of Distributed Minimum Weight Cycle ApproximationResearch Paper
A network can have inexpensive routes between many pairs of devices while its cheapest round trip remains difficult to identify. A minimum weight cycle is a simple closed route of minimum total edge weight. Finding one is a basic graph optimization problem related to shortest paths. In a distributed network the graph also determines which devices can…
Matrix sensing meets property testing: Sample-optimal testing for low rankResearch Paper
A low-rank matrix represents a linear transformation whose output lies in a small-dimensional subspace. Matrix sensing uses random linear measurements to recover such a transformation. Recovery assumes that the target has low rank; a property test instead checks that assumption, distinguishing a matrix with rank at most a specified integer from one…
Sybil-Proofness of Generalized Adaptive Clinching and Implications for Blockchain Mechanism DesignResearch Paper
An automated market maker (AMM) is a pool of two tokens X and Y that trades against users along a fixed reserve curvey=φ(x). On a blockchain, orders are collected into a batch by a block builder, and the batch is then executed against the pool. Executing orders one at a time in builder-chosen order exposes users to front-running and sandwich attacks.…
Rapid mixing of Gibbs samplers via quantum Dobrushin–Shlosman conditionsResearch Paper
Preparing the Gibbs stateσβ=e−βH/Tre−βH of a quantum many-body Hamiltonian is a basic task of quantum simulation: it gives access to thermal expectation values, and it is the quantum analogue of Markov chain Monte Carlo. A quantum Gibbs sampler is a continuous-time quantum Markov dynamics etL whose unique…
Parameterized Tractability of Euclidean k-Steiner TreeResearch Paper
A Steiner tree connects a set of terminals by a network of minimum total length, possibly through auxiliary Steiner points. In the discrete Euclidean variant the Steiner points must be chosen from a finite candidate set given in the input, and in the k-Steiner variant at most k of them may be used, while the number of terminals is unrestricted. Exact…
Distributed LTL Synthesis under Arbitrary Message AdversariesResearch Paper
Reactive synthesis asks for a program whose outputs satisfy a logical specification against every input stream. For a single process and specifications in linear temporal logic (LTL) it is decidable (Pnueli–Rosner 1989); for several processes with partial information it is undecidable in general (Pnueli–Rosner 1990), and decidable cases rely on a hierarchy…
Santa Claus and Weighted Nash Social Welfare with Subadditive ValuationsResearch Paper
In max-min allocation, also called the Santa Claus problem, n agents share m indivisible items and the aim is to make the worst-off agent as well off as possible. It is the egalitarian counterpart of welfare maximization and a basic model of fair division; with identical valuations its optimum is the maximin share of the agents. The problem is NP-hard even…
For compact convex sets K1,…,Km⊆Rn, Minkowski showed that the volume of a weighted Minkowski sum is a homogeneous polynomial of degree n in the weights,
The log log jam in Gaussian state tomographyResearch Paper
A Gaussian state of n bosonic modes (light in an optical fibre, a microwave cavity, a mechanical oscillator) is fixed by a mean vector and a covariance matrix, so it looks like a finite-dimensional object to learn. Yet the best known procedures for Gaussian state tomography use O(nloglogE+poly(n)/ε2) copies, where E is the mean energy…
RARE: Response-Aware Rational Equilibrium in Budget-Constrained Pricing GamesResearch Paper
Sellers of digital and physical goods set prices in competition for the same pool of buyer money. When buyers have hard budgets rather than quasilinear utilities, the sellers' revenues are coupled through those budgets: a price change by one seller moves money to or from every other seller. The textbook equilibrium notion for such a pricing game is the Nash…
Proper Agnostic Learning of Two Balanced Product Distributions from Prefix-Conditional SamplesResearch Paper
Mixtures of product distributions on the Boolean cube are a basic model of latent structure: each sample comes from one of a few hidden populations, and within a population the coordinates are independent. Learning such mixtures from ordinary samples is hard in general. Learning two-component mixtures, for example, requires assumptions on the component…
Memory–Sample Tradeoffs in High–Dimensional StatisticsResearch Paper
Many high-dimensional estimation and testing problems show a gap between the number of samples that suffices information-theoretically and the number that efficient algorithms seem to need. Statistical-query (SQ) lower bounds are one standard way to show such gaps. A central example is Non-Gaussian Component Analysis (NGCA): distinguish a standard Gaussian…