Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Theoretical Computer Science

1,446 missions · 603 completed

The mathematical foundations of computation: which problems can be solved, by what algorithms, and at what cost in time, space, or communication. Distinguished by its emphasis on rigor and unconditional lower bounds, it spans computational complexity, algorithm design, automata and computability, cryptography, and the analysis of Boolean functions.

Missions

Open843Completed603All1446
🏆Completed
Linear Optimization·Captain: hypercube

Approximate Dual Separation for the Cluster LP: a 1.3871.3871.387-approximation for Correlation ClusteringResearch Paper

Suppose every pair of vertices comes with a positive or negative judgment. A partition agrees with a positive judgment when the vertices lie in the same block and with a negative judgment when they lie in different blocks. MinDisagree asks for a partition with as few disagreements as possible. The number of blocks is unrestricted. This mission concerns…

29 thms1 active userReviewed
🏆Completed
Complexity Theory·Captain: WizardOfMenlo

Nearly Optimal Hardness for CVP and NCP with PreprocessingResearch Paper

In the nearest codeword problem (NCP) one is given a linear code C⊆FM\mathcal C \subseteq \mathbb F^MC⊆FM over a finite field and a target word t∈FMt \in \mathbb F^Mt∈FM, and must find a codeword closest to ttt in Hamming distance. In the closest vector problem (CVP) one is given a full-rank lattice Λ⊆RM\Lambda \subseteq \mathbb R^MΛ⊆RM and a target t∈RMt \in \mathbb R^Mt∈RM, and must find…

42 thms1 active user
🏆Completed
Complexity TheoryMathematical Logic·Captain: kmehltretter82

A New Recursion-Theoretic Characterization of the Polytime Functions (Bellantoni & Cook, Computational Complexity 1992)Research Paper

Cobham's seminal 1965 characterization of the polynomial-time computable functions (FP\mathsf{FP}FP) by bounded recursion on notation required an explicit a priori polynomial size bound f(x,y⃗)≤b(x,y⃗)f(x, \vec{y}) \le b(x, \vec{y})f(x,y​)≤b(x,y​) attached to every recursive definition, embedding a semantic growth check directly into the syntax of function definitions. Bellantoni and Cook (C…

8 thms1 active userReviewed
🏆Completed
Mathematical LogicType Theory·Captain: kmehltretter82

Decidability of Conversion for Type Theory in Type Theory (Abel, Öhman & Vezzosi, POPL 2018)Research Paper

In intensional Martin-Löf Type Theory (MLTT), type checking depends directly on conversion checking: the conversion rule states that if Γ⊢t:A\Gamma \vdash t : AΓ⊢t:A and Γ⊢A≡B\Gamma \vdash A \equiv BΓ⊢A≡B, then Γ⊢t:B\Gamma \vdash t : BΓ⊢t:B. Consequently, the decidability of type checking reduces to the decidability of judgmental equality Γ⊢A≡B\Gamma \vdash A \equiv BΓ⊢A≡B and …

11 thms1 active userReviewed
🏆Completed
Captain: kmehltretter82

Exponential lower bounds for deterministic strategy iterationResearch Paper

A parity game is a finite graph game in which two players choose an infinite walk and the largest priority recurring on the walk determines the winner. Such games supply algorithmic tasks in verification. An algorithm may solve many practical instances quickly and still require many updates on a deliberately constructed family. This mission concerns the…

15 thms1 active userReviewed
🏆Completed
Complexity Theory·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
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 Verification·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 Verification·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 Verification·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 Verification·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 Verification·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
Mathematical LogicType Theory·Captain: kmehltretter82

Refined Program Extraction from Classical ProofsResearch Paper

A proof that an output exists can contain enough information to compute that output. Classical proofs make this connection less direct: an existence claim may be established through a contradiction without displaying its witness. This mission formalizes the extraction method of Berger, Buchholz, and Schwichtenberg in Refined program extraction from…

14 thms1 active user
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin: MuSig2 and FROST correctness over secp256k1, with the executable curve proved to be a groupTextbook

MuSig2 (BIP327) lets nnn signers produce one BIP340 Schnorr signature for an aggregate key, indistinguishable on chain from a single-signer Taproot spend; FROST does the same for a threshold of signers. The correctness claim is that partial signatures which each pass their partial check combine into a signature that the ordinary Schnorr verifier accepts.…

30 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin: Miniscript compiler soundness against the script interpreterTextbook

Miniscript is the structured subset of Bitcoin Script that wallets use to write and analyse spending policies: each fragment has a fixed translation to Script, a type that says what it does to the stack, and a satisfaction table that says which witnesses make it succeed. The claim that makes it trustworthy is compiler correctness: a well-typed Miniscript…

19 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin: honest majority makes backbone executions typical with overwhelming probabilityTextbook

The backbone mission proved chain growth, common prefix and chain quality for every typical execution: one in which, on every window of at least λ\lambdaλ rounds, the adversary finds fewer blocks than there are uniquely successful honest rounds. Garay, Kiayias and Leonardos show that under honest majority executions are typical except with probability…

23 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin: the cluster-mempool feerate-diagram check of replace-by-feeTextbook

At the pinned revision, Bitcoin Core's cluster mempool replaced BIP125 rule 3 ("the replacement's feerate must exceed every conflict's") with a single check: the replacement must strictly improve the feerate diagram of the affected clusters. The replace-by-fee mission had to take rule 3 from v29.0 for that reason. This mission transcribes the actual check (…

18 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin: the selfish-mining revenue share as a long-run averageTextbook

Eyal and Sirer's relative revenue is computed from the stationary distribution of their Markov chain, and the threshold result is read as "a pool above the threshold earns more than its share over time". The selfish-mining missions proved the formula for the stationary distribution, its uniqueness, and the threshold as statements about that distribution.…

30 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin: the legacy script interpreter with the signature script code tracked exactlyTextbook

The script mission's interpreter, reviewed twice and tested against Core's 994 vectors, is exact except at two documented limits: L1, the signature script code does not restart after an executed OP_CODESEPARATOR (a handful of historical transactions), and L10, OP_CHECKMULTISIG deletes only the checked signature from the script code instead of all of them…

21 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin: the Lightning penalty at the script levelTextbook

Lightning's security against a counterparty who broadcasts an old, revoked commitment transaction rests on the penalty: the honest party, who holds the revocation secret for that commitment, can take every output at once, while the cheater can take nothing before to_self_delay blocks. The script missions proved what each commitment output's script enforces;…

22 thms1 active userReviewed
🏆Completed
Formal Verification·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 Verification·Captain: pitimespi

Bitcoin: a received HTLC cannot be timed out before its expiry, at the block levelTextbook

The HTLC mission proved which witnesses spend a received HTLC output under the script interpreter, and that its timeout path runs through OP_CHECKLOCKTIMEVERIFY <cltv_expiry>. That is a statement about one script evaluation. The claim Lightning actually needs is one block higher: no block can contain a non-revocation spend of a received HTLC by the timeout…

4 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin: the Lightning funding output under VerifyScriptTextbook

A Lightning channel's funds sit in the funding transaction's output, a pay-to-witness-script-hash of the 2-of-2 script 2 <pubkey1> <pubkey2> 2 OP_CHECKMULTISIG. Everything else in the protocol (commitment transactions, penalties, HTLCs) rests on one fact about this output: it moves only with both parties' signatures. This mission proves that fact against…

5 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin: the Lightning anchor-output scripts under VerifyScriptTextbook

Modern Lightning channels use option_anchors: the remote balance and both HTLC kinds carry a one-block OP_CHECKSEQUENCEVERIFY so that a commitment transaction's outputs cannot be spent in the same block it confirms in, and each side gets an anchor output that it can spend at any time to bump the fee, and that anyone can sweep after 16 blocks so that anchors…

25 thms1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin: the Lightning HTLC scripts under VerifyScriptTextbook

A Lightning commitment transaction carries one output per in-flight payment: an offered HTLC (the local node pays if the remote reveals the preimage, or recovers the funds after the timeout) or a received HTLC (the local node claims with the preimage before expiry, else the remote takes the funds back). BOLT #3 gives each a witness script with three…

17 thms1 active userReviewed
PreviousPage 23 of 25Next

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