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.
A Nearly Linear-Time FPRAS for Counting KnapsackResearch Paper
Given nonnegative integer weights w1,…,wn and a capacity T, the counting knapsack problem (#Knapsack) asks how many subsets of the items fit: the size of the family of feasible subsetsΩ. The problem is the counting version of 0/1 knapsack and, equivalently, counts the points of the Boolean cube below a halfspace, an object studied in learning…
Non-Interactive Cryptography over Noisy Channels from Indistinguishability ObfuscationResearch Paper
A noisy channel produces randomness that no party chose and no party fully observes. Wyner's wiretap channel (Wyner 1975) used this to send a message confidentially without a shared key, and a long line of work showed that noise is a resource for secure computation as well. One-way communication is the setting where this resource matters most: a sender…
Asymptotically Good Quantum Locally Testable CodesResearch Paper
A quantum locally testable code (qLTC) is a quantum error-correcting code whose membership can be checked by measuring a few qubits at a time, with a rejection probability proportional to the distance from the code. Classical locally testable codes underlie the PCP theorem and property testing; their quantum analogue was proposed by Aharonov and Eldar (AE15)…
Lower Bounds for Preprocessing Attacks on Quantum CryptographyResearch Paper
Cryptographic hash functions are analysed in the random oracle model, where the hash is a uniformly random function R that every party may query. An attacker who knows the hash function in advance may spend unbounded time precomputing advice about R before it sees its challenge; security against such preprocessing attacks (non-uniform security) is what…
Stochastic Matching with Polynomial DegreeResearch Paper
The stochastic matching problem of Blum et al. (EC 2015) models matching markets in which the availability of each potential pair is uncertain and can only be learned through a costly query: kidney exchange, where a compatibility test is expensive, online labor markets and online dating. A known graph G=(V,E) is given; each edge is realized independently…
Asymmetry and Complexity of Nondeterministic ComputationsResearch Paper
Meta-complexity studies the computational complexity of computing Kolmogorov complexity itself: how hard is it, given a string x and a threshold s, to decide whether x has a short description? The question connects circuit lower bounds, pseudorandomness, learning and cryptography, and lower bounds for such problems are among the few unconditional lower…
Tight Approximation Bounds for Clock AuctionsResearch Paper
A clock auction serves a feasible set of single-parameter bidders while learning about them only through rising prices. Each bidder faces a weakly increasing sequence of personal prices; she stays while she accepts and leaves for good at her first rejection, and the auction serves a feasible set of the bidders still active. Clock auctions were introduced by…
From Degree Three to Degree Two: Statistical Randomized Encodings for All FunctionsResearch Paper
A randomized encoding of a function f replaces f(x) by a randomized value f^(x;r) from which f(x) can be decoded and which reveals nothing else about x. Encodings are useful when f^ is much simpler than f, and in secure multiparty computation the relevant measure of simplicity is the algebraic degree of f^ over F2, jointly in the input…
Group Action and Spin Representation Lead to a Holant* Complexity Dichotomy on Domain Size 3Research Paper
Counting problems such as counting perfect matchings, edge colourings or weighted graph homomorphisms can all be written as Holant problems: one sums, over all assignments of domain values to the edges of a graph, the product of local constraint functions at the vertices. Complexity theory asks for a dichotomy: a criterion on the constraint functions that…
Optimal Sub-Gaussian Mean Estimation in Low DimensionsResearch Paper
Estimating the mean of a distribution from independent samples is the most basic task in statistics. For Gaussian data the sample mean is optimal: in one dimension, with probability 1−δ its error is at most (1+o(1))σ2log(1/δ)/n, and no estimator does better in the worst case. For heavy-tailed data the sample mean loses this…
Fair and Strategyproof Facility Location in Euclidean SpaceResearch Paper
Strategyproof facility location is a basic problem of approximate mechanism design without money (Procaccia and Tennenholtz 2009). Agents report locations, a mechanism places one facility, and every agent wants the facility close to her true location. A mechanism is strategyproof if no agent can move the facility closer to herself by misreporting. Since the…
Causal Failure Rank Determines Statistical DepthResearch Paper
Many automated workflows must produce a sequence of outputs that are all correct, while verification is noisy and paid for per observation. If a written output turns out to be wrong, it can sometimes be repaired, but only by a repair right that can be used once and fits only some of the outputs. A natural question is how the optimal evidence bill grows as…
Maximum Cardinality Matching in n2+o(1) TimeResearch Paper
Maximum cardinality matching asks for a largest set of pairwise disjoint edges in a graph. It is one of the oldest problems in combinatorial optimization, and general graphs are what distinguish it from bipartite matching and ordinary flow. Two lines of work have stood as the fastest for decades: the O(mn) combinatorial algorithm of Micali and…
Synergies between Proof Complexity and CryptographyResearch Paper
A central question in cryptography is whether problems with the structure of NP∩coNP must be hard if strong cryptography exists. Factoring and discrete logarithm lie in that class, while indistinguishability obfuscation (iO), together with one-way functions, yields much of standard cryptography from an apparently unstructured…
Almost Tight Hardness of Approximation for 0-ExtensionResearch Paper
In 0-Extension, introduced by Karzanov (1998), a graph with nonnegative edge weights and k terminals carrying a metric must be retracted onto its terminals at minimum total cost. The problem combines the terminal constraints of Multiway Cut with the metric edge costs of Metric Labeling, and it is connected to Lipschitz extension, metric embeddings and…
A Unified and Simplified Framework for Dynamic Distance-Based Graph ProblemsResearch Paper
Distance problems on graphs that change over time sit behind many algorithms for flows, cuts and routing. A data structure that answers approximate distance queries while edges are deleted can replace repeated shortest-path computations inside iterative methods. Deterministic structures are of special interest, since they withstand an adaptive adversary by…
A Near-Optimal Space Lower Bound for Euclidean Diameter Estimation in Dynamic StreamsResearch Paper
A massive set of points in high-dimensional Euclidean space arrives as a sequence of insertions and deletions, and a small-memory algorithm must estimate how far apart the two farthest surviving points are. This is one of the basic questions of geometric streaming, a model introduced by Indyk (STOC 2004), in which the data is a dynamic multiset rather than…
Path Decompositions of Sparse Graphs via Gaussian Sweeps and Faster Exponential AlgorithmsResearch Paper
How large can the pathwidth of a sparse graph be? For graphs of maximum degree 3 the question matters in two places. Structurally, pathwidth, bisection width and cutwidth of such graphs are tied together by classical relations, so an upper bound on one transfers to the others. Algorithmically, many exact exponential algorithms for sparse instances run a…
Optimal Online Joint Replenishment with Linear DelaysResearch Paper
The joint replenishment problem (JRP) is a classical model from inventory theory and one of the basic models of online algorithms with delay. A retailer buys several commodities from one supplier in response to customer demand: combining purchases into one shipment saves delivery cost, but waiting to combine them delays customers. The same trade-off appears…
Solving One of Many Instances Is Almost as Hard as Solving OneResearch Paper
A direct-sum theorem says that solving many independent instances of a communication problem costs proportionally more than solving one (Feder, Kushilevitz, Naor, Nisan 1995; Karchmer, Raz, Wigderson 1995). A strong direct-sum theorem would imply something weaker and still informative: solving one of k instances is almost as hard as solving a single…
Streaming Graph Colouring Meets Molloy–Reed via KernelizationResearch Paper
Brooks' theorem says that a connected graph of maximum degree Δ other than a clique or an odd cycle has a proper Δ-colouring, and Molloy and Reed showed that, for large Δ and k below a threshold of order Δ, the failure of (Δ−k)-colourability is witnessed by a small subgraph. In the streaming model the edges of the graph arrive…
Trading Time, Space, and Alternations: General Plasticity for Algorithms from Hardness of Range AvoidanceResearch Paper
Whether polynomial time can be simulated in small space is one of the central questions of complexity theory. A simulation of P in space nγ for every γ>0 would imply P=PSPACE by the space hierarchy theorem. Williams gave an unconditional simulation of time T in space about T (Wil25), and asking for much less…
A randomized algorithm that runs in time T and uses T random bits usually errs on some fraction of its random strings. Derandomization asks for a deterministic algorithm with the same answers, and fine-grained derandomization asks that the deterministic algorithm be almost as fast, in time T1+O(ϵ) rather than poly(T). Without a generic…
Brooks' theorem (Brooks 1941) says that a connected graph of maximum degree Δ can be properly colored with Δ colors unless it is a clique KΔ+1 or an odd cycle. For Δ≥3 the only obstruction is KΔ+1, and the theorem is tight: Δ colors is one fewer than the greedy bound Δ+1.
Resolving the Worst-Case Complexity of Linear Secret SharingResearch Paper
A secret-sharing scheme lets a dealer split a secret among n parties so that every authorized coalition can recover it, while every other coalition learns nothing about it. Since Shamir and Blakley introduced threshold schemes in 1979, and Ito, Saito and Nishizeki showed in 1987 that every monotone family of coalitions can be realized, the central…