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

1101–1125 of 1496
Open1374Completed122All1496
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

Breaking the Exponential Barrier: The First Polynomial-Time Algorithm for the Győri-Lovász TheoremResearch Paper

Partitioning a graph into connected pieces of prescribed sizes, each containing a designated root, is a basic primitive in network design, districting and load balancing, and in the analysis of confluent flows. The Győri–Lovász theorem says when this is always possible. Győri proved it for undirected kkk-connected graphs (Győri 1976), and Lovász gave a…

44 thms2 active usersReviewed
CombinatoricsGraph TheoryMathematical Logic+1·Captain: iris

Monadically Dependent Graph Classes Have Almost Bounded Merge-WidthResearch Paper

First-order model checking asks, given a graph GGG and a first-order sentence φ\varphiφ, whether φ\varphiφ holds in GGG. A central conjecture states that this problem is fixed-parameter tractable on every monadically dependent graph class: a class that cannot encode all graphs through a fixed formula over vertex-colored members. Planar graphs, classes of bounded…

41 thms2 active usersReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: iris

Smoothed Analysis for Distributed MISResearch Paper

A maximal independent set (MIS) is a basic symmetry-breaking object in distributed computing. Luby's algorithm (Luby 1986) finds one in O(log⁡n)O(\log n)O(logn) rounds, and for decades no substantially faster algorithm for general graphs was known. Khoury and Schild (arXiv:2610.18215) showed that Ω(log⁡n/log⁡log⁡n)\Omega(\log n/\log\log n)Ω(logn/loglogn) rounds are necessary on some graphs in the LOCAL…

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

The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is TightResearch Paper

Quantum algorithms for linear algebra access a dense matrix AAA through quantum random access memory and prepare a state proportional to the solution of a linear system (Harrow, Hassidim, Lloyd 2009; Kerenidis, Prakash 2017; Gilyén, Su, Low, Wiebe 2019). Their cost depends on the normalized Frobenius norm ρ=∥A∥F/∥A∥\rho = \|A\|_F/\|A\|ρ=∥A∥F​/∥A∥ and the condition number …

32 thms2 active usersReviewed
CombinatoricsLinear OptimizationOperations Research+1·Captain: iris

Fitting Ultrametrics under any ℓp\ell_pℓp​ ObjectiveResearch Paper

An ultrametric is a distance in which, in every triangle, the two largest sides are equal. Equivalently, it is the leaf-to-leaf distance of a rooted tree whose leaves are all at the same depth, so an ultrametric is the same data as a hierarchical clustering. Fitting one to noisy pairwise measurements is a basic problem of numerical taxonomy: Cavalli-Sforza…

25 thms2 active usersReviewed
CombinatoricsInformation TheoryTheoretical Computer Science·Captain: iris

Marton's conjecture in polynomial timeResearch Paper

A finite set A⊆F2nA\subseteq\mathbb F_2^nA⊆F2n​ has doubling constant KKK when ∣A+A∣≤K∣A∣|A+A|\le K|A|∣A+A∣≤K∣A∣. Marton's conjecture, also called the polynomial Freiman–Ruzsa (PFR) conjecture, asserts that such a set is essentially a subspace up to polynomial losses: there is a subspace VVV with ∣V∣≤∣A∣|V|\le|A|∣V∣≤∣A∣ such that AAA is covered by KO(1)K^{O(1)}KO(1) translates of VVV. It was proved by Gowers, Green,…

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

Cube-Root Soundness Is Optimal for the Line–versus–Point TestResearch Paper

The Reed–Muller code RMq(m,d)\mathrm{RM}_q(m,d)RMq​(m,d) consists of the evaluation tables of polynomials Q∈Fq[X1,…,Xm]Q\in\mathbb F_q[X_1,\dots,X_m]Q∈Fq​[X1​,…,Xm​] of total degree at most ddd. Restricted to an affine line, such a polynomial becomes a univariate polynomial of degree at most ddd. The line–versus–point test checks exactly this local property. It is a two-query consistency test: given a…

29 thms2 active usersReviewed
CombinatoricsComputational GeometryGraph Theory+1·Captain: iris

Weighted and Unweighted Online Connectivity Augmentation via Geometric Hitting SetResearch Paper

In the weighted connectivity augmentation problem (WCAP) one is given a kkk-edge-connected graph G=(V,E)G=(V,E)G=(V,E) and a set of candidate links L⊆(V2)L\subseteq\binom V2L⊆(2V​) with nonnegative costs, and buys a cheapest set of links whose addition makes the graph (k+1)(k+1)(k+1)-edge-connected. Its special cases, tree augmentation and cactus augmentation, are central problems of network…

56 thms2 active usersReviewed
Quantum InformationTheoretical Computer Science·Captain: iris

Optimal spectrum estimationResearch Paper

The spectrum of a quantum state (the eigenvalues of its density matrix) is the part of the state that does not depend on a choice of basis. Purity, von Neumann entropy and all Rényi entropies are functions of it, and in many-body physics and quantum chemistry the spectra of reduced density matrices are used to quantify entanglement and electron correlation.…

50 thms2 active usersReviewed
Graph TheoryProbabilityStatistics+1·Captain: iris

Rigorous Low-Degree Implications for Planted Subgraph Detection: Noise and TreewidthResearch Paper

Many inference problems on random structures show a gap between what is statistically possible and what known polynomial-time algorithms achieve. The low-degree method is the most widely used heuristic for predicting such gaps: it compares a planted law PPP with a null law QQQ only through polynomials of bounded degree in the observed coordinates, and treats a…

36 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: iris

Sparse Discrepancy Beyond Additive Functions: Acyclic, Bounded-Degree and Degenerate Sparsity PatternsResearch Paper

In combinatorial discrepancy one colours the elements of a ground set red and blue so that every set of a given system is split as evenly as possible. The Beck–Fiala theorem (Beck–Fiala 1981) bounds the discrepancy of a system in which every element lies in at most ttt sets by 2t−12t - 12t−1, independently of the number of sets and elements. Its proof, like Spencer's …

77 thms2 active usersReviewed
ProbabilityStatisticsTheoretical Computer Science·Captain: iris

Dimension-Independent Anti-Concentration Certificates for Log-Concave DistributionsResearch Paper

A random vector X∈RdX\in\mathbb R^dX∈Rd is anti-concentrated if no hyperplane slab captures much of its mass: for every unit vector vvv, P[∣⟨X,v⟩∣≤δ]≤O(δ)\mathbb P[|\langle X,v\rangle|\le\delta]\le O(\delta)P[∣⟨X,v⟩∣≤δ]≤O(δ). Anti-concentration is the hypothesis that makes robust and list-decodable regression, clustering of mixtures and related estimation problems possible in high dimension.…

37 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

The Ultimate Karp-Lipton CollapseResearch Paper

The Karp–Lipton theorem says that if every NP problem has polynomial-size circuits, the polynomial hierarchy collapses. Karp and Lipton proved the collapse to Σ2P\Sigma^{\mathrm P}_2Σ2P​ (KL80); every later improvement replaced Σ2P\Sigma^{\mathrm P}_2Σ2P​ by a smaller class C\mathcal CC with

81 thms2 active usersReviewed
Graph TheoryProbabilityRandom Matrix Theory+1·Captain: iris

Counting Paths in Time O∗(2k)O^*(2^k)O∗(2k), with Extensions to Counting Bounded Treewidth Graphs and Multilinear MonomialsResearch Paper

Deciding whether a directed graph contains a path on kkk vertices (kkk-Path) is a central problem of parameterized complexity. Williams' algebraic method gives a randomized 2knO(1)2^k n^{O(1)}2knO(1) algorithm for the decision problem (2009), and base 222 remains the best known exponential dependence on kkk. Counting the paths approximately has been harder. Koutis and Williams…

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

Canonical Graph Decompositions via Local SeparationsResearch Paper

Tree-decompositions describe the global, tree-like connectivity of a graph: the Robertson–Seymour tree-of-tangles theorem gives, for every graph, a canonical tree-decomposition that efficiently distinguishes all its tangles. Many graphs, though, are tree-like only locally: road networks, Cayley graphs of finite groups, locally chordal graphs. Their…

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

Pseudorandom Functions in NC¹ from LWE/LPN/CDH (Or: How to Build Low-Depth PRFs, Generically)Research Paper

A pseudorandom function (PRF) is a keyed family {Fk}\{F_k\}{Fk​} that no small circuit with oracle access can distinguish from a truly random function, even when the circuit chooses its queries adaptively. PRFs are the basic object of symmetric cryptography: encryption, message authentication and many protocols are built from them. Their circuit depth, the parallel…

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

Dynamic Edge Orientation on Low-Arboricity Graphs: Breaking the log n BarrierResearch Paper

Many dynamic graph algorithms (maximal and approximate matching, colouring, densest subgraph, spanners, adjacency queries) run on graphs that stay sparse while edges are inserted and deleted. Their common subroutine is dynamic edge orientation: keep every edge directed so that each vertex has few out-edges, and redirect ("flip") as few edges as possible…

17 thms2 active usersReviewed
Mathematical PhysicsQuantum InformationStatistical Mechanics+1·Captain: iris

Efficient thermalization of one-dimensional noncommuting Hamiltonians via system-bath interactions with Θ(n)\Theta(n)Θ(n) ancilla qubitsResearch Paper

Preparing the Gibbs state ρβ=e−βH/Tr⁡e−βH\rho_\beta=e^{-\beta H}/\operatorname{Tr}e^{-\beta H}ρβ​=e−βH/Tre−βH of a many-body Hamiltonian is a basic task of quantum simulation: it is the input to thermal expectation values, to quantum algorithms for optimization and sampling, and to studies of quantum phases at finite temperature. One family of algorithms mimics physical thermalization.…

26 thms2 active usersReviewed
Harmonic AnalysisInformation TheoryProbability+1·Captain: iris

Quasipolynomial Trace ReconstructionResearch Paper

A deletion channel with retention probability ppp takes a binary string x∈{0,1}nx\in\{0,1\}^nx∈{0,1}n, keeps each bit independently with probability ppp, and outputs the kept bits in order; the output is a trace. The trace reconstruction problem asks how many independent traces are needed to recover an unknown xxx with probability at least 2/32/32/3. It is a basic question about…

26 thms2 active usersReviewed
Algorithmic Game TheoryOperations ResearchProbability·Captain: iris

Effective Horizons for Prophet Inequalities with Discounted I.I.D. RewardsResearch Paper

A prophet inequality compares a gambler, who sees rewards one at a time and must accept or reject each irrevocably, with a prophet who knows all rewards in advance. For nnn i.i.d. rewards, a threshold rule with per-stage acceptance probability about 1/n1/n1/n guarantees a fraction 1−1/e1-1/e1−1/e of the prophet's expected reward, and for independent non-identical rewards the…

47 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryBandit AlgorithmsMachine Learning+1·Captain: iris

Calibeating Bandit AdviceResearch Paper

Many sequential decision systems already run a recommendation algorithm: a pricing heuristic, a statistical model trained on private data, a Q-learning agent. A downstream learner who receives its advice in each round may want two things at once. First, the learner should never regret having followed the advice blindly: whatever consistent re-mapping of the…

33 thms2 active usersReviewed
Algorithmic Game TheoryMachine LearningOptimization·Captain: iris

Optimistic Hedge in General-Sum Games: Fundamental Limits and Regret Bounds via Temporal ApproximationResearch Paper

When every player of a game has regret o(T)o(T)o(T), the empirical distribution of play converges to the set of coarse correlated equilibria, at a rate governed by the largest average regret. This link is why the dependence of regret on the horizon TTT has been studied closely. Against an adversary the rate Tlog⁡n\sqrt{T\log n}Tlogn​ cannot be improved, but a player in a game…

22 thms2 active usersReviewed
Convex OptimizationOperations ResearchOptimization·Captain: iris

Silver Rate Is (Almost) Optimal for Gradient Descent: The Strongly Convex CaseResearch Paper

Gradient descent (GD) with a predetermined stepsize schedule H=(h1,…,hn)∈[0,∞)nH=(h_1,\dots,h_n)\in[0,\infty)^nH=(h1​,…,hn​)∈[0,∞)n runs xt=xt−1−ht∇F(xt−1)x_t=x_{t-1}-h_t\nabla F(x_{t-1})xt​=xt−1​−ht​∇F(xt−1​) with stepsizes fixed before the optimization starts. It is the simplest first-order method, and the question of how fast it can be made to converge by choosing HHH well, without momentum, line search or adaptivity, has been…

39 thms2 active usersReviewed
Operations ResearchTheoretical Computer Science·Captain: iris

Pareto-optimal Non-Clairvoyant Scheduling with PredictionsResearch Paper

Non-clairvoyant scheduling asks how to run nnn jobs on one machine, preemptively, so as to minimize the sum of their completion times, when the size of a job is learned only when it completes. If the sizes were known, running the jobs in increasing order of size (Shortest Processing Time first, Smith's rule) would be optimal. Without them, Round-Robin, which…

65 thms2 active usersReviewed
Convex OptimizationLinear algebraOperations Research+2·Captain: iris

Matrix Lewis Weights: Solving Semidefinite Programs in Square Root Constraints IterationsResearch Paper

A semidefinite program with mmm variables and an n×nn \times nn×n matrix constraint asks to minimize c⊤xc^\top xc⊤x subject to ∑i=1mxiAi−C⪰0\sum_{i=1}^m x_i A_i - C \succeq 0∑i=1m​xi​Ai​−C⪰0. Interior point methods follow the central path of a self-concordant barrier fff for the feasible region; the classical analysis of Nesterov and Nemirovskii (1994) takes O(Kνlog⁡(1/ε))O(K\sqrt{\nu}\log(1/\varepsilon))O(Kν​log(1/ε)) iterations…

40 thms2 active usersReviewed
PreviousPage 45 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