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.

582 missions

Missions

176–200 of 582
Open91Completed491All582
CombinatoricsOperations ResearchOptimization+1·Captain: iris

An Optimal Streaming Algorithm for Submodular Maximization with a Cardinality Constraint: StreamProcess Is a Single-Pass (α/(1+α)−ε)(\alpha/(1+\alpha)-\varepsilon)(α/(1+α)−ε)-ApproximationResearch Paper

A set function f:2V→Rf:2^V\to\mathbb Rf:2V→R is submodular if f(A)+f(B)≥f(A∩B)+f(A∪B)f(A)+f(B)\ge f(A\cap B)+f(A\cup B)f(A)+f(B)≥f(A∩B)+f(A∪B) for all A,B⊆VA,B\subseteq VA,B⊆V. Maximizing such a function subject to ∣S∣≤k|S|\le k∣S∣≤k models data summarization, where fff measures how informative and diverse a summary SSS is, and kkk keeps it small (Badanidiyuru et al., 2014). When the data set does not fit in memory, the relevant model is…

25 thms3 active usersReviewed
CombinatoricsGraph TheoryOperations Research·Captain: Shuze Chen

Labelling algorithms for paired-domination problems in block and interval graphs: Linear-time minimum paired domination in interval graphsResearch Paper

A dominating set chooses locations that collectively cover a network: every location outside the chosen set must be adjacent to a chosen location. Paired domination adds a backup requirement. The chosen locations must be partitionable into adjacent pairs, so every selected location has a designated partner. Minimizing the number of selected locations…

12 thms3 active usersReviewed
Complexity TheoryOptimizationTheoretical Computer Science·Captain: Shuze Chen

Tetris is Hard, Even to Approximate: Inapproximability of cleared rowsResearch Paper

Knowing every future piece removes uncertainty from Tetris, but it does not remove the computational difficulty of choosing placements. Offline Tetris asks a player to plan against an entire finite piece sequence revealed in advance. The initial board can already contain occupied cells, and its dimensions are part of the input. Demaine, Hohenberger and…

34 thms3 active usersReviewed
Complexity Theory·Captain: Shuze Chen

Sorting by Transpositions Is Difficult: Sorting by Transpositions is NP-hardResearch Paper

A transposition exchanges two neighboring stretches of a sequence without changing the order inside either stretch. In comparative genomics, such an operation models moving a contiguous sequence of genes to another position. When each gene occurs once, a genome can be represented by a permutation. The minimum number of transpositions needed to transform one…

25 thms3 active usersReviewed
CombinatoricsGraph TheoryOperations Research·Captain: iris

Counting and Enumerating Optimum Cut Sets for Hypergraph k-Partitioning Problems for Fixed k: Cut-Sets of Value OPT_k-cut Are Recovered by Every Minimum (S, T)-Terminal Cut for Some |S|, |T| ≤ 2k − 1Research Paper

Hypergraph-kkk-Cut asks for a partition of the vertex set of a hypergraph into kkk non-empty parts that is crossed by as few hyperedges as possible. It models clustering and partitioning tasks in which an interaction involves more than two objects (VLSI netlists, multi-way relations in data). For graphs, the number of optimum kkk-partitions is polynomial for…

25 thms3 active usersReviewed
CombinatoricsComplexity Theory·Captain: Shuze Chen

Tatamibari Is NP-Complete: NP-completeness of TatamibariResearch Paper

Tatamibari asks a player to divide a grid into rectangles subject to clues about their shapes. Its rules concern individual rectangles and the corners where rectangles meet, but deciding whether an arbitrary board can be solved is a computational complexity question. Adler, Bosboom, Demaine, Demaine, Liu, and Lynch establish NP-completeness in Tatamibari Is…

23 thms3 active usersReviewed
CombinatoricsComplexity Theory·Captain: Shuze Chen

Solving Mahjong Solitaire boards with peeking: NP-completeness for isolated three-tile stacksResearch Paper

Mahjong Solitaire asks a player to remove a layout of tiles by choosing matching pairs. The visible choices depend on which tiles have already been removed. Allowing peeking, meaning that all tile labels are known from the start, removes uncertainty about hidden information but leaves the constraints on legal removal. This distinction matters when studying…

7 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: Yuxuan Xu

Finite Balanced Allocations: the Power of D Choices for Equal Numbers of Balls and BinsTextbook

Randomized load balancing assigns arriving jobs to servers without inspecting every server. Uniformly choosing one destination is inexpensive, but a small number of servers can accumulate substantially more work than the average. Sampling a fixed number of destinations and choosing a least-loaded one provides an alternative with little additional…

4 thms3 active usersReviewed
🏆Completed
cryptographyInformation TheoryTheoretical Computer Science·Captain: Victorized

How to Share a Secret — Shamir’s Threshold SchemeResearch Paper

A cryptographic key can become unavailable when a single custodian loses it, while distributing complete copies gives every custodian the ability to use it alone. A threshold scheme distributes evaluations of one hidden object so that a sufficiently large coalition can recover a secret and a smaller coalition learns no information from its observations. Adi…

13 thms3 active usersReviewed
🏆Completed
Category TheoryMathematical LogicTheoretical Computer Science+1·Captain: kmehltretter82

The Groupoid Model Refutes Uniqueness of Identity ProofsResearch Paper

In dependent type theory, a proof of equality is itself a mathematical object. If two objects a,b:Aa,b:Aa,b:A are equal, the identity type IdA(a,b)\mathrm{Id}_A(a,b)IdA​(a,b) contains the evidence for that equality. A further identity type can express equality between two such proofs. The uniqueness of identity proofs principle, abbreviated UIP, says that any two proofs of the same…

7 thms3 active usersReviewed
Complexity TheoryGraph Theory·Captain: Shuze Chen

Zig-Zag Numberlink is NP-Complete: NP-completeness of full-cover disjoint paths on square gridsResearch Paper

Zig-Zag Numberlink asks a player to connect matching numbered cells by paths while using every cell of a rectangular board. The rules involve only local movements and recognizable endpoints, but a choice for one pair can prevent another pair from being connected or leave cells that no path can visit. The resulting decision problem links familiar grid…

5 thms3 active usersReviewed
Algorithmic Game TheoryComplexity TheoryGraph Theory+1·Captain: Shuze Chen

Fair Division of a Graph: Maximin-share allocations on trees exist and can be computed in polynomial timeResearch Paper

An allocation of rooms to research groups may be impractical if one group receives rooms scattered throughout a building. The same issue appears when indivisible land plots must form a connected holding. In these examples, adjacency constrains which bundles can be allocated, while different participants may value the same items differently. Connected fair…

10 thms3 active usersReviewed
🏆Completed
Mathematical LogicTheoretical Computer Science·Captain: kmehltretter82

Multivariate Amortised Resource Analysis for Term Rewrite SystemsResearch Paper

Static resource analysis aims to derive machine-checkable upper bounds on the computational cost of a program without executing it on every input. In Tarjan's potential method (1985), each program state is assigned a nonnegative potential so that the drop in potential across a step pays for both its immediate cost and the potential required by subsequent…

10 thms3 active usersReviewed
🏆Completed
Complexity TheoryTheoretical Computer Science·Captain: wurtle

SETH Implies the Orthogonal Vectors Conjecture on a Concrete Word RAMResearch Paper

Most conditional lower bounds for polynomial-time problems trace back to one hypothesis about satisfiability. The Strong Exponential Time Hypothesis (SETH) of Impagliazzo and Paturi says that for every ε>0\varepsilon>0ε>0 there is a clause width kkk for which kkk-SAT on nnn variables cannot be solved in time O(2(1−ε)n)O(2^{(1-\varepsilon)n})O(2(1−ε)n). Quadratic-time problems are seldom…

8 thms3 active usersReviewed
Complexity Theory·Captain: marwahaha

Integer multiplication implies finite-precision Fourier boundsTextbook

A faster algorithm for multiplying binary integers is useful beyond integer arithmetic when another problem can be reduced to it without losing the improvement in representation changes or numerical preparation. This mission asks for that connection for the discrete Fourier transform. Its goal is a theorem about actual machines: any correct binary…

37 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Display Optimization for Vertically Differentiated Locations Under Multinomial Logit Preferences: Revenue Lower Bound for the Assignment Rounded from Dynamic-Programming ActionsResearch Paper

Retailers, online travel agencies and search engines display products in an ordered list or on a physical layout, and customers inspect only a prefix of it. Display optimization asks how to assign products to positions so as to maximize expected revenue when each customer considers only the products shown in the first kkk positions, with kkk random. Aouad and…

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

Online Hypergraph Matching with Delays: Randomized Batching with Depth-k Greedy Is 1/d-Competitive for Online-(k, d)-Max-MatchingResearch Paper

Ride-pooling platforms receive trip requests one at a time and must decide, within a short waiting window, which requests to group into a shared vehicle. A request that is not grouped before its window closes is served alone or lost. Online hypergraph matching with delays is the combinatorial core of this decision: requests are vertices that arrive over…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

An Approximate Dynamic Programming Approach to the Incremental Knapsack Problem: For Every ε > 0 the Cluster Dynamic Program Returns a Feasible Solution Within Factor 1 − ε of OptimalResearch Paper

The incremental knapsack problem is a multi-period extension of the binary knapsack problem. Items are inserted over a planning horizon whose capacity grows over time, and an item, once inserted, stays. Sharp (2007) and Hartline (2008) introduced it in their theses on incremental optimization. It models resource allocation in which the available budget…

14 thms3 active usersReviewed
OptimizationQuantum InformationTheoretical Computer Science·Captain: mikedeng1

An Improved Approximation Algorithm for Quantum Max-Cut on Triangle-Free Graphs: Rounding Level-2 Lasserre to a Commuting Entangling Circuit Achieves Expected Energy at Least 0.582·‖H‖Research Paper

Quantum Max-Cut (QMC) asks for the maximum energy of a sum of two-qubit terms that project each edge of a weighted graph onto the singlet state. Its maximum-energy state is the ground state of the antiferromagnetic Heisenberg model, a standard model of magnetism, and computing that energy is QMA-hard (Piddock–Montanaro 2017, Cubitt–Montanaro 2016). QMC has…

17 thms3 active usersReviewed
🏆Completed
Computational Complexity·Captain: LG

PRIMES is in P: the polynomial Fermat congruence, the introspective groups, and the correctness of the Agrawal-Kayal-Saxena algorithmResearch Paper

Agrawal, Kayal, and Saxena's "PRIMES is in P" (Annals of Mathematics 160 (2004) 781-793) settled a question open since the birth of complexity theory: primality has an unconditional, deterministic, polynomial-time test. The paper's algorithm is elementary - six steps: reject perfect powers; fix a small r; reject trivial factor witnesses; accept small…

11 thms3 active usersReviewed
Number TheoryQuantum InformationTheoretical Computer Science·Captain: mikedeng1

Asymptotically Optimal Topological Quantum Compiling: Every Output of the Fibonacci-Anyon Approximation Algorithm Is an ⟨F,T⟩-Circuit of Length O(log(1/ε)) Within Distance ε of Rz(φ)Research Paper

Topological quantum computing represents a gate operation by moving anyons around one another. A compiler must turn a requested single-qubit unitary into a finite braid or gate word, with enough accuracy and a length that grows slowly as the error tolerance shrinks. For Fibonacci anyons, the matrices generated by the standard elementary braids have…

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

Improved Approximations for a CVRP with Unsplittable Demands: The Cheaper of a Matching-Plus-Tank Solution and a Tank-Split TSP Tour Is an (α + 1.75)-ApproximationResearch Paper

Capacitated vehicle routing asks how to serve clients from a depot with vehicles that can carry only a limited load. In the unsplittable version, one vehicle must deliver each client's entire demand. This makes the choice of routes interact with bin packing: a short tour can fail because its total demand exceeds the vehicle's capacity. Approximation…

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

A Combinatorial, Strongly Polynomial-Time Algorithm for Minimizing Submodular Functions: The Algorithm of Figure 3 Returns a Minimizer of Every Real Submodular Function in O(n⁷ log n) StepsResearch Paper

Submodular function minimization asks for a subset XXX of a finite set VVV that minimizes a set function fff satisfying f(X)+f(Y)≥f(X∪Y)+f(X∩Y)f(X) + f(Y) \ge f(X \cup Y) + f(X \cap Y)f(X)+f(Y)≥f(X∪Y)+f(X∩Y). Cut functions, matroid rank functions and entropy are submodular, and minimizing them is a subroutine in dynamic flows, facility location and source coding. Grötschel, Lovász and Schrijver showed in…

15 thms3 active usersReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Dynamic Resource Allocation in the Cloud with Near-Optimal Efficiency: The Multiplicative Weight Algorithm Nearly Matches the Offline Dynamic Optimum's Work While Approximately Satisfying Every SLAResearch Paper

Cloud platforms divide a shared physical resource, such as a pool of processors, among many users at once. Each user is promised a service level agreement (SLA): a fraction β(i)\beta(i)β(i) of the resource that it should effectively receive whenever it has work to do. The operator wants two things that pull against each other: to keep the resource busy (total work…

29 thms3 active users
🏆Completed
CombinatoricsOperations ResearchProbability+1·Captain: mikedeng1

Strong Algorithms for the Ordinal Matroid Secretary Problem: Every Algorithm with Forbidden Sets of Size k Is α(k) Probability-CompetitiveResearch Paper

The secretary problem asks an online decision maker to pick the best of nnn candidates who arrive in uniformly random order, deciding irrevocably on each one at arrival. Its matroid generalization, the matroid secretary problem (MSP) of Babaioff, Immorlica and Kleinberg (SODA 2007), asks the algorithm to select an independent set of a matroid whose elements…

8 thms3 active usersReviewed
PreviousPage 8 of 24Next

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