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.
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…
Lower Bounds for Memory-Efficient Differentially Private Continual CountingResearch Paper
Differentially private training of machine-learning models repeatedly releases noisy prefix sums of gradients. The mechanism with the best known accuracy for this task is the matrix mechanism: factor the prefix-sum matrix An as An=BC, and release B(Cx+z)=Anx+Bz for Gaussian noise z. Fichtenberger, Henzinger and Upadhyay gave a lower-triangular Toeplitz sq…
On the optimality of truncation among binary linear sketchesResearch Paper
A binary linear sketch compresses a binary vector by reporting parity measurements: each output bit is the sum modulo two of selected input coordinates. Such sketches support distributed computation because parity measurements of a sum can be obtained by adding the separate measurements. When two terminals observe correlated data, however, preserving this…
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…
Tight Bounds for Tusnády's Problem in the PlaneResearch Paper
A coloring assigns each point one of two signs, interpreted as membership in two groups. For a region of the plane, its imbalance is the absolute difference between the numbers of points of the two signs inside it. Small imbalance simultaneously over many regions is a basic objective of geometric discrepancy theory. Axis-parallel rectangles are a natural…
Monotone circuit lower bounds from spread matchingsResearch Paper
A monotone Boolean circuit computes with AND and OR gates only. Exponential lower bounds for such circuits are a long line of unconditional results in circuit complexity, and matching resisted improvement for decades. Razborov proved in 1985 that computing matching requires monotone circuits of size nΩ(logn). That bound stood until Cavalar, Göös,…
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…
Optimal Conversion from Zero-Concentrated to Gaussian Differential PrivacyResearch Paper
Differential privacy is stated in several incompatible currencies. Zero-concentrated differential privacy (zCDP), introduced by Bun and Steinke (2016), bounds Rényi divergences between the output laws on neighbouring datasets; it composes additively and is used in deployed systems, including the 2020 U.S. Census TopDown algorithm. Gaussian differential…
Hamiltonicity of mildly pseudorandom regular graphsResearch Paper
An (n,d,λ)-graph is an n-vertex d-regular graph whose adjacency matrix has all non-trivial eigenvalues of absolute value at most λ. The smaller λ is compared to d, the more the graph resembles a random one. Whether such a graph has a Hamilton cycle, a cycle through every vertex, is a central question on pseudorandom graphs. Krivelevich and…
Online Multi-Level Aggregation with Maximum DelayResearch Paper
Requests for a shared service often arrive at different times and locations. Combining them can save the cost of the resources they share, while waiting to combine them makes the oldest request wait longer. Multi-Level Aggregation with Maximum Delay studies this tradeoff when the resources form a tree and each service pays for its longest wait. The…
A program can describe an infinite set by printing its elements indefinitely. This makes description length meaningful even when no finite output string contains the whole object. Researchers in computability and algorithmic information theory ask how much shorter such a description can become when the program receives random bits. The relevant success…
Associativity of Multiplication Is Hard for ResolutionResearch Paper
SAT and SMT solvers handle bit-vector arithmetic by bit-blasting: every bit becomes a Boolean variable and every multiplication a multiplier circuit, encoded as a CNF formula. Formulas that require reasoning about multiplication remain a known weak point of this approach in bounded model checking, arithmetic hardware verification and the verification of…
Metric Facility Location under Batched Random OrderResearch Paper
Online metric facility location was introduced by Meyerson [Mey01]: clients of a metric space arrive one at a time, each must be connected irrevocably to an open facility on arrival, opening a facility at a permitted site y costs f(y), and connecting a client costs its distance. The arrival order decides what can be guaranteed. Under a uniformly random…