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

251–275 of 491
Open91Completed491All582
🏆Completed
CombinatoricsOperations ResearchOptimization+2·Captain: mikedeng1

Maximizing Non-Monotone Submodular Functions I: A Uniformly Random Set Achieves 1/4 of the Optimum, and 1/2 for Symmetric FunctionsResearch Paper

Many combinatorial optimization problems ask for a subset of a finite ground set that maximizes a set function with diminishing returns: Max Cut and Max Directed Cut in graphs, facility location, maximum entropy sampling, and welfare problems in combinatorial auctions all fit this pattern. The common abstraction is the maximization of a submodular function,…

8 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Approximation Techniques for Average Completion Time Scheduling IV: List Scheduling from an Optimal One-Machine Schedule Is a 2-Approximation for In-TreesResearch Paper

Minimizing the sum of weighted completion times of jobs on identical parallel machines is one of the basic objectives of machine scheduling: it measures the average time a job spends in the system, weighted by its importance. When the jobs are subject to precedence constraints (a job may start only after certain other jobs have finished), the problem is…

6 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Approximation Techniques for Average Completion Time Scheduling III: From One Machine to Many with Delay ListResearch Paper

Minimizing the sum of weighted completion times ∑jwjCj\sum_j w_jC_j∑j​wj​Cj​ is one of the standard objectives of machine scheduling: it measures the average time a job spends in the system, weighted by its importance. With release dates or precedence constraints the problem is NP-hard already on one machine, and on mmm identical parallel machines it is harder still, so the…

12 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Approximation Techniques for Average Completion Time Scheduling II: A 2.83-Approximation for Parallel Machines with Release DatesResearch Paper

Minimizing the average completion time of jobs that arrive over time is a basic objective in machine scheduling. It measures how long a job spends in the system on average. With several identical machines, release dates and no preemption (written P∣rj∣∑CjP|r_j|\sum C_jP∣rj​∣∑Cj​), the problem is strongly NP-hard already on one machine. Research has therefore looked for…

11 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Local Search Heuristics for k-Median and Facility Location Problems IV: Local Search with Multi-Copy Moves for Capacitated Facility Location Has Locality Gap 4Research Paper

Facility location asks where to open service points (warehouses, plants, servers) and how to connect customers to them so that the total opening cost plus the total connection cost is minimum. In the capacitated version each facility can serve only a limited number of customers, which is the situation in most applications: a warehouse has a floor area, a…

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

Local Search Heuristics for k-Median and Facility Location Problems I: Single-Swap Local Search for k-Median Has Locality Gap 5Research Paper

The k-median problem asks where to open kkk facilities so that the total distance from a set of clients to their nearest open facility is as small as possible. It is a basic model of facility location in operations research (placing depots, warehouses or servers) and of clustering with representative centres, and it is NP-hard, so the question of interest is…

8 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

The Design of Competitive Online Algorithms via a Primal-Dual Approach VI: Maximizing Ad-Auctions RevenueTextbook

Search-engine ad-auctions sell items (ad slots) to buyers who arrive with per-item bids and a fixed daily budget, online: each item must be allocated the moment it appears, with no ability to revisit past allocations, and no buyer may ever be charged more than its budget. Buchbinder and Naor's survey [1] models this as a generalization of online bipartite…

8 thms3 active users
🏆Completed
Machine LearningOperations ResearchProbability+2·Captain: mikedeng1

Foundations of Machine Learning XIV: Finite Markov Decision Processes and Bellman's EquationsTextbook

Reinforcement learning formalizes a scenario supervised learning cannot: an agent that actively interacts with an environment, choosing actions that change both the state it observes next and the reward it receives, rather than passively receiving an i.i.d. labeled sample. Every practical treatment of this scenario — from classical dynamic programming to…

13 thms3 active usersReviewed
🏆Completed
Mathematical PhysicsQuantum InformationTheoretical Computer Science·Captain: LG

Undecidability of the Spectral GapResearch Paper

The spectral gap of a quantum many-body Hamiltonian is the difference between the energy of its ground state and the energy of its first excited state, in the limit of infinitely many particles. Whether a given microscopic interaction produces a gapped or a gapless system decides much of the macroscopic physics: gapped systems have exponentially decaying…

22 thms3 active usersReviewed
🏆Completed
Mechanism DesignTheoretical Computer Science·Captain: Shuze Chen

Algorithmic Game Theory IV: VCG and the Limits of TruthfulnessTextbook

Mission III of this series ends at an impossibility: without money, incentive compatibility over three or more alternatives means dictatorship. This mission formalizes the classical escape route — quasilinear utilities and payments — and the exact price of it. Vickrey (1961) discovered that a second-price auction makes truth-telling dominant; Clarke (1971)…

6 thms3 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: marwahaha

Asymmetric Hashing Square Bound: omega < 2.3747Research Paper

AI generated, I think it's correct

131 thms3 active usersReviewed
🏆Completed
Computational GeometryTheoretical Computer Science·Captain: wurtle

Generalization of Hinging PlanesResearch Paper

A continuous piecewise linear (CPWL) function is one assembled from finitely many flat pieces glued along flat seams. Every ReLU network computes such a function, and every such function is computed by some ReLU network. Questions about how deep a network must be are therefore questions about the internal structure of CPWL functions.

3 thms3 active users
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: marwahaha

Weighted-cache 3SUM refinement in O(n1.920279408185)O(n^{1.920279408185})O(n1.920279408185) timeResearch Paper

3SUM asks whether three distinct positions in an integer array hold values summing to zero. This mission imports Jionghan Wang's sharper weighted-cache refinement into the 3SUM Exponent campaign, improving the previously published exponent 1.920279421.920279421.92027942 to 1.9202794081851.9202794081851.920279408185.

4 thms2 active usersReviewed
🏆Completed
CombinatoricsMachine Learning·Captain: iris

Deep Sets: Over a Countable Universe, a Function of a Finite Set Is Permutation Invariant iff It Has the Form ρ(∑x∈Xϕ(x))\rho(\sum_{x\in X}\phi(x))ρ(∑x∈X​ϕ(x))Research Paper

Many learning problems take a set as input rather than a vector: a point cloud, the collection of words in a document, a group of users in an audience, a sample from a distribution. A model for such data must give the same answer however the elements of the set are listed. Deep Sets (Zaheer, Kottur, Ravanbakhsh, Póczos, Salakhutdinov, Smola,…

6 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchProbability+1·Captain: iris

Online Policies for Efficient Volunteer Crowdsourcing: The Sparse Notification Policy Is 12−q(1−1e)\frac{1}{2-q}(1-\frac{1}{e})2−q1​(1−e1​)-CompetitiveResearch Paper

Nonprofit crowdsourcing platforms rely on volunteers to perform time-sensitive tasks. On Food Rescue U.S., for example, a task is a scheduled pickup of a perishable donation, and when a task goes unclaimed the platform can push a notification to a subset of volunteers. Notifying more volunteers raises the chance that the current task gets done, but…

19 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: iris

Online Matching Frameworks under Stochastic Rewards, Product Ranking, and Unknown Patience: Greedy with a κ-Approximate Star-Graph Black Box Is κ/2-Competitive under Adversarial ArrivalsResearch Paper

Online bipartite matching, introduced by Karp, Vazirani and Vazirani (1990), models a platform that must assign arriving customers to a known stock of items, one customer at a time and irrevocably. In e-commerce, job search and online advertising, a recommendation is only a suggestion: a customer buys an offered item with some known probability, and after…

15 thms2 active usersReviewed
🏆Completed
Mathematical LogicTheoretical Computer ScienceType Theory·Captain: kmehltretter82

Type-Based Termination Checking in AgdaResearch Paper

A proof assistant based on type theory has to reject non-terminating definitions: a function that loops can inhabit any type, including the empty one, and so proves everything. Agda therefore checks every recursive definition for termination before accepting it. Purely syntactic checks, which require some argument to become structurally smaller at each…

30 thms2 active users
🏆Completed
Algorithmic Game TheoryCombinatoricsOperations Research+2·Captain: iris

Tight Approximation for Unconstrained XOS Maximization: Algorithm 4 Finds a (k−1)(k-1)(k−1)-Maximizer of Every kkk-XOS Function in O(k2n)O(k^2 n)O(k2n) Time, Exactly When k=2k=2k=2Research Paper

Maximizing a set function is a basic task in combinatorial optimization and algorithmic game theory. Computing an agent's demand under prices ppp amounts to maximizing v(X)−∑x∈Xpxv(X)-\sum_{x\in X}p_xv(X)−∑x∈X​px​, which need not be monotone even when the valuation vvv is. XOS functions generalize submodular functions, and they are studied in combinatorial auctions, where they are…

22 thms2 active usersReviewed
🏆Completed
Formal VerificationTheoretical Computer Science·Captain: pitimespi

Bitcoin: the Eyal-Sirer selfish-mining thresholdTextbook

Eyal and Sirer (2014) showed that a mining pool can earn more than its share of the hashrate by withholding blocks: the pool's revenue share under the selfish strategy exceeds α\alphaα exactly when α>(1−γ)/(3−2γ)\alpha > (1-\gamma)/(3-2\gamma)α>(1−γ)/(3−2γ), where γ\gammaγ is the fraction of honest hashrate that mines on the pool's block during a tie. The result is usually quoted as…

18 thms2 active usersReviewed
🏆Completed
Complexity Theory·Captain: marwahaha

Fourier and integer-convolution runtime transferTextbook

When a faster multiplication algorithm becomes available, its consequences depend on which problems reduce to multiplication and how the reduction changes input size. A displayed runtime bound alone does not identify this connection. The surrounding computation can also consume the improvement if its cost is omitted or underestimated.

22 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: marwahaha

3SUM below 1.921: deterministic exponent 1.9202796 on the word RAMResearch Paper

The 3SUM problem — does an integer array contain three values, at three distinct positions, that sum to zero — is a canonical benchmark of fine-grained complexity. Hundreds of reductions sit beneath it in the 3SUM-hardness lattice, so its worst-case exponent governs the reported complexity of convex-hull degeneracies, motion planning, and many…

2 thms2 active usersReviewed
🏆Completed
cryptographyInformation Theory·Captain: queelius

GBFPlus: disclosure from public occupancyResearch Paper

A data structure can hide each stored share individually while revealing their joint value through its visible layout. This distinction matters when a ledger publishes both a collection of shares and the markers identifying which cells were filled by genuine insertions. The GBFPlus protocol records cross-domain transfers in ledger attestations and uses a…

5 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchProbability+1·Captain: mikedeng1

The Power of Adaptivity for Stochastic Submodular Cover: With Independent Items, r Rounds of Adaptivity Achieve Expected Cost O(Q^{1/r} log Q) Times the Optimal Fully Adaptive CostResearch Paper

In many sequential decision problems an unknown quantity is revealed only when paid for: a medical test, a sensor reading, a database query. Stochastic submodular cover is the common abstraction: items are probed one at a time at a cost, each probe reveals a random outcome, and probing stops once the revealed outcomes jointly reach a coverage target. It…

14 thms2 active usersReviewed
🏆Completed
Graph TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Quasi-Polynomial Algorithms for Submodular Tree Orienteering and Other Directed Network Design Problems: Recursive Greedy Is an O(log k/log log k)-Approximation in (n log B)^O(log^(1+ε) k) TimeResearch Paper

Directed network design asks which connections can be bought under a limited budget when traffic follows the directions of arcs. In directed tree orienteering, the reward comes from vertices reached by a rooted directed tree. The submodular version allows the reward of a new vertex to depend on which vertices have already been reached. This captures…

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

A Polynomial Approximation Scheme for Scheduling on Uniform Processors: Using the Dual Approximation Approach: Binary Search over all-pack Is a (1 + ε)-Approximation for Makespan on Uniform MachinesResearch Paper

Scheduling independent jobs on machines that run at different speeds, so that the last job finishes as early as possible, is one of the basic problems of scheduling theory. In the classification of Graham, Lawler, Lenstra and Rinnooy Kan it is denoted Q∥Cmax⁡Q\|C_{\max}Q∥Cmax​, the minimum makespan problem on uniform parallel machines. It is strongly NP-hard, so the…

15 thms2 active usersReviewed
PreviousPage 11 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