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.
The Metacomplexity Structure of Search ProblemsResearch Paper
Metacomplexity studies the complexity of computational tasks that are themselves about computation: compressing strings, estimating circuit complexity, or refuting a claimed algorithm by finding an input on which it fails. Refutation tasks appear in learning theory, in hardness magnification, in derandomization and in bounded arithmetic. A refutation task…
Single-Sample Prophet Inequalities: A Combinatorial to Single-Item ReductionResearch Paper
In an online allocation problem, buyers arrive one at a time and each must be served irrevocably on arrival; the benchmark is the prophet, who sees all valuations in advance and allocates optimally. When the valuations are random with known distributions, guarantees of this kind are prophet inequalities. A much weaker information model gives the algorithm…
Optimal Early-Stopping Broadcast via Exponential Information GatheringResearch Paper
A Byzantine broadcast protocol lets a designated sender distribute an input despite parties that can lie, omit messages or send different reports to different recipients. Honest parties must eventually output a common value, and that value must equal the sender’s input when the sender is honest. These requirements give distributed protocols a common value…
From Oblivious to Adaptive Adversaries: Black-Box Reductions for Monotone Dynamic Problems with Applications to Cuts, Distances, and ClusteringResearch Paper
A randomized dynamic graph algorithm receives updates and maintains an answer after each one. An oblivious adversary commits to its update sequence independently of the algorithm's randomness. An adaptive adversary can choose the next update after inspecting earlier published answers. A guarantee for every fixed sequence does not automatically cover…
Identifying Minimax Payoffs from Bounded InterventionsResearch Paper
A service choosing a randomized action to minimize its largest group loss solves a finite minimax problem. A user who can change row priorities and action prices can observe a sequence of such decisions without seeing the underlying losses. The identification question is whether those observations determine the payoff table. It matters for interpreting what…
Constant-Time Range Counting for Pattern-Avoiding Permutations and Entry Access to Twin-Ordered MatricesResearch Paper
Given a permutation τ of [n]={1,…,n}, a dominance query(x,y) asks how many of the first x values of τ are at most y. Together with rectangle queries (four dominance counts by inclusion–exclusion), it is the basic primitive of two-dimensional orthogonal range counting in rank space, and it underlies succinct text indexes and compressed matrix…
Seed Recycling: Explicit Codes for Mixed Synchronization Errors Matching the Leading Term of the Gilbert–Varshamov BoundResearch Paper
A stored or transmitted bit string can lose symbols, gain symbols, or change their order. Such synchronization errors disrupt the alignment between the original and received strings. A decoder therefore has to identify the original message while also resolving where its symbols moved. The paper studies a fixed number of errors as the block length grows,…
Exponential Quantum Advantage in Number-on-Forehead CommunicationResearch Paper
A communication problem distributes an input among several participants and asks how many bits they must exchange to compute an answer. In the number-on-forehead model, each participant sees every input block except their own. With three participants, these views overlap substantially: a fact hidden from one participant is visible to the other two. Lower…
Work-Efficient Parallel Rounding: Product ObjectivesResearch Paper
Randomized rounding often certifies a collection of requirements by assigning a nonnegative penalty to each failure and bounding their total expectation. When the coordinates are independent, exponential penalties for linear sums factor into products of functions of individual coordinates. Preserving the sum of these product expectations therefore provides…
An Efficient 1/4-Competitive Prophet Inequality for Subadditive Combinatorial AllocationsResearch Paper
A seller with several distinct items must often decide whom to serve before knowing the demand of later buyers. Waiting for every valuation would permit a welfare maximizing allocation in hindsight, but an online allocation must commit items as buyers arrive. This creates a quantitative question: how much welfare can a causal algorithm preserve when it…
Testing Fourier Sparsity Near OptimallyResearch Paper
A Boolean function f:F2n→{−1,+1} is s-Fourier-sparse when at most s of its Fourier coefficients are nonzero. Sparse functions include parities and k-juntas (which have at most 2k nonzero coefficients), so sparsity is one of the basic "concise representation" classes of learning theory and property testing. A tester for this class reads f at a…
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…
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…