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.

491 completed missions

Missions

476–491 of 491
Open91Completed491All582
🏆Completed
Theoretical Computer Science·Captain: Chutong

CLRS — Chapter 4, §4.2: Strassen Matrix Multiplication — Correctness and Running TimeTextbook

Prove2Me mission category: Textbook.

7 thms1 active userReviewed
🏆Completed
Theoretical Computer Science·Captain: lunjia

CLRS — Chapter 21, §21.2: Kruskal — Correctness and Inverse-Ackermann Running TimeTextbook

Prove2Me mission category: Textbook.

11 thms1 active userReviewed
🏆Completed
Theoretical Computer Science·Captain: lunjia

CLRS — Chapter 21, §21.2: Prim with a Fibonacci Heap — Correctness and Running TimeTextbook

Prove2Me mission category: Textbook.

7 thms1 active userReviewed
🏆Completed
Theoretical Computer Science·Captain: lunjia

CLRS — Chapter 22, §22.3: Dijkstra with a Fibonacci Heap — Correctness and Running TimeTextbook

Prove2Me mission category: Textbook.

7 thms1 active userReviewed
🏆Completed
ProbabilityTheoretical Computer Science·Captain: YY

Appendix E — Randomized AC0 Sampling of Regular Languages and Markov ChainsResearch Paper

Sampling an entire finite-state execution is a different computational task from recognizing a supplied word. A membership circuit must answer correctly on its given input. A sampler instead chooses the input together with its associated output, while preserving their joint distribution. This distinction is relevant when finite-state models describe…

10 thms1 active userReviewed
🏆Completed
Complexity TheoryOperations ResearchTheoretical Computer Science·Captain: wurtle

A Polynomial-Time Algorithm for Three-Machine Unit-Job SchedulingResearch Paper

A set of unit-length jobs with precedence constraints is to be run on a fixed number of identical machines so that all jobs finish as early as possible. For two machines this was solved in 1969–1972; for a number of machines given as part of the input the problem is NP-complete (Ullman, 1975). Whether the problem is polynomial-time solvable for three machine…

4 thms1 active userReviewed
🏆Completed
Theoretical Computer Science·Captain: marwahaha

OpenAI matrix multiplication: the 9/4 boundResearch Paper

Multiplying matrices is a basic operation whose asymptotic cost is measured by the number of scalar arithmetic operations needed as the matrix dimensions increase. The familiar entry-by-entry algorithm has cubic cost. The question addressed here is how small an exponent can describe exact multiplication of square matrices when algorithms may use more…

2 thms1 active userReviewed
🏆Completed
CombinatoricsProbabilityQuantum Information+1·Captain: sattath

A Quantum Lovász Local Lemma (Ambainis, Kempe, Sattath)Research Paper

Status: complete. This mission records a finished formalization rather than an open call for work. Every statement below, including the goal, was uploaded together with a proof that the platform has verified, so there is nothing left to prove.

1 thm1 active userReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: wurtle

APSP in O(n^2.9983) via All-Edges Exact TriangleResearch Paper

All-pairs shortest paths (APSP) computes the shortest distance between every pair of vertices in a weighted graph.

49 thms1 active userReviewed
🏆Completed
CombinatoricsOptimizationTheoretical Computer Science·Captain: moutei

Primal-Dual Online Algorithms III: Set-Cover Approximation via CertificatesTextbook

Set cover is the standard worked example of the primal-dual method, and Chapter 2 of Buchbinder's thesis uses it that way: it is where the machinery of §2.1 is first turned on a concrete NP-hard problem. Two analyses appear. The greedy algorithm, analysed by dual fitting, buys the set with the best cost-per-newly-covered-element ratio and charges the price…

10 thms1 active userReviewed
🏆Completed
Linear OptimizationOptimizationTheoretical Computer Science·Captain: moutei

Primal-Dual Online Algorithms I: Fractional Ski RentalTextbook

An online algorithm must commit to decisions before it knows the rest of its input, and it is judged by competitive analysis: the ratio between its cost and the cost of an optimal solution computed with full knowledge of the input. A recurring obstacle in this area is that each problem seems to need its own ad hoc potential-function argument. Buchbinder's…

9 thms1 active userReviewed
🏆Completed
Mathematical LogicTheoretical Computer Science·Captain: tomasz

Friedberg–Muchnik: incomparable computably enumerable setsResearch Paper

Computability theory studies which questions admit algorithms and how the unsolvable questions compare with one another. A decision problem can be represented by a set of natural numbers: the question on input nnn is whether nnn belongs to the set. Even when there is no algorithm that always answers this question, there may be an algorithm that eventually…

11 thms1 active userReviewed
🏆Completed
AlgebraTheoretical Computer Science·Captain: Cosme

Eilenberg Theorems for Many-Sorted FormationsResearch Paper

Classical Eilenberg correspondence theorems connect algebraic descriptions of finite-state behavior with language-theoretic closure principles. The version developed by Juan Climent Vidal and Enric Cosme Llópez replaces one-sorted monoids by many-sorted algebras, so that operations may accept arguments of several prescribed sorts and return a value of…

9 thms1 active userReviewed
🏆Completed
AlgebraTheoretical Computer Science·Captain: Cosme

A Kleene Theorem for Free Many-Sorted AlgebrasResearch Paper

Kleene's theorem (Kleene 1956; McNaughton–Yamada 1960) is a cornerstone of formal language theory: over a free monoid, the languages recognized by finite automata are exactly the regular ones — those built from finite languages by union, concatenation, and the Kleene star. Mezei and Wright (1967) lifted recognizability off strings, calling a subset of an…

32 thms1 active userReviewed
🏆Completed
CombinatoricsNumber TheoryTheoretical Computer Science·Captain: ShouqiaoWang

Erdős Problem 788: Exponent One-Half and Explicit BoundsResearch Paper

Erdős Problem 788 asks how large a set can always be retained when prescribed distinct pair-sums are forbidden. This mission formalizes the repository’s strengthened version of Theorem 1.1: an explicit lower bound valid for every n≥3n\ge 3n≥3, an eventual quantitative upper bound, the conclusion f(n)=n1/2+o(1)f(n)=n^{1/2+o(1)}f(n)=n1/2+o(1), and the exact affirmative answer to the original…

6 thms1 active userReviewed
🏆Completed
Theoretical Computer Science·Captain: intro_user0735

Schönhage's Bound: omega < 2.55Research Paper

Prove Schönhage's 1981 bound that the matrix-multiplication exponent satisfies omega < 51/20, via the tau theorem and the asymptotic sum inequality.

0 thms0 active usersReviewed
PreviousPage 20 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