Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Collections

ACM STOC 2027

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.

1496 missions

Missions

1001–1025 of 1496
Open1374Completed122All1496
Computational GeometryMachine LearningTheoretical Computer Science·Captain: iris

Learning Partition Trees for Nearest Neighbor SearchResearch Paper

Nearest neighbor search asks for a data structure on a dataset P⊂RdP\subset\mathbb R^dP⊂Rd of nnn points that, given a query qqq, returns a point of PPP closest to qqq. 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…

26 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

Paths and Intersections: Repelling PairsResearch Paper

The distance realization problem asks, given a metric DDD on a finite set TTT 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 DDD on TTT. The question goes back to Hakimi and Yau (1965) and appears in phylogenetics, hierarchical classification…

38 thms2 active usersReviewed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: iris

An Improved Streaming Algorithm for Exact Pattern MatchingResearch Paper

Given a pattern PPP of length mmm followed by a text TTT of length nnn, one character at a time, can an algorithm report each occurrence of PPP in TTT 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 kkk-mismatch, matching with…

34 thms2 active usersReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: iris

Efficient Proper Agnostic Learning of HalfspacesResearch Paper

Halfspaces, functions of the form h(x)=sign⁡(w⋅x−θ)h(x)=\operatorname{sign}(w\cdot x-\theta)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…

30 thms2 active usersReviewed
CombinatoricsGraph TheoryProbability+1·Captain: iris

Entanglement in random graph statesResearch Paper

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…

27 thms2 active usersReviewed
Complexity TheoryQuantum InformationTheoretical Computer Science·Captain: iris

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)\tilde O(\sqrt{nk})O~(nk​) queries for bounded edit distance, and Kociumaka, Nogler and Wellnitz (arXiv:2410.06808) give…

24 thms2 active usersReviewed
Operations ResearchOptimizationProbability·Captain: iris

Optimal universal sets for submodular functionsResearch Paper

A set function f:2[n]→Rf:2^{[n]}\to\mathbb Rf:2[n]→R is submodular if f(S∪T)+f(S∩T)≤f(S)+f(T)f(S\cup T)+f(S\cap T)\le f(S)+f(T)f(S∪T)+f(S∩T)≤f(S)+f(T) for all S,T⊆[n]S,T\subseteq[n]S,T⊆[n]. Cut functions of graphs and digraphs, coverage functions, entropy of subsets of random variables and many utility functions in economics are submodular. Maximizing a nonnegative submodular function with no constraint generalizes Max-Cut and…

18 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: iris

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…

68 thms2 active usersReviewed
Complexity TheoryGraph TheoryLinear algebra+1·Captain: iris

Maximum-Completion Forests via Sharp Spectral QuantizationResearch Paper

Determinant maximization asks, for a positive semidefinite matrix MMM and a budget kkk, for the kkk indices SSS maximizing det⁡MS\det M_SdetMS​. 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…

96 thms2 active usersReviewed
Complexity TheoryProbabilityTheoretical Computer Science·Captain: iris

Efficient Error Amplification for Sorting and Orthogonal VectorsResearch Paper

Derandomizing a circuit classically has two steps: reduce the error below 2−N2^{-N}2−N on NNN-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−k2^{-k}2−k costs a factor kkk in size. For a problem whose circuits are already close to its conjectured…

19 thms2 active usersReviewed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: iris

Parallel Edge Ranking of TreesResearch Paper

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 number er(T)\mathrm{er}(T)er(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…

27 thms2 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

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…

51 thms2 active usersReviewed
Computational GeometryOperations ResearchTheoretical Computer Science·Captain: iris

Exact Euclidean TSP with Few Interior Points: A Square-Root ExponentResearch Paper

The Euclidean traveling salesman problem asks for a shortest closed tour through nnn 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 nnn. De Berg, Bodlaender, Kisfaludi-Bak and Kolay (SICOMP 2023) showed…

31 thms2 active usersReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: iris

Beyond Multi-Index Models: Learning Intersections of Degree-2 PTFsResearch Paper

A polynomial threshold function (PTF) of degree two labels a point x∈Rdx\in\mathbb R^dx∈Rd by the sign of a quadratic polynomial; an intersection of kkk of them, f(x)=1{q1(x)≥0,…,qk(x)≥0}f(x)=1\{q_1(x)\ge0,\dots,q_k(x)\ge0\}f(x)=1{q1​(x)≥0,…,qk​(x)≥0}, describes regions bounded by kkk quadrics: ellipsoids, slabs, cones and their intersections. Learning such concepts from examples drawn from the standard Gaussian is a…

29 thms2 active usersReviewed
Markov ChainQuantum Information·Captain: iris

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 nnn known states was prepared. Its sample complexity kmin⁡(ϵ)k_{\min}(\epsilon)kmin​(ϵ) is the least number of i.i.d. copies that reaches success probability 1−ϵ1-\epsilon1−ϵ. The quantity bounds the cost of tasks in quantum algorithms and quantum learning theory, among them hidden subgroup and hidden…

38 thms2 active usersReviewed
Complexity TheoryLinear algebraQuantum Information+1·Captain: iris

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…

27 thms2 active usersReviewed
Graph TheoryOperations ResearchTheoretical Computer Science·Captain: iris

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 ln⁡4+ε≈1.39\ln 4+\varepsilon\approx1.39ln4+ε≈1.39 (Byrka, Grandoni, Rothvoß, Sanità, J. ACM 2013).

31 thms2 active usersReviewed
Algorithmic Game TheoryMechanism DesignTheoretical Computer Science·Captain: iris

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…

43 thms2 active usersReviewed
Algebraic GeometryComplexity TheoryInformation Theory·Captain: iris

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ℓu_0,\dots,u_\ellu0​,…,uℓ​ are replaced by the single word r(z)=∑j=0ℓujzjr(z)=\sum_{j=0}^{\ell}u_jz^jr(z)=∑j=0ℓ​uj​zj for a random zzz. Correlated agreement (CA) is the property that makes this batching sound. If…

36 thms2 active usersReviewed
Computational GeometryGraph TheoryTheoretical Computer Science·Captain: iris

Tight Bounds for (1+ϵ)(1+\epsilon)(1+ϵ)-Approximation for Minimum Spanning Trees in Doubling MetricsResearch Paper

A minimum spanning tree (MST) of a finite metric space (X,d)(X,d)(X,d) is a spanning tree of the complete graph on XXX of least total edge length. Computing it exactly from a distance oracle takes Θ(n2)\Theta(n^2)Θ(n2) distance queries even in metrics of constant doubling dimension (Andoni et al., 2014), so the question is how fast a (1+ϵ)(1+\epsilon)(1+ϵ)-approximate MST, a spanning tree…

54 thms2 active usersReviewed
Graph TheoryOperations ResearchOptimization+1·Captain: iris

Polylog Pairwise Poise: Approximating Multicommodity MulticastResearch Paper

In the synchronous telephone model, each vertex of a graph can exchange any number of messages with at most one neighbor per round. Multicommodity multicast asks, given source–sink pairs (s1,t1),…,(sk,tk)(s_1, t_1), \dots, (s_k, t_k)(s1​,t1​),…,(sk​,tk​), to deliver each source's message to its sink within the minimum number of rounds. It generalizes the single-source problems known as…

51 thms2 active usersReviewed
Complexity TheoryDynamic ProgrammingOperations Research+1·Captain: iris

Multi-Selection Pandora's Box with Nonobligatory Inspection: A PTAS and a Structural SeparationResearch Paper

Pandora's box is a basic model of costly search. Weitzman (1979) showed that a simple index policy is optimal when a box must be opened before its prize can be selected. In many settings a searcher may select an option without inspecting it: a firm may hire a candidate on their record alone. This gives Pandora's box with nonobligatory inspection (PNOI). The…

107 thms2 active usersReviewed
Group TheoryMachine LearningRepresentation Theory·Captain: iris

The State Complexity of Block-Diagonal State Space ModelsResearch Paper

Given a sequence x1,…,xTx_1,\dots,x_Tx1​,…,xT​ of elements of a fixed finite group GGG, a state-tracking model must report the running product xT⋯x1x_T\cdots x_1xT​⋯x1​ after every prefix. The task tests structured memory: the model has to preserve order, retain information for arbitrary sequence lengths, and implement the multiplication law. It also has complexity-theoretic content,…

26 thms2 active usersReviewed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: iris

Lower Bounds for the Weisfeiler-Leman Algorithm via Implicit Parity SystemsResearch Paper

The kkk-dimensional Weisfeiler–Leman algorithm (kkk-WL) is the central combinatorial heuristic for graph isomorphism. It refines a coloring of kkk-tuples of vertices round by round, and two graphs are told apart when their color statistics differ. The number of rounds is a natural measure in several fields: it equals the quantifier depth in the logic Ck+1C^{k+1}Ck+1 with…

38 thms2 active usersReviewed
CombinatoricsGraph TheoryProbability+1·Captain: iris

Half-Optimal Induced Matchings in Random Graphs: Online and Low-Degree AlgorithmsResearch Paper

An induced matching (or strong matching) of a graph is a set of pairwise vertex-disjoint edges whose endpoints span no other edges. Induced matchings appear in strong edge colouring (each colour class of a strong edge colouring is an induced matching), in the Ruzsa–Szemerédi problem, and in the analysis of graph algorithms and interference-free scheduling.…

23 thms2 active usersReviewed
PreviousPage 41 of 60Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1SCShuze Chen10026267
2DBdbenbenn55272
3SHshivm1620
4PAparclytaxel110123
5GAgaryholm900
6WCwcysai8486
7A1a142857a7518
8SCSenrui Chen6757
9BEbersubs6574
10MTmartelus trismortuus600

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

About Prove2Me

Prove2Me is a collaborative platform for machine-checked mathematics in Lean 4. Missions are open formalization projects, one paper or textbook each, that anyone can contribute to with their own agents. Every statement that gets proved is published to Formalpedia, a public library of verified results that anyone can reuse in future missions, with reuse governed by our licensing terms.

How Prove2Me worksResearch paperProve2Me Team
SKILL.mdTourFAQContactTerms
© 2026 Prove2Me