Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Collections

The TCS Formalization Drive

A coordinated effort to formalize the mathematics of theoretical computer science in Lean 4.

Scope: missions in computational complexity, algorithms and optimization, data structures, automata and computability, randomized and approximation algorithms, cryptography, learning theory, information theory, algorithmic game theory, combinatorics, computational geometry, and distributed computing.

490 completed missions

Missions

51–75 of 490
Open92Completed490All582
🏆Completed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: mikedeng1

Eigenvalues and Expanders: A Regular Bipartite Graph Is a Strong Expander If and Only If λ(G) Is Bounded Away from 0Research Paper

Expander graphs are sparse graphs in which every set of vertices has many neighbours. Families of them with bounded degree and expansion bounded away from zero are a basic tool of theoretical computer science: they are the main component of the sorting network of Ajtai, Komlós and Szemerédi (AKS 1983), the building block of superconcentrators and other…

16 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

A Dynamic Near-Optimal Algorithm for Online Linear Programming I: The Competitive Ratio of the Dynamic Learning AlgorithmResearch Paper

Many resource-allocation problems are decided one request at a time: a seller of airline seats or hotel nights, an ad platform allocating advertiser budgets, a network operator admitting bandwidth requests. Each request asks for a bundle of resources and offers a price. It must be accepted or rejected on arrival, before the later requests are seen. The onlin…

13 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability+1·Captain: mikedeng1

Competitive Randomized Algorithms for Nonuniform Problems III: The Optimal Randomized Two-Server Ratio on the 1-d-d Isosceles TriangleResearch Paper

The k-server problem of Manasse, McGeoch and Sleator (J. Algorithms 11 (1990)) asks how kkk mobile servers in a metric space should respond, on-line, to a sequence of requests at points of the space, each of which must be covered by a server. It is the central model of on-line computation: paging is the special case of a uniform metric, and many caching and…

9 thms5 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: xuanji

AlphaEvolve Eighth-Power Bound: omega < 2.371177Research Paper

Formalize ω<2.371177\omega < 2.371177ω<2.371177, the current record from Dupont, Eisenberger, Kozlovskii, Mehrabian, Ruiz, See, Zhou, Alman, Vassilevska Williams and Balog (arXiv:2608.16884, August 2026).

9 thms5 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Competitive Paging Algorithms IV: An Algorithm Competitive against Several Others Exists iff the Reciprocal Ratios Sum to at Most 1Research Paper

Paging is the problem of managing a fast memory that holds kkk pages out of nnn: when a requested page is not in fast memory (a page fault), some resident page must be evicted, and the cost of an algorithm is its number of faults. Practitioners have many eviction rules. Least-recently-used (LRU) performs well on real workloads but can be kkk times worse than the…

9 thms5 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

The Design of Competitive Online Algorithms via a Primal-Dual Approach VIII: The Bounded Allocation ProblemTextbook

The classical online allocation (AdWords) problem has a tight 1 - 1/e competitive ratio in general, achieved by the water-level algorithm and matched by a lower bound in which the number of buyers interested in each item can be as large as the total number of buyers. Buchbinder and Naor's Chapter 13 observes that in many realistic settings each item's…

16 thms5 active users
🏆Completed
Machine LearningProbabilityStatistics+1·Captain: mikedeng1

Foundations of Machine Learning XII: Algorithmic StabilityTextbook

Every generalization bound in Chapters 2-11 depends only on the complexity of a fixed hypothesis set HHH — Rademacher complexity, VC-dimension, growth function — and holds regardless of which algorithm within HHH actually returns the hypothesis. This is both a strength (broad applicability) and a limitation: it throws away everything specific to how an…

12 thms5 active users
🏆Completed
Machine LearningProbabilityStatistics+1·Captain: mikedeng1

Foundations of Machine Learning V: Kernel Methods and the Representer TheoremTextbook

Linear methods like SVMs work only when the classes are linearly separable, but most real data is not. Chapter 6 shows how to get non-linear decision boundaries for free: replace the input space's inner product with a kernel KKK that implicitly computes an inner product in a (possibly very high- or infinite-dimensional) feature space, without ever explicitly…

7 thms5 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: marwahaha

Coppersmith–Winograd Bound: omega < 2.376Research Paper

AI generated but i think correct. I think the milestones make it really annoying but the central theorem looks correct.

72 thms5 active usersReviewed
🏆Completed
Quantum Information·Captain: marwahaha

Quantum Max-Cut: 0.5260.5260.526 energy estimationResearch Paper

Prove that a uniform randomized classical polynomial-time algorithm estimates the maximum Quantum Max-Cut energy within a factor of 0.5260.5260.526 on every graph with nonnegative rational edge weights.

47 thms4 active usersReviewed
🏆Completed
Quantum Information·Captain: marwahaha

Classical 0.53 energy estimation for Quantum Max-CutResearch Paper

Quantum Max-Cut asks for the largest eigenvalue of HG=∑i<jwij(I−SWAPij)H_G=\sum_{i<j}w_{ij}(I-\mathrm{SWAP}_{ij})HG​=∑i<j​wij​(I−SWAPij​) on a graph with nonnegative rational weights. This mission formalizes the classical numerical 0.530.530.53 approximation target motivated by Anshu, Gosset, and Morenz's published TQC 2020 Theorem 3.

54 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOptimization·Captain: iris

Finding Hall Blockers by Matrix Scaling: without a perfect matching, (1/4)n² log(mA_max/A_min) Sinkhorn iterations and a sort of the scaling vectors output a Hall blockerResearch Paper

Matrix scaling asks for positive diagonal matrices that turn a nonnegative matrix into one with prescribed row and column sums. The Sinkhorn algorithm, which alternately normalizes rows and columns, is the standard method; it appears in statistics (iterative proportional fitting), entropic optimal transport, and combinatorial optimization. For the doubly…

16 thms4 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: Shuze Chen

Online Matching and Ad Allocation: MSVV attains the optimal small-bids competitive ratioResearch Paper

An advertising platform must decide which advertiser receives each arriving opportunity before it knows what will arrive later. A bidder offering a high payment now may also be the only bidder interested in a later request. Spending that bidder’s budget immediately can therefore reduce the total money collected over the day. This tension is the Adwords…

16 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Minimum Label s-t Cut has Large Integrality Gaps: Nearly cube-root integrality gap for the strengthened relaxationResearch Paper

A network failure can remove several connections at once. When the connections share a physical resource, paying for or disabling that resource acts on an entire class of edges. The minimum label s-t cut problem captures this distinction: edges carry labels, and the cost of removing a label is paid once, regardless of how many edges have that label. Zhang…

14 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryComputational ComplexityOperations Research·Captain: Shuze Chen

When Are Elections with Few Candidates Hard to Manipulate?: Non-plurality positional scoring is NP-complete to manipulate with three candidatesResearch Paper

A voting rule aggregates submitted preferences into a collective choice. A coalition can sometimes change that choice by coordinating its submitted rankings. The computational question is whether it can efficiently determine how to make a particular candidate win. This matters in collective decision systems where an agent's voting weight can represent…

6 thms4 active usersReviewed
🏆Completed
Operations ResearchStochastic SystemsTheoretical Computer Science·Captain: mikedeng1

Tail-Optimized Caching for LLM Inference: Expected-Tail-Optimized LRU Is an Optimal Online Caching Policy for Tail Excess Latency in the Stochastic Conversation ModelResearch Paper

A large language model serving a multi-turn conversation re-reads the whole conversation history at every turn. The intermediate attention state of that history, the KV cache, can be stored in GPU memory and reused, so that only the uncached part of the prompt must be recomputed before the first output token appears. GPU memory is scarce, so a server must…

8 thms4 active usersReviewed
🏆Completed
Group TheoryQuantum InformationTheoretical Computer Science·Captain: mikedeng1

The Solovay-Kitaev algorithm: every gate in SU(d) is ε-approximated by a sequence of O(log^{ln 5/ln(3/2)}(1/ε)) gates from any instruction setResearch Paper

A quantum computer executes a fixed, finite instruction set of gates, while quantum algorithms are written with arbitrary gates. Every algorithm must therefore be compiled: each gate UUU is replaced by a sequence of available instructions whose product approximates UUU. If an accuracy δ\deltaδ required sequences of length O(1/δ)O(1/\delta)O(1/δ), compiling an mmm-gate…

14 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Pipeline Interventions: The Budget-Splitting Dynamic Program over an ε-Net of the Simplex Attains Social Welfare at Least OPT − 3(k−1)ε‖R‖∞Research Paper

Many consequential outcomes (a faculty position, a high-paying job) are the end of a long pipeline of earlier stages: neighbourhood, elementary school, high school, college, graduate school. Inequities that compound along such a pipeline are hard to correct by intervening only at its last stage, and a planner with a limited budget would like to decide where…

8 thms4 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Stochastic Load Balancing on Unrelated Machines: An Effective-Size LP and Its Rounding Give a Constant-Factor Approximation to the Minimum Expected MakespanResearch Paper

Load balancing asks for an assignment of nnn jobs to mmm machines that keeps the largest machine load, the makespan, small. On unrelated machines the processing time of a job may depend arbitrarily on the machine; the deterministic problem has the classical 222-approximation of Lenstra, Shmoys and Tardos (1990). In many applications (virtual-circuit routing,…

16 thms4 active usersReviewed
🏆Completed
ProbabilityQuantum InformationTheoretical Computer Science·Captain: mikedeng1

Simulating Large Quantum Circuits on a Small Quantum Computer: A (K, d)-Clustered Circuit Is Simulated to Precision ε with Probability 2/3 by O(2^{4K} r/ε²) Runs of d-Qubit PiecesResearch Paper

Near-term quantum processors have few qubits, while the circuits one would like to run (variational eigensolvers, sampling benchmarks, error-mitigated algorithms) often need more qubits than any single device has. Peng, Harrow, Ozols and Wu (arXiv:1904.00102, Phys. Rev. Lett. 125, 150504, 2020) show that a circuit which is only loosely connected (a few…

16 thms4 active usersReviewed
🏆Completed
Linear algebraQuantum InformationTheoretical Computer Science·Captain: mikedeng1

Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics: Singular Value Transformation by Real Polynomials via Alternating Phase ModulationResearch Paper

Many quantum algorithms act on a matrix AAA that is not itself unitary: a Hamiltonian to be simulated, a linear system to be inverted, a projector to be amplified. The standard way to hand such a matrix to a quantum computer is to embed it as a block of a unitary UUU, so that A=Π~UΠA=\widetilde\Pi U\PiA=ΠUΠ for two orthogonal projectors Π,Π~\Pi,\widetilde\PiΠ,Π. The question is…

15 thms4 active usersReviewed
🏆Completed
Linear algebraOptimizationQuantum Information+1·Captain: mikedeng1

Optimization by Decoded Quantum Interferometry 2: With an Imperfect Decoder and Uniform v, 𝔼_v⟨f⟩ ≥ wᵀ[A − 2ε(m+1)]w / Σ_k w_k²(1 − ε_k) for max-XORSATResearch Paper

A max-XORSAT instance asks for a binary assignment that satisfies as many parity constraints as possible. A matrix specifies the parity check in each constraint, while a second binary vector specifies the desired parity. The objective can be written as the number of satisfied constraints minus the number violated, so an assignment with a high objective…

10 thms4 active usersReviewed
🏆Completed
Linear algebraQuantum InformationTheoretical Computer Science·Captain: mikedeng1

Learning Stabilizer States by Bell Sampling: Algorithm 1 Identifies an n-Qubit Stabilizer State from 5n+2 Copies, Failing with Probability at Most 2⁻ⁿResearch Paper

Determining an unknown quantum state of nnn qubits to good accuracy requires, in general, a number of copies of the state exponential in nnn; this follows from Holevo's theorem. One way around this barrier is to restrict the class of states. Stabilizer states are the natural candidate: they are the states produced from ∣0n⟩|0^n\rangle∣0n⟩ by Clifford circuits, they…

14 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability+1·Captain: mikedeng1

Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios II: In the Deterministic Case Multi-price Ranking Is minᵢ F(𝒫ᵢ)-CompetitiveResearch Paper

Online matching models a platform that must commit resources to requests as they arrive, without knowing the future. In revenue management the resources are items in limited supply and the requests are customers, and the firm also chooses the price. Ma and Simchi-Levi (arXiv:1905.04770, Oper. Res. 2020, DOI 10.1287/opre.2019.1957) give algorithms whose…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature I: Swap-Local Optima of the Non-Oblivious Potential Are (1 − c/e)-Approximate for Submodular MaximizationResearch Paper

Maximizing a monotone submodular function over the bases of a matroid is the standard model for coverage, facility location, sensor placement and welfare maximization. The best possible approximation factor in the value-oracle model is 1−1/e1 - 1/e1−1/e (Nemhauser–Wolsey 1978; Călinescu–Chekuri–Pál–Vondrák 2011). Many functions met in practice are far from the worst…

9 thms4 active usersReviewed
PreviousPage 3 of 20Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1EYEyal199050737706
2FIfizzyinc313047
3MAmarwahaha643870
4MRmrfancypants6290
5DBdbenbenn546543
6KMkmehltretter82385111
7NINihal2960
8NINickrobbins952698
9SCShuze Chen224794
10SHshivm2080

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