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.
Graphon Colourings and Limits of Graph PartitionsResearch Paper
The Cheeger constant of a graph measures its worst bottleneck: the smallest ratio between the number of edges leaving a vertex set and the volume of that set. It controls the spectral gap of the random walk through the Cheeger–Buser inequalities, and through them mixing times, expansion and the quality of spectral partitioning.
The quantum query complexity of the semigroup product problemResearch Paper
Many quantum query problems are iterated products in disguise. Membership in a regular language reduces to computing the product x1x2⋯xn of input letters in a finite monoid and testing whether it lies in an accepting set. Maximum finding is a product in the monoid (N,max), and finding all distinct letters of an input is a product in the…
How to Round Spiky Balls into Submission; And Faster Algorithms For The Closest Vector ProblemResearch Paper
The Closest Vector Problem asks for the point of a lattice nearest to a given target. It is a central problem of the algorithmic geometry of numbers: integer programming in fixed dimension, lattice-based cryptanalysis and many reductions between lattice problems pass through it. Its complexity depends on the norm. In the Euclidean norm, exact CVP is solved…
Private Information Retrieval from Two Entangled ServersResearch Paper
Private information retrieval (PIR) lets a client read one record of a database without revealing which record. Over one server with classical communication and information-theoretic privacy, the client must essentially download the database; with two non-communicating classical servers, the best known schemes still communicate subpolynomially many but…
Classical Verification of Quantum Computation Beyond the Polynomial HierarchyResearch Paper
A quantum computer that solves a problem outside classical reach raises a practical question: how does a classical party check the answer? Relative to an oracle, Raz and Tal showed that BQP is not contained in PH with the Forrelation problem (STOC 2019), but that separation does not come with a classical proof system. Recursive Fourier…
Matrix Spencer: Eight Standard Deviations Suffice and an Almost-Linear Time Algorithm for Dense InputResearch Paper
Spencer's "six standard deviations suffice" theorem says that every family of n sets on n points has a {−1,1}-coloring of discrepancy at most 6n, while independent random signs lose a factor logn (Spencer 1985). The Matrix Spencer conjecture of Meka asks for the noncommutative form: for symmetric matrices …
Learning Partition Trees for Nearest Neighbor SearchResearch Paper
Nearest neighbor search asks for a data structure on a dataset P⊂Rd of n points that, given a query q, returns a point of P closest to q. In high dimension, worst-case guarantees are known only with a multiplicative approximation to the distance (Andoni, Indyk 2006; Andoni, Laarhoven, Razenshteyn, Waingarten 2017). Practical systems are…
Paths and Intersections: Repelling PairsResearch Paper
The distance realization problem asks, given a metric D on a finite set T of terminals and a family of graphs, whether some graph in the family with nonnegative edge lengths, possibly with extra Steiner vertices, has shortest-path metric exactly D on T. The question goes back to Hakimi and Yau (1965) and appears in phylogenetics, hierarchical classification…
An Improved Streaming Algorithm for Exact Pattern MatchingResearch Paper
Given a pattern P of length m followed by a text T of length n, one character at a time, can an algorithm report each occurrence of P in T as soon as it ends, while remembering very little? Exact Pattern Matching in the streaming model is the basic problem of a large area: it is used as a black box in streaming algorithms for k-mismatch, matching with…
Efficient Proper Agnostic Learning of HalfspacesResearch Paper
Halfspaces, functions of the form h(x)=sign(w⋅x−θ), are among the most basic objects in learning theory. In Valiant's PAC model they are efficiently learnable when the labels are realizable, but in the agnostic model of Kearns, Schapire and Sellie the labels may be arbitrary, and the learner must compete with the best-fitting…
Graph states are multi-qubit stabilizer states indexed by graphs (Hein, Eisert, Briegel, 2004, doi). They are used in measurement-based quantum computation, error correction and secret sharing, so it is useful to measure their entanglement by combinatorial invariants of the underlying graph. Two graph states are equivalent under single-qubit Clifford…
Quantum Approximate Pattern Matching with Wildcards and Weighted Edits: Provable Baselines and Sparse-Defect VerificationResearch Paper
Approximate pattern matching asks whether some substring of a text is close to a pattern under edit operations. For the unit-cost model, quantum algorithms are near optimal: Gibney, Jin, Kociumaka and Thankachan (arXiv:2311.01793) give O~(nk) queries for bounded edit distance, and Kociumaka, Nogler and Wellnitz (arXiv:2410.06808) give…
Sharp Limits of Graph-Based Nearest Neighbor Search on the SphereResearch Paper
Most large-scale approximate nearest-neighbor search systems, such as HNSW, NSG and DiskANN, build a proximity graph on the data and answer a query by greedy navigation: from an entry point, repeatedly move to the listed neighbor closest to the query, and stop when none is closer. Practice has outrun theory here. Laarhoven (2018) analyzed random restarts on…
Maximum-Completion Forests via Sharp Spectral QuantizationResearch Paper
Determinant maximization asks, for a positive semidefinite matrix M and a budget k, for the k indices S maximizing detMS. For a Gram matrix this is the squared volume spanned by the chosen vectors; in a fixed-size determinantal model it is the most likely subset. For general positive semidefinite matrices the best known deterministic polynomial-time…
Efficient Error Amplification for Sorting and Orthogonal VectorsResearch Paper
Derandomizing a circuit classically has two steps: reduce the error below 2−N on N-bit inputs, then fix one good random string non-uniformly. The generic way to reduce the error is to run independent copies and combine their answers, and reaching error 2−k costs a factor k in size. For a problem whose circuits are already close to its conjectured…
An edge ranking of a tree assigns positive integer ranks to its edges so that the path between any two distinct edges of equal rank contains an edge of higher rank. The edge ranking numberer(T) is the least possible maximum rank. This number gives the minimum worst-case number of edge queries needed to locate a target element in a tree, the…
A Near-Optimal Generalized Sorting AlgorithmResearch Paper
Ordinary comparison sorting assumes that any two elements can be compared. In many settings only some comparisons are possible or affordable: in the nuts and bolts problem a nut can only be compared with a bolt, and in pairwise preference or ranking problems only certain pairs are ever presented together. Generalized sorting, introduced by Huang, Kannan and…
Exact Euclidean TSP with Few Interior Points: A Square-Root ExponentResearch Paper
The Euclidean traveling salesman problem asks for a shortest closed tour through n given points of the plane, with costs the true Euclidean distances. It is NP-hard (Papadimitriou, 1977), and the subset dynamic program of Bellman and of Held and Karp (1962) solves it in time exponential in n. De Berg, Bodlaender, Kisfaludi-Bak and Kolay (SICOMP 2023) showed…
Beyond Multi-Index Models: Learning Intersections of Degree-2 PTFsResearch Paper
A polynomial threshold function (PTF) of degree two labels a point x∈Rd by the sign of a quadratic polynomial; an intersection of k of them, f(x)=1{q1(x)≥0,…,qk(x)≥0}, describes regions bounded by k quadrics: ellipsoids, slabs, cones and their intersections. Learning such concepts from examples drawn from the standard Gaussian is a…
A mixing time method for estimating the sample complexity of quantum state discriminationResearch Paper
Quantum state discrimination asks for a measurement that identifies which of n known states was prepared. Its sample complexitykmin(ϵ) is the least number of i.i.d. copies that reaches success probability 1−ϵ. The quantity bounds the cost of tasks in quantum algorithms and quantum learning theory, among them hidden subgroup and hidden…
The Role of Diagonal Lines in Quantum Low-Degree TestingResearch Paper
A low-degree test checks that answers to local questions come from a single global polynomial. Low-degree tests go back to the multilinearity and low-individual-degree tests of Babai, Fortnow and Lund (1991) and became central to the PCP theorem. Against provers who share entanglement the situation changes, because answers to different questions come from…
Tight Bounds for Sublinear Metric Steiner TreeResearch Paper
The metric Steiner tree problem asks for a cheapest tree connecting a prescribed set of terminals in a metric space, possibly through additional points. It is one of Karp's original NP-complete problems, with a best known polynomial-time ratio of ln4+ε≈1.39 (Byrka, Grandoni, Rothvoß, Sanità, J. ACM 2013).
Truthful-in-Expectation Mechanism with Constant Maximin-Share GuaranteeResearch Paper
Dividing indivisible goods among agents with private additive valuations is a basic problem of algorithmic game theory: the agents' reports are the only input, so a rule that rewards misreporting cannot be fair with respect to the true values. A randomized mechanism is truthful in expectation (TIE) if no agent can raise her expected true value by…
On Proximity Gaps for One-Point Algebraic Geometric CodesResearch Paper
Succinct proof systems of the FRI, STIR and WHIR family test whether a committed word lies close to a code. To test many words at once, they combine them with a random challenge: words u0,…,uℓ are replaced by the single word r(z)=∑j=0ℓujzj for a random z. Correlated agreement (CA) is the property that makes this batching sound. If…
Tight Bounds for (1+ϵ)-Approximation for Minimum Spanning Trees in Doubling MetricsResearch Paper
A minimum spanning tree (MST) of a finite metric space (X,d) is a spanning tree of the complete graph on X of least total edge length. Computing it exactly from a distance oracle takes Θ(n2) distance queries even in metrics of constant doubling dimension (Andoni et al., 2014), so the question is how fast a (1+ϵ)-approximate MST, a spanning tree…