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
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Approximation Algorithms for Combinatorial Problems II: The Greedy Literal Algorithm B1 Has Worst-Case Ratio (k+1)/k on MS(k)Research Paper

Maximum satisfiability asks for a truth assignment satisfying as many clauses of a propositional formula as possible. The paper notes that the restriction MS(k)MS(k)MS(k), in which every clause has at least kkk literals, is polynomial complete for every k≥1k \ge 1k≥1, so exact optimization is out of reach in general and one asks instead how close a fast algorithm is…

8 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Approximation Algorithms for Combinatorial Problems I: The Subset-Sum Algorithms A_k Have Worst-Case Ratio (k+1)/kResearch Paper

David S. Johnson's 1974 paper Approximation Algorithms for Combinatorial Problems (J. Comput. System Sci. 9 (1974) 256–278) is one of the founding papers of the theory of approximation algorithms. It asks, for optimization problems whose decision versions Karp had just shown to be polynomial complete, how close a fast heuristic can be guaranteed to come to…

8 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

An n Job, One Machine Sequencing Algorithm for Minimizing the Number of Late Jobs I: Moore's Algorithm Yields a Schedule with the Minimum Number of Late JobsResearch Paper

A single machine must process a set of jobs, each with a processing time and a due-date, and a job that finishes after its due-date is late. Counting late jobs is the natural objective when a late order is simply lost, whatever its lateness. In the three-field notation of scheduling theory this is the problem 1 ∥ ∑Uj1\,\|\,\sum U_j1∥∑Uj​, and it is one of the few…

15 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: mikedeng1

Fast Algorithms for Finding Nearest Common Ancestors III: The Plies of the Compressed Tree Are SmallResearch Paper

The nearest common ancestor problem asks, for a rooted tree and two of its vertices vvv and www, for the deepest vertex that is an ancestor of both, written nca⁡(v,w)\operatorname{nca}(v,w)nca(v,w). It is a subroutine in string and graph algorithms.

9 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

An Analysis of Several Heuristics for the Traveling Salesman Problem II: Every Insertion Method Is Within ⌈lg n⌉ + 1 of the Optimal TourResearch Paper

The traveling salesman problem asks for a shortest closed route visiting every node of a weighted complete graph exactly once. It is NP-hard, so practitioners use fast heuristics, and the basic question about a heuristic is how far from optimal its tour can be. Rosenkrantz, Stearns and Lewis (SIAM J. Comput. 6(3), 1977) gave the first systematic worst-case…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsDynamic Programming·Captain: mikedeng1

A Faster Algorithm Computing String Edit Distances 1: for a finite alphabet and discrete costs, the block algorithm (Algorithms Y and Z) computes the edit distance from a finite tableResearch Paper

The edit distance between two strings is the least total cost of a sequence of single-character insertions, deletions and replacements turning one string into the other. It is the basic similarity measure of spelling correction, file comparison and biological sequence alignment. Wagner and Fischer (JACM 1974) showed that it can be computed by filling a …

10 thms2 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationOperations Research·Captain: mikedeng1

Finding Minimum-Cost Circulations by Canceling Negative Cycles: Polynomial Termination of Minimum-Mean Cycle CancelingResearch Paper

The minimum-cost circulation problem is a central problem of network optimization: transportation, assignment, shortest-path and maximum-flow problems are all special cases, and it is one of the few classes of linear programs with fast combinatorial algorithms. The oldest algorithm for it, the cycle-canceling algorithm of Klein (1967), repeatedly finds a…

10 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

An Optimal On-Line Algorithm for Metrical Task System 2: The Randomized Competitive Ratio of the Uniform Task System Lies Between H(n) and 2H(n)Research Paper

Metrical task systems, introduced by Borodin, Linial and Saks (J. ACM 39(4), 1992), are a common abstraction of on-line problems in which a server occupies one of finitely many states, pays a cost for each task depending on its current state, and may pay a transition cost to change state first. Paging, list update and the kkk-server problem all fit into this…

9 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

An Optimal On-Line Algorithm for Metrical Task System 1: Every n-State Metrical Task System Has Competitive Ratio 2n - 1Research Paper

A system that processes a stream of tasks can often be configured in several ways, and the configuration affects both the cost of the current task and the cost of switching before the next one: paging schemes, replicated files, server placements. When the future is unknown, the natural worst-case yardstick is competitive analysis, introduced by Sleator and…

12 thms2 active usersReviewed
🏆Completed
Information Theory·Captain: marwahaha

Most Informative Boolean Function ConjectureResearch Paper

Send a uniformly random string X∈{0,1}nX \in \{0,1\}^nX∈{0,1}n through a memoryless binary symmetric channel with crossover probability ppp: each coordinate is flipped independently with probability ppp, producing Y∈{0,1}nY \in \{0,1\}^nY∈{0,1}n. An observer sees YYY and wants to learn about XXX — but the summary of XXX they are allowed to keep is a single bit f(X)f(X)f(X), computed by a Boolean function fff…

7 thms2 active usersReviewed
🏆Completed
AnalysisMachine LearningProbability·Captain: MiltMont

Flow Matching Theorem 1: Marginal Continuity EquationResearch Paper

Flow matching models a changing probability distribution using a time-dependent velocity field. A conditional model specifies a density and a velocity separately for each conditioning point. The mathematical question is whether those conditional descriptions determine a velocity for the mixture distribution. This mission concerns the continuity-equation…

6 thms2 active usersReviewed
🏆Completed
Information Theory·Captain: LG

Shannon 1949: Perfect SecrecyResearch Paper

Cryptography before 1949 was a catalogue of ciphers and of the tricks that broke them. C. E. Shannon's Communication Theory of Secrecy Systems (Bell System Technical Journal 28(4):656–715, 1949) replaced the catalogue with a probabilistic model: a cipher is a family of invertible maps from messages to cryptograms, indexed by a key drawn from a known…

7 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

The Design of Competitive Online Algorithms via a Primal-Dual Approach IX: General Packing-Covering ConstraintsTextbook

Chapter 4's framework (formalized in this series' 04-framework mission) solves the online covering-packing pair only in the restricted setting a(i,j) ∈ {0,1}, b(j) = 1 — every constraint is an unweighted "cover me with at least one of these" condition. Chapter 14 delivers the promise made at the very start of the survey (p. 115: "we show how to extend the…

7 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

The Design of Competitive Online Algorithms via a Primal-Dual Approach V: Online RoutingTextbook

Network routing is one of the paradigmatic applications of the online primal-dual method: requests for bandwidth between a source and target arrive one at a time, and the algorithm must commit bandwidth to paths without knowing future requests. Chapter 4 already gave a simple (3, O(log n))-competitive routing algorithm as an illustration of the general…

2 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: mikedeng1

The Design of Competitive Online Algorithms via a Primal-Dual Approach III: Metrical Task Systems on a Weighted StarTextbook

The metrical task system (MTS) problem is one of the earliest and most general online models: a server occupies a state in a metric space, requests arrive with per-state service costs, and the server may change state (paying the metric's transition cost) before serving each request. On a general metric, competitive algorithms are hard to design directly.…

6 thms2 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·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 Design·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 Theory·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
CombinatoricsProbability·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
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
Captain: marwahaha

Every LTL formula has an equivalent finite-state Büchi automatonResearch Paper

For any type of atomic propositions and every linear temporal logic formula over it, there exists a nondeterministic Büchi automaton with a finite state type accepting exactly the same infinite words. The alphabet consists of sets of atomic propositions; no finiteness assumption on the atomic-proposition type is required.

1 thm1 active userReviewed
🏆Completed
Formal Verification·Captain: pitimespi

Bitcoin: Taproot script-path soundness as a reduction to SHA-256 and tweak collisionsTextbook

A Taproot output commits to a tree of scripts through its tweaked key, and a spender opens one leaf by presenting a control block: the internal key, a parity bit, and a Merkle path. The design claim of BIP341 is that nobody can open a leaf the output's creator did not put in the tree. The Taproot mission transcribed VerifyTaprootCommitment and the tagged…

9 thms1 active userReviewed
🏆Completed
Captain: marwahaha

Arrow’s theorem for Boolean voting rulesResearch Paper

A Boolean-valued voting rule is a function on the Hamming cube. This formalization proves that if the rule is unanimous and always admits a Condorcet winner, then it is a dictatorship.

3 thms1 active userReviewed
🏆Completed
Combinatorics·Captain: marwahaha

Chandra–Furst–Lipton: forbidden patterns for zero-sum evaluationResearch Paper

In the number-on-the-forehead communication model, each player sees every input coordinate except their own. The players send bits according to a shared protocol. This Lean library studies what the resulting transcript can distinguish when the function being evaluated tests whether the inputs sum to zero in an additive commutative group.

4 thms1 active userReviewed
🏆Completed
Captain: wurtle

A One-Sided Sublinear-Query Tester for Bounded-Degree 2SATResearch Paper

A 2SAT formula asks whether Boolean variables can be assigned values that satisfy every clause. Suppose the formula is too large to read in full, but a tester may ask which clause occupies a chosen incidence slot of a chosen variable. How many queries suffice to distinguish a satisfiable formula from one that requires many clause deletions?

4 thms1 active userReviewed
PreviousPage 22 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