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

426–450 of 491
Open91Completed491All582
🏆Completed
CombinatoricsGraph TheoryOperations Research+2·Captain: mikedeng1

An Analysis of Several Heuristics for the Traveling Salesman Problem IV: Insertion Heuristics Can Return Poor k-Optimal ToursResearch Paper

Insertion heuristics build a traveling salesman tour one city at a time: start from a single city, and at each step choose a city not yet on the subtour and splice it into the subtour where it lengthens the subtour least. Local search heuristics start from a tour and repeatedly replace a few of its edges by others while this shortens the tour. Both families…

14 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Approximation Algorithms for Combinatorial Problems III: The Worst-Case Ratio of the Weighted Algorithm B2Research Paper

MAXIMUM SATISFIABILITY asks for a truth assignment satisfying as many clauses of a given set as possible. It was among the first NP-hard optimization problems for which an approximation algorithm came with a proven worst-case guarantee. In Approximation Algorithms for Combinatorial Problems (J. Comput. System Sci. 9, 1974, doi:10.1016/S0022-0000(74)80044-9),…

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

An Analysis of Several Heuristics for the Traveling Salesman Problem III: Nearest and Cheapest Insertion Are Within a Factor of TwoResearch Paper

The traveling salesman problem (TSP) asks for a shortest closed route through a finite set of points. It is NP-hard, and in practice tours are built by fast constructive heuristics whose output is then improved or used as is. A central question in the analysis of algorithms, raised in this form by Rosenkrantz, Stearns and Lewis in 1977, is how far such a…

10 thms2 active usersReviewed
🏆Completed
Control TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Supervisory Control of a Class of Discrete Event Processes II: Every Reduced, Trim Supervisor Is the Quotient of a Supervisor Built on a Recognizer for Its Closed-Loop LanguageResearch Paper

Supervisory control theory, introduced by Ramadge and Wonham (SIAM J. Control Optim. 25(1), 1987), models a manufacturing cell, a communication protocol or a resource-sharing system as an automaton whose transitions are events, some of which an external controller may disable. A controller, the supervisor, is itself an automaton that watches the event…

15 thms2 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

A Faster Algorithm Computing String Edit Distances 2: Discrete Edit Costs Are NecessaryResearch Paper

The edit distance between two strings is the least total cost of a sequence of single-character insertions, deletions and replacements that turns one string into the other. It underlies spelling correction, sequence alignment in computational biology, and file comparison. Wagner and Fischer (J. ACM 21, 1974) computed it for strings of length nnn in time O(n2)O(n^2)O(n2)…

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

Maximizing Non-Monotone Submodular Functions III: Guarantees of Deterministic Local SearchResearch Paper

Many optimization problems ask for a subset of a finite ground set that maximizes a function with diminishing returns: the cut of a graph or a directed graph, the value of a facility-location configuration, the entropy of a set of random variables, or a welfare function in combinatorial auctions. These functions are submodular but typically non-monotone:…

14 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Local Search Heuristics for k-Median and Facility Location Problems II: p-Swap Local Search for k-Median Has Locality Gap 3 + 2/pResearch Paper

The k-median problem asks to open kkk facilities among a set of candidate sites so that the total distance from clients to their nearest open facility is as small as possible. It is a basic model of facility location and of clustering, and it is NP-hard, so the question studied in approximation algorithms is how close a polynomial-time method can get to the…

8 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear algebra+2·Captain: mikedeng1

Matching Is as Easy as Matrix Inversion: Steps 1–3 Find a Minimum Weight Perfect Matching with Probability at Least 1/2Research Paper

Deciding whether a graph has a perfect matching, and finding one, are basic problems of combinatorial optimization; Edmonds' blossom algorithm solves them sequentially in polynomial time. The question behind this paper is whether they can also be solved in parallel, in polylogarithmic time on polynomially many processors (the class NC, or RNC when random…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Approximation Algorithms for Combinatorial Problems IV: Greedy Set Cover C1 Has Worst-Case Ratio H(k) on SC(k)Research Paper

Set covering asks for the fewest members of a family of sets whose union is everything the family covers. It models crew scheduling, facility siting, test-suite reduction, logic minimization and fault testing; Johnson names the last two as its practical applications. Karp showed in 1972 that the decision version is NP-complete (Karp 1972), so in practice…

8 thms2 active usersReviewed
🏆Completed
Linear algebraNumerical AnalysisOptimization+1·Captain: mikedeng1

Sparse Approximate Solutions to Linear Systems 1: The Column Bound for Greedy SelectionResearch Paper

Many problems in scientific computing and statistics ask for a solution of a linear system Ax≈bAx\approx bAx≈b that uses as few unknowns as possible. In statistics this is subset selection (Golub and Van Loan, Matrix Computations, 1983). In coding theory over binary matrices it is the minimum weight solution problem (Gallager, 1968). Natarajan's own motivation was r…

12 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·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+1·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 ResearchOptimizationTheoretical Computer Science·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 TheoryTheoretical Computer Science·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+2·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 ProgrammingTheoretical Computer Science·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+1·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+1·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 ResearchOptimizationTheoretical Computer Science·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 TheoryTheoretical Computer Science·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+1·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 TheoryTheoretical Computer Science·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 ResearchTheoretical Computer Science·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 ResearchTheoretical Computer Science·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 ResearchTheoretical Computer Science·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
PreviousPage 18 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