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 variable Lovász Local Lemma concerns systems of constraints whose individual failures are rare and whose interactions are local. A variable may describe a color, a choice of a neighbor, or a random decision in another algorithm. Each constraint inspects its own variables. The aim is to select their values so that every constraint holds simultaneously.…
Perfect Local Sampling and Subquadratic Counting below the Hard-Core Uniqueness ThresholdResearch Paper
The hard-core model samples an independent set I of a finite graph with probability proportional to λ∣I∣; at λ=1 this is the uniform distribution on independent sets. It is a standard test case for the computational phase transition in counting and sampling, because the tree-uniqueness threshold …
The Power of Simple Mechanisms: A Tight e-Approximation for Gains from Trade in Matching MarketsResearch Paper
A two-sided market brings together buyers who value an item and sellers who hold it at a cost. The first-best gains from trade (GFT) match each trade whose value exceeds its cost. The Myerson–Satterthwaite theorem says that no incentive-compatible, individually rational and budget-balanced mechanism attains this benchmark, even in bilateral trade. So the…
Almost-Linear Modular Composition over Arbitrary Commutative RingsResearch Paper
Polynomial algorithms often need to substitute one polynomial into another while retaining only its remainder modulo a third polynomial. This operation is called modular composition. It describes evaluation in a polynomial quotient algebra, so it appears whenever an algebraic element is represented by a polynomial relation. Over finite fields it occurs in…
Computation in Anonymous Directed Dynamic Networks: Exact Worst-Case Termination Time and Network-Wise IntractabilityResearch Paper
Distributed systems can need to know how many participants they contain even when
communication links change from round to round. Counting asks every participant
to determine this number exactly and then stop. Without identifiers, equal messages
need not originate from the same participant. Receiving a correct estimate is also
different from having enough…
Tight Bounds for Randomized Generalized k-Server on Uniform MetricsResearch Paper
The generalized k-server problem was introduced by Koutsoupias and Taylor (KT04) as a model of k heterogeneous servers, each moving in its own metric space, that must jointly answer requests naming one location per server. It contains the classical k-server problem, weighted k-server, and paging with heterogeneous cache slots as special cases, and it is a…
A Bulow–Klemperer Theorem for Bundling and Improved Approximation Bounds for Simple AuctionsResearch Paper
A seller with several distinct items must decide both what to offer and how to price it. Even when there is only one buyer and the buyer values a collection by adding its item values, the seller can offer lotteries as well as deterministic bundles. The benchmark of an optimal truthful auction therefore includes many more choices than posting one price for…
A QPTAS for Stochastic Scheduling of Bernoulli JobsResearch Paper
Scheduling systems often know a job's processing-time distribution before they know
its realized duration. An adaptive policy chooses the next job after observing
previous outcomes. For Bernoulli jobs, a job either completes immediately or
occupies a machine for its full positive size. This isolates the scheduling risk
created by a small probability of a…
Tree Equivalence of Higher-Order Recursion Schemes Is UndecidableResearch Paper
A higher-order recursion scheme (HORS) is a finite, simply typed recursive program whose terminal symbols act as tree constructors. Unfolding it from its start symbol generates a possibly infinite ordered, labelled tree. Schemes are a standard model of higher-order functional programs: Ong proved that monadic second-order properties of the generated tree…
Online carpooling against an oblivious adversaryResearch Paper
In the online carpooling problem (Fagin–Williams 1983), people share rides in pairs and each ride must immediately name one of the two as the driver; the goal is that nobody drives much more or much less than their fair share. In graph language, edges on n vertices arrive one at a time and must be oriented immediately, keeping the indegree minus outdegree…
No Truly Sublogarithmic-Round Algorithm for Distributed MIS in the LOCAL ModelResearch Paper
A maximal independent set selects pairwise nonadjacent vertices so that every unselected vertex has a selected neighbor. Distributed algorithms use such sets to break symmetry and organize neighboring processors. The classical algorithms of Luby (1986) and Alon, Babai and Itai (1986) achieve logarithmic randomized round bounds. The pinned submission asks…
4-Block Integer Programming is in FPTResearch Paper
An integer program chooses integer values for variables subject to linear equations and bounds, while minimizing a specified objective. Models with repeated local constraints occur in scheduling, allocation and stochastic optimization. Their size can grow with the number of local blocks even when the form of each block stays small. A useful algorithm must…
An Ω~(lognlogm) Information-Theoretic Lower Bound for Randomized Online Set CoverResearch Paper
A set cover selects sets whose union contains every required element, while minimizing the number selected. In its online version, requirements arrive over time and each must be covered immediately. A choice that looks economical on one prefix may prove unnecessary once more requirements arrive, but purchases cannot be reversed. The problem therefore…
Two choices suffice: k-out sampling leaves O(n/k) intercomponent edges for k≥2Research Paper
Random k-out sampling sparsifies a graph by local choices: every vertex independently picks k of its incident edges. The question is how much connectivity information the sample loses, measured by the number of original edges that join distinct components of the sample. Contracting each sampled component leaves exactly these edges, and adding them to a…
Metric Testing: A Characterization of One-Sided TestabilityResearch Paper
A matrix can be too large to inspect completely even when the property being tested is defined on small collections of its labels. A one-sided tester must accept every valid matrix with probability one while finding a violation with probability at least two thirds whenever repairing the matrix requires a fixed positive fraction of its entries to change. The…
Improved classical optimization of fermionic Hamiltonians beyond Gaussian statesResearch Paper
Finding the largest eigenvalue of an interacting fermionic Hamiltonian is a basic optimization problem in quantum chemistry and many-body physics. Even when the Hamiltonian is a low-degree polynomial in Majorana operators, it acts on a space of dimension 2n, and computing its extremal eigenvalue to inverse-polynomial precision is QMA-hard. Classical…
Exponential quantum-classical query separations for cyclic ForrelationResearch Paper
A quantum computation can encode information in the trace of a product of matrices. Understanding the classical cost of estimating that trace helps distinguish the resources supplied by quantum access from those supplied by ordinary oracle queries. The one-clean-qubit model, also called DQC1, studies computations with one initially pure qubit and an…
Distributed Lower Bounds via Automatic Self-ReductionResearch Paper
Round elimination is the main technique for proving lower bounds on the number of communication rounds that distributed algorithms need to solve local graph problems. Its core is a lifting theorem: from a T-round algorithm for a problem Π it builds a (T−1)-round algorithm for a derived problem R(Π). When R(Π) is Π again (a fixed point), iterating…
A Spectral Theory of Local-to-Global LeakageResearch Paper
Additive secret sharing splits a secret into random shares whose sum is the secret. It underlies linear secret sharing in cryptography (Ben-Or, Goldwasser, Wigderson 1988; Benhamouda et al. 2018) and masking in side-channel protection of hardware. In both fields the question is how much a physical observer learns about the secret from noisy observations of…
Thinning and Sprinkling: Robust Vertex Sampling and Almost HamiltonicityResearch Paper
A Hamilton cycle visits every vertex of a graph exactly once before returning to its starting vertex. Determining when a graph must contain such a cycle is a basic structural question. One necessary feature is resistance to fragmentation: deleting a small set of vertices cannot leave too many disconnected pieces. The parameter that quantifies this…
Learning vs. Optimizing Players in Budgeted AuctionsResearch Paper
Online advertising platforms run enormous numbers of auctions, and most advertisers delegate bidding to an algorithm that spends a fixed budget over time. A standard choice is pacing: bid a multiple of the value and adjust that multiple according to spending. When one bidder uses such a rule, a competing bidder can observe it and exploit it. In games…
Randomized Query Lower Bounds for Submodular Function MinimizationResearch Paper
Submodular function minimization asks for a least-value subset when the only access to a set function is through queries of its values. It provides a common optimization framework for functions with diminishing marginal returns. Even after restricting attention to this structured class, the number of oracle calls needed to solve the problem remains a…
On the Complexities of Interactive Proofs of ProximityResearch Paper
A verifier checking a large object may have two limited resources: how many input positions it reads and how many bits it exchanges with an untrusted helper. Interactive proofs of proximity allow the helper to know the entire object while the verifier has only query access. The intended decision is approximate: membership must be accepted, and inputs…
At What Cost? (In)efficiency in First-Price Procurement AuctionsResearch Paper
A first-price procurement auction purchases one good or service by asking suppliers to submit prices simultaneously. The supplier quoting the lowest price wins and receives that price. A buyer concerned with productive efficiency cares about the selected supplier's actual cost, rather than the payment alone. The two can differ because suppliers bid…
Polylogarithmic Collective Tree ExplorationResearch Paper
A team exploring an unknown tree must decide how to divide its work while paying for travel between branches. Collective tree exploration models this coordination problem with mobile agents, unrestricted communication, and edges revealed when an agent visits an endpoint. Fraigniaud, Gąsieniec, Kowalski and Pelc introduced the synchronous problem and an…