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

451–475 of 491
Open91Completed491All582
🏆Completed
Machine LearningProbabilityStatistics+1·Captain: mikedeng1

Foundations of Machine Learning XIII: The Johnson-Lindenstrauss LemmaTextbook

High-dimensional data is often computationally expensive to work with and hard to visualize. The Johnson-Lindenstrauss lemma answers a striking question in this setting: can any finite set of points, no matter how high-dimensional the ambient space, be squeezed into a space of dimension depending only on the number of points (logarithmically) and the…

6 thms2 active usersReviewed
🏆Completed
Mechanism DesignTheoretical Computer Science·Captain: Shuze Chen

Algorithmic Game Theory III: Arrow and Gibbard–SatterthwaiteTextbook

Before a mechanism can pay anyone, it must decide something — and the impossibility theorems of social choice say that deciding honestly is already hard. Arrow's theorem (1951) showed that any method of aggregating individual rankings into a social ranking that respects unanimity and independence of irrelevant alternatives must be a dictatorship; Gibbard…

4 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryTheoretical Computer Science·Captain: Shuze Chen

Algorithmic Game Theory II: No-Regret Learning and Correlated EquilibriaTextbook

Equilibrium concepts are static; play is dynamic. The bridge between the two is regret minimization: simple adaptive rules that, against arbitrary — even adversarial — opponents, perform nearly as well as the best fixed alternative in hindsight. The subject begins with Hannan (1957) and Blackwell (1956), whose consistency theorems predate most of…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsProbabilityTheoretical Computer Science·Captain: sr

Erdős (1947): The Probabilistic Ramsey Lower BoundResearch Paper

Ramsey theory asks for the smallest number R(k)R(k)R(k) such that every graph on R(k)R(k)R(k) vertices contains either a clique of size kkk or an independent set of size kkk. Beyond being one of the oldest problems in extremal combinatorics, Ramsey numbers sit at the junction of combinatorics, probability, and computer science: the two-coloring of edges they quantify is…

5 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: wenxinzhang

Primal-Dual Online Load Balancing on Unrelated MachinesTextbook

Fix m≥1m \ge 1m≥1 machines and nnn jobs arriving one at a time in the order 0,…,n−10, \dots, n-10,…,n−1. Job iii carries a whole vector of nonnegative loads p~(i,j)\tilde p(i,j)p~​(i,j), one per machine, with no assumed relationship between the entries — the same job may be cheap on one machine and unplaceable on another. This is the unrelated machines model. When job iii arrives its load vector…

10 thms2 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: marwahaha

A 2o(n)2^{o(n)}2o(n) Time Algorithm for 3-SAT: Refuting ETHResearch Paper

The Exponential Time Hypothesis (ETH) asserts that deciding whether a Boolean formula with at most three literals per clause has a satisfying assignment requires a positive exponential rate in its number of variables. It is a benchmark assumption in computational complexity. The paper A 2o(n)2^{o(n)}2o(n) Time Algorithm for 3-SAT, attributed to Claude (Anthropic),…

8 thms1 active userReviewed
🏆Completed
Theoretical Computer Science·Captain: kmehltretter82

Exponential lower bounds for Cunningham’s ruleResearch Paper

A local improvement algorithm can reach an optimum without coming close to doing so quickly. A pivot rule chooses the next neighboring solution of a linear program. Cunningham’s rule uses a fixed cyclic order and remembers the last variable selected. It resumes its scan from that variable, choosing the first eligible entering variable. Avis and Friedmann…

13 thms1 active userReviewed
🏆Completed
Formal VerificationTheoretical Computer Science·Captain: pitimespi

OpenSearch cluster coordination: randomized election timersTextbook

When an OpenSearch cluster has no cluster-manager, every cluster-manager-eligible node in candidate mode that has discovered enough peers to form an election quorum (or has just bootstrapped the cluster) starts an election scheduler (ElectionSchedulerFactory), which fires at random intervals; each firing starts a new pre-voting round if the node is still a…

8 thms1 active userReviewed
🏆Completed
Formal VerificationTheoretical Computer Science·Captain: pitimespi

OpenSearch cluster coordination: progress under a stable periodTextbook

The safety mission proves that OpenSearch's cluster coordination never forks, whatever the network does: messages lost, duplicated, delayed or reordered, nodes restarting. Progress cannot be proved in that generality. In that model a message may never be delivered, and nothing stops candidates from starting elections in ever higher terms, each start-join…

7 thms1 active userReviewed
🏆Completed
Formal VerificationTheoretical Computer Science·Captain: pitimespi

OpenSearch cluster coordination: safety of the Zen2 consensus protocolTextbook

An OpenSearch cluster keeps its metadata in one cluster state that an elected node, the cluster-manager, publishes to the others. Every node runs the per-node consensus state machine CoordinationState, transcribed and specified in the OpenSearchCoordination mission, driven by the Coordinator over a network that loses, duplicates, delays and reorders…

45 thms1 active userReviewed
🏆Completed
Formal VerificationTheoretical Computer Science·Captain: pitimespi

OpenSearch cluster coordination: pre-voting and election schedulingTextbook

In OpenSearch's cluster coordination a node starts an election by sending StartJoinRequests for a new term, and every node that handles one moves to that term (CoordinationState.handleStartJoin, transcribed in the per-node mission) and discards its election and publication state: a leader that handles one is no longer leader. A node that started elections…

11 thms1 active userReviewed
🏆Completed
Formal VerificationTheoretical Computer Science·Captain: pitimespi

OpenSearch cluster coordination: the per-node consensus state machine (CoordinationState)Textbook

OpenSearch (and Elasticsearch since 7.0) keeps the metadata of a cluster — which indices exist, their mappings and settings, which node holds which shard — in a single cluster state that one elected node, the cluster-manager (formerly "master"), publishes to all others. The algorithm that elects the cluster-manager and makes every published state durable is…

19 thms1 active userReviewed
🏆Completed
Quantum Information·Captain: marwahaha

Quantum Max-Cut: 0.5950.5950.595 energy estimationResearch Paper

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

26 thms1 active userReviewed
🏆Completed
Quantum Information·Captain: marwahaha

Quantum Max-Cut: 0.6030.6030.603 energy estimationResearch Paper

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

25 thms1 active userReviewed
🏆Completed
Quantum Information·Captain: marwahaha

Quantum Max-Cut: 0.6140.6140.614 energy estimationResearch Paper

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

26 thms1 active userReviewed
🏆Completed
Quantum Information·Captain: marwahaha

Classical 1/21/21/2 energy estimation for Quantum Max-CutTextbook

This completed mission proves a deterministic classical polynomial-time 1/21/21/2 approximation to the Quantum Max-Cut optimum. Compute total edge weight WWW and a greedy maximum-edge matching of weight ggg, then return the exact rational estimate v=(W+3g)/2v=(W+3g)/2v=(W+3g)/2.

3 thms1 active userReviewed
🏆Completed
Quantum Information·Captain: marwahaha

Classical 0.4980.4980.498 energy estimation for Quantum Max-CutTextbook

This completed mission proves existence of a classical polynomial-time numerical 0.4980.4980.498 approximation to Quantum Max-Cut. Every returned rational estimate is at most the unrestricted optimum, and its expectation is at least 0.498 OPT(G)0.498\,\mathrm{OPT}(G)0.498OPT(G).

4 thms1 active userReviewed
🏆Completed
Quantum Information·Captain: marwahaha

Classical 1/41/41/4 energy estimation for Quantum Max-CutTextbook

This completed foundation proves a deterministic classical polynomial-time numerical estimator for Quantum Max-Cut. If WWW is total edge weight, the algorithm returns the exact rational v=W/2v=W/2v=W/2.

3 thms1 active userReviewed
🏆Completed
Quantum Information·Captain: marwahaha

A verified 1/41/41/4-approximation foundation for Quantum Max-CutTextbook

Quantum Max-Cut is an optimization problem for a system of interacting qubits. An input graph specifies which pairs interact and the nonnegative weight of each interaction. The task is to prepare a quantum state with high energy relative to the maximum permitted by quantum mechanics. This makes approximation algorithms a way to compare feasible state…

2 thms1 active userReviewed
🏆Completed
Formal VerificationTheoretical Computer Science·Captain: pitimespi

Bitcoin: the selfish-mining chain has a unique stationary distributionTextbook

The selfish-mining mission took the stationary distribution of Eyal and Sirer's equation (7) as a definition and proved it is invariant with total mass 1. That leaves a gap a careful reader will point out: the revenue analysis is only meaningful if the chain has no other stationary distribution. This mission closes it: every nonnegative, lead-summable,…

9 thms1 active userReviewed
🏆Completed
Formal VerificationTheoretical Computer Science·Captain: pitimespi

Bitcoin: chain growth, common prefix and chain quality in the synchronous backbone modelTextbook

"Bitcoin is secure as long as honest miners hold the majority of the hashrate" is the informal reading of Garay, Kiayias and Leonardos's backbone analysis: in a synchronous network, if the adversary finds fewer blocks than there are uniquely successful honest rounds over every long enough window, then honest chains grow (chain growth), agree on all but…

9 thms1 active userReviewed
🏆Completed
Complexity TheoryDiscrete Geometry·Captain: marwahaha

OpenAI Ten Proofs 07: Hardness of the closest vector problemResearch Paper

Hardness of the closest vector problem, from the OpenAI Ten Proofs formalization. The source already contains machine-checked proofs; this mission organizes its headline result and additional Comparator targets for reuse.

5 thms1 active userReviewed
🏆Completed
Complexity Theory·Captain: marwahaha

OpenAI Ten Proofs 05: Arithmetic formula lower bounds for the permanentResearch Paper

Arithmetic formula lower bounds for the permanent, from the OpenAI Ten Proofs formalization. The source already contains machine-checked proofs; this mission organizes its headline result and additional Comparator targets for reuse.

3 thms1 active userReviewed
🏆Completed
Information Theory·Captain: marwahaha

OpenAI Ten Proofs 02: Binary and spherical codesResearch Paper

Binary and spherical codes, from the OpenAI Ten Proofs formalization. The source already contains machine-checked proofs; this mission organizes its headline result and additional Comparator targets for reuse.

11 thms1 active userReviewed
🏆Completed
Complexity TheoryQuantum Information·Captain: thomasvidick

MIP* = REResearch Paper

In a two-player one-round nonlocal game, a verifier samples a pair of questions, sends one to each of two players who cannot communicate, and accepts or rejects the pair of answers. The players may share an arbitrary quantum state and measure it; the entangled value of the game is the supremum of their acceptance probability over all such strategies.…

109 thms1 active userReviewed
PreviousPage 19 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