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

376–400 of 491
Open91Completed491All582
🏆Completed
Formal VerificationTheoretical Computer Science·Captain: mikedeng1

Reaching Agreement in the Presence of Faults 1: With n ≥ 3m + 1 Processors, the Recursive Majority Procedure on (m + 1)-Level Scenarios Assures Interactive Consistency for m FaultsResearch Paper

A fault-tolerant system often replicates a computation on several processors and needs the nonfaulty ones to act on the same data, even though some processors may fail in arbitrary ways: send wrong values, send different values to different recipients, or lie about what they were told. Pease, Shostak and Lamport posed the question in 1980, motivated by the…

7 thms2 active usersReviewed
🏆Completed
Machine LearningOperations ResearchProbability+1·Captain: mikedeng1

The Weighted Majority Algorithm 6: Under the Weak Independence Condition, the Randomized Master WMR Has E(m) ≤ E(ln(w_init/w_fin))/(1−β)Research Paper

Prediction with expert advice asks a learner to predict a binary label in each of a sequence of trials, having seen the predictions of a pool of nnn prediction algorithms (the experts), and to make not many more mistakes than the best of them, with no probabilistic assumption on how the instances and labels are generated. Littlestone and Warmuth's Weighted…

3 thms2 active usersReviewed
🏆Completed
Machine LearningOperations ResearchTheoretical Computer Science·Captain: mikedeng1

The Weighted Majority Algorithm 3: On a Countably Infinite Pool, WMI2 Makes at Most inf_i (log(Ŵ(1)/W(i)) + m_i log(1/β) + log 2)/log(1/u) MistakesResearch Paper

In prediction with expert advice, a master algorithm predicts a binary label in each of a sequence of trials, after seeing the predictions of a pool of other algorithms (the "experts"), and is charged one mistake whenever its prediction differs from the label. No probabilistic assumption is made on the sequence: the goal is a bound on the master's mistakes,…

4 thms2 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: xuanji

Deterministic APSP in O(n^2.99791) time on a Word RAMResearch Paper

All-pairs shortest paths (APSP) asks for the exact distance between every ordered pair of vertices in an nnn-vertex weighted directed graph. Floyd–Warshall solves it in O(n3)O(n^3)O(n3) time, and for decades no algorithm beat n3−δn^{3-\delta}n3−δ for any constant δ>0\delta>0δ>0 on graphs with polynomially bounded integer weights. The APSP conjecture of fine-grained complexity…

5 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization+2·Captain: mikedeng1

Approximation Algorithms for Scheduling Unrelated Parallel Machines 1: Binary Search over Rounded LP Vertices Finds a Schedule within Twice the Optimal MakespanResearch Paper

Scheduling unrelated parallel machines to minimize the makespan, written R ∥ Cmax⁡R\,\|\,C_{\max}R∥Cmax​, is one of the basic NP-hard problems of scheduling theory. A set of jobs must each be run on one of several machines, and the time a job takes depends arbitrarily on the machine; the goal is to finish all jobs as early as possible. Before the work formalized here, the…

11 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Flowshop and Jobshop Schedules: Complexity and Approximation 6: Concatenating Optimal Schedules of Processor Pairs Gives Finish Time within ⌈m/2⌉ Times the OptimumResearch Paper

A flow shop is the simplest model of a production line: every job passes through the same sequence of machines in the same order. Minimizing the time at which the last job leaves the last machine (the finish time, or makespan) is easy for two machines, where Johnson's rule gives an optimal schedule in time O(nlog⁡n)O(n\log n)O(nlogn) (Johnson 1954), and NP-hard from three…

7 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Flowshop and Jobshop Schedules: Complexity and Approximation 5: Sequencing Jobs by Shortest Total Processing Time Gives Mean Flow Time within m Times the OptimumResearch Paper

Flow shops and job shops are the basic models of multi-stage production: every job passes through several machines, and each machine handles one task at a time. Gonzalez and Sahni (Operations Research 26(1), 1978) showed that minimizing the finish time of such shops is NP-complete even with preemption, and then asked how well simple heuristics do. One of…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Flowshop and Jobshop Schedules: Complexity and Approximation 4: The 3-Partition Job Shop on Two Machines Has a Schedule of Finish Time 2tB, Preemptive or Not, Iff a 3-Partition ExistsResearch Paper

In a job shop, each job has an ordered list of tasks, and each task must use a specified machine. A production planner may be able to interrupt a task and resume it later, yet still be unable to find a short schedule efficiently. Gonzalez and Sahni studied how the ability to preempt changes the difficulty of minimizing the time at which all jobs are…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Flowshop and Jobshop Schedules: Complexity and Approximation 1: The Partition Flow Shop on Three Machines Has a Schedule of Finish Time 2T, Preemptive or Not, Iff a Partition ExistsResearch Paper

Shop scheduling asks how to process a set of jobs, each a sequence of tasks on prescribed machines, so that all work is completed as early as possible. The flow shop, in which every job visits the machines in the same order, is the most studied of these models in operations research. For two machines, Johnson's rule (1954) computes a schedule of minimum…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Bounds on Multiprocessing Timing Anomalies 1: Changing the List, Relaxing the Order, Shortening the Tasks and Using n′ Processors Multiplies the Finishing Time by at Most 1 + (n − 1)/n′Research Paper

Scheduling work on several identical processors creates a plausible expectation: completing tasks sooner, removing constraints, or adding a processor should not delay the overall finish. A fixed priority-list rule defeats that expectation. When a task becomes ready earlier, it can occupy a processor that would otherwise have run another task; that decision…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Bounds on Multiprocessing Timing Anomalies 2: Scheduling the k Longest Independent Tasks Optimally First Gives ω(k)/ω₀ ≤ 1 + (1 − 1/n)/(1 + ⌊k/n⌋)Research Paper

Parallel processing poses a basic allocation question: given tasks of known lengths and several identical processors, how much time is lost when tasks are assigned by a simple list rule instead of an optimal allocation? The finishing time is the moment the last processor completes its work. For independent tasks, a list rule starts each next task on a…

8 thms2 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: marwahaha

Truly Subquadratic 3SUM on a Word RAMResearch Paper

3SUM asks whether three distinct positions in a list of integers contain values summing to zero. It is a central problem in fine-grained complexity.

60 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Fibonacci Heaps and Their Uses in Improved Network Optimization Algorithms: O(log n) Amortized Time for Delete Min and Delete, O(1) for Every Other F-Heap OperationResearch Paper

Many network optimization algorithms spend most of their time in a heap (priority queue): a set of items with real keys that supports inserting an item, finding and deleting an item of minimum key, melding two heaps, decreasing the key of an item, and deleting an arbitrary item. Dijkstra's shortest-path algorithm performs at most one delete min per vertex…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: wurtle

Truly Subcubic APSP on a Word RAMResearch Paper

All-pairs shortest paths (APSP) computes the shortest distance between every pair of vertices in a weighted graph. It is a fundamental problem in graph algorithms and a fundamental problem in fine-grained complexity.

61 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Approximation Algorithms for Scheduling Unrelated Parallel Machines 3: On the 3-Dimensional Matching Instances, a Schedule within ρ < 3/2 of Optimal Has Makespan ≤ 2 Iff a Matching ExistsResearch Paper

Minimum makespan scheduling on unrelated parallel machines, written R ∣∣ Cmax⁡R\,||\,C_{\max}R∣∣Cmax​, is one of the basic models of scheduling theory: nnn jobs must each be run on one of mmm machines, and the time a job takes depends arbitrarily on the machine. Lenstra, Shmoys and Tardos (CWI Report OS-R8714, 1987; journal version Math. Programming 46, 1990) gave a polynomial…

8 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Approximation Algorithms for Scheduling Unrelated Parallel Machines 4: With Times in {p, q} and gcd(p, q) = 1, a q-Dimensional Matching Exists Iff a Schedule Has Makespan ≤ pqResearch Paper

Minimum makespan scheduling on unrelated parallel machines asks for an assignment of nnn jobs to mmm machines, where job jjj takes pijp_{ij}pij​ time units on machine iii, so that the largest machine load is as small as possible. In the three-field notation of Graham, Lawler, Lenstra and Rinnooy Kan (1979) it is R ∥ Cmax⁡R\,\|\,C_{\max}R∥Cmax​. It models load balancing across…

7 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryCombinatoricsOperations Research+2·Captain: mikedeng1

Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments V: Stackelberg Matroid Pricing Is an Assortment Problem Under a Regular Choice ModelResearch Paper

In Stackelberg network pricing a leader sets prices on some resources, and a follower then buys the cheapest structure available to them, paying the leader for the priced resources they use. The Stackelberg Minimum Spanning Tree problem, introduced by Cardinal, Demaine, Fiorini, Joret, Langerman, Newman and Weimann (Algorithmica 2011), is the version in…

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

Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments III: The Three Revenue-Ordered Approximation Bounds Are TightResearch Paper

A retailer or an airline chooses which products to offer, and customers choose among what is offered, or buy nothing. Choosing the offer set that maximizes expected revenue is the assortment problem, central to revenue management (Talluri and van Ryzin, 2004). It is NP-hard even for simple mixtures of logit models, so practice relies on heuristics. The most…

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

Assortment Optimisation Under a General Discrete Choice Model: A Tight Analysis of Revenue-Ordered Assortments II: Revenue-Ordered Assortments Earn OPT/(1 + ln ν), ν the Optimum's Purchase RatioResearch Paper

A retailer that can display only some of its products must choose an assortment: the set of products offered to an arriving customer. Customers substitute: whether a given product is bought depends on what else is on the shelf. The assortment problem asks for the offer set that maximises expected revenue under a model of this substitution behaviour. It is a…

9 thms2 active usersReviewed
🏆Completed
Formal VerificationTheoretical Computer Science·Captain: mikedeng1

Consensus in the Presence of Partial Synchrony II: With Synchronous Processors, Partially Synchronous Communication and t Fail-Stop Faults, No Consensus Protocol Exists When 2 ≤ N ≤ 2tResearch Paper

Consensus asks NNN processors, each holding an initial value, to agree on one value despite some of them failing. It underlies replicated databases, atomic commit and state-machine replication. Its solvability depends on the timing assumptions. With fully synchronous processors and communication, ttt fail-stop faults can be tolerated for any t<Nt < Nt<N. With fully…

5 thms2 active usersReviewed
🏆Completed
Formal VerificationTheoretical Computer Science·Captain: mikedeng1

Consensus in the Presence of Partial Synchrony I: For N ≥ 2t + 1, Algorithm 1 Achieves Consistency, Strong Unanimity and Termination in the Basic Round Model with Fail-Stop or Omission FaultsResearch Paper

Consensus asks NNN processors, each starting with a value, to agree on one value although some of them may be faulty. It underlies replicated databases, atomic commitment and state-machine replication. Two classical models bracket the problem. In a fully synchronous system, with known bounds on message delay and processor speed, consensus is solvable for many…

6 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Approximation Algorithms for Precedence-Constrained Scheduling Problems on Parallel Machines That Run at Different Speeds: A min{K + 2√K + 1, 1.89 log m + O(√log m)}-Approximation for Q|prec|CmaxResearch Paper

Graham (1966) showed that list scheduling finds a schedule within a factor 222 of optimal for precedence-constrained jobs on identical parallel machines, the first performance guarantee for an approximation algorithm. When the machines run at different speeds (uniformly related machines), the same analysis breaks down, and for two decades the problem …

16 thms2 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Online Primal-Dual Algorithms for Covering and Packing 4: Online Rounding of the Fractional Routing Scheme Respects Capacities and Is O(log P(max)·[exp(1 + 2 ln m/u(min)) − 1])-CompetitiveResearch Paper

In online routing of virtual circuits, connection requests between pairs of nodes of a capacitated network arrive one at a time. Each request must be accepted and routed on a single path with bandwidth 111, or rejected, immediately and irrevocably, and no edge may carry more than its capacity. The goal is to maximize the number of accepted requests (the…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsMachine LearningTheoretical Computer Science·Captain: mikedeng1

A Characterization of Multiclass Learnability 1: Classes of Finite DS Dimension Have n → r Sample Compression Schemes with r Polylogarithmic in nResearch Paper

In multiclass classification a learner sees examples (x,y)(x, y)(x,y) with xxx in a domain X\mathcal XX and a label yyy in a set Y\mathcal YY, and must predict labels of new points. When Y\mathcal YY is finite, the Natarajan dimension characterizes PAC learnability, extending the role of the VC dimension in binary classification (Natarajan 1989; Ben-David, Cesa-Bianchi,…

20 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

On the Approximability of Single-Machine Scheduling with Precedence Constraints 6: The Optimal Value of S_G Lies Between n² − an²(ln 1/a + 2) and n² − an²Research Paper

The problem 1 ∣ prec ∣ ∑wjCj1\,|\,\mathrm{prec}\,|\,\sum w_jC_j1∣prec∣∑wj​Cj​ asks for a single-machine sequence of jobs, respecting precedence constraints, that minimizes the weighted sum of completion times. It has been known to be strongly NP-hard since Lawler (1978) and Lenstra and Rinnooy Kan (1978), several different 2-approximation algorithms are known, and closing the…

8 thms2 active usersReviewed
PreviousPage 16 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