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.

92 open missions

Missions

76–92 of 92
Open92Completed490All582
Computational ComplexityMachine Learning·Captain: Shuze Chen

Training a 3-node neural network is NP-complete: NP-completeness of exact training on Boolean inputsResearch Paper

Training a classifier asks for parameters that fit observed examples. Even when the data can be classified perfectly, the task of finding suitable parameters can have substantial computational cost. The question here concerns exact training: deciding whether any parameter choice makes zero mistakes on the entire supplied data set. It concerns computation on…

7 thms2 active usersReviewed
Algorithmic Game TheoryOperations ResearchProbability+1·Captain: iris

Prophet Matching with General Arrivals: a 0.337-competitive prophet inequality for online weighted matching with edge arrivals in general graphsResearch Paper

A prophet inequality compares an online decision maker, who sees random values one at a time and must accept or reject each irrevocably, with a "prophet" who sees all values in advance. The classical single-item version (Krengel–Sucheston, Samuel-Cahn) guarantees half of the prophet's expected value. Since the work of Hajiaghayi, Kleinberg and Sandholm…

19 thms2 active usersReviewed
CombinatoricsComplexity Theory·Captain: Shuze Chen

The Complexity of Clickomania: NP-completeness with five columns and three colorsResearch Paper

A puzzle can have simple local rules while the choice of moves has global consequences. Clickomania, also known as Same Game, is an example: a player removes adjacent blocks of one color, and the remaining blocks move into the vacated space. The computational question asks whether a given starting position can be cleared completely. Biedl, Demaine, Demaine,…

6 thms2 active usersReviewed
OptimizationQuantum InformationTheoretical Computer Science·Captain: mikedeng1

Optimizing Quantum Circuit Parameters via SDP: Algorithm 1 Is a 0.562-Approximation for Quantum Max CutResearch Paper

Quantum Max Cut asks for the highest energy of a two-qubit interaction Hamiltonian placed on the edges of a weighted graph. It is a quantum analogue of Max Cut: a classical cut assigns one of two labels to each vertex, while a quantum state can use correlations and entanglement across the qubits. Lee studies an approximation algorithm that first solves a…

13 thms2 active usersReviewed
Graph TheoryQuantum InformationTheoretical Computer Science·Captain: mikedeng1

Beyond product state approximations for a quantum analogue of Max Cut: Tensor Products of One- and Two-Qubit States Reach 0.55 of the Maximum Energy on Every Weighted GraphResearch Paper

Classical Max Cut asks for a partition of the vertices of a weighted graph that maximises the total weight of edges crossing it. Its best-known approximation algorithm, due to Goemans and Williamson, rounds a semidefinite relaxation and guarantees ratio 0.8780.8780.878. Quantum Max Cut is the analogous problem for a family of local Hamiltonians: each edge contributes…

12 thms2 active usersReviewed
ProbabilityQuantum InformationTheoretical Computer Science·Captain: mikedeng1

Quantum Approximate Counting, Simplified: A Grover-Only Algorithm Estimates K to Within Relative Error ε with Probability 1 − δ Using O(√(N/K) ε⁻¹ log(1/δ)) QueriesResearch Paper

Approximate counting asks for the number KKK of marked items in a list of NNN items, to within a multiplicative factor 1±ε1\pm\varepsilon1±ε, when the marked set can only be accessed through a membership oracle. Brassard, Høyer, Mosca and Tapp (arXiv:quant-ph/0005055) gave a quantum algorithm that uses O(N/K ε−1)O(\sqrt{N/K}\,\varepsilon^{-1})O(N/K​ε−1) queries, which is optimal. Their…

15 thms2 active usersReviewed
Linear algebraLinear OptimizationTheoretical Computer Science·Captain: mikedeng1

A Strongly Polynomial Algorithm for Linear Exchange Markets II: A Z₊-Matrix Polyhedron P_M Lies Between an M2VPI Polyhedron and Its Scaling by B²Research Paper

In a linear exchange market every agent owns one divisible good and has linear utilities over all goods; an equilibrium is a price vector at which every agent can spend its budget on goods that maximize utility per unit of money, and all goods are sold. Computing such an equilibrium in strongly polynomial time, with a number of arithmetic operations bounded…

11 thms2 active usersReviewed
Theoretical Computer Science·Captain: wurtle

Two WordRAM models: equivalence with polylogarithmic overheadTextbook

Prove equivalence between two WordRAM models: one with unsigned pointers, bit operations, and shifts; the other with signed pointers and branching on sign. Both support bounded-word arithmetic and multiplication.

16 thms2 active usersReviewed
Linear algebraNumerical AnalysisProbability+1·Captain: mikedeng1

Low Rank Approximation and Regression in Input Sparsity Time 1: A Sparse Embedding Matrix with O((r/ε)⁴ log²(r/ε)) Rows Is a (1 ± ε) Subspace Embedding for a Rank-r Matrix with Probability 9/10Research Paper

Many matrix algorithms spend most of their time reading their input. A matrix with few nonzero entries should admit routines whose cost scales with that number, rather than with the product of its dimensions. Clarkson and Woodruff study random maps that compress a matrix before a regression or low rank approximation calculation while retaining the geometric…

9 thms2 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: mikedeng1

Twin-width I: Tractable FO Model Checking 4: Every K_t-Minor-Free Graph Has Twin-width at Most 4c_g(t)·2^(4c_g(t)+2), a Triple-Exponential Bound in tResearch Paper

Many graph classes are defined by excluding a fixed graph as a minor. A minor can be formed by deleting vertices, deleting edges, and contracting edges. Planar graphs, for example, exclude K5K_5K5​ as a minor. Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant proved that every class excluding a fixed clique minor has bounded twin-width, a graph…

17 thms2 active usersReviewed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

Budgeted Prize-Collecting Traveling Salesman and Minimum Spanning Tree Problems: The Primal-Dual Upper Bound on the Optimal TourResearch Paper

Many routing problems come with a hard limit on distance or time rather than a requirement to visit everything. A repair crew with a fixed shift wants to service as many stations as possible; a vehicle with a fixed range wants to cover as many customers as possible. The budgeted prize-collecting traveling salesman problem captures this: given edge costs and…

7 thms2 active usersReviewed
CombinatoricsGraph TheoryOperations Research+2·Captain: mikedeng1

Linear-Time Approximation for Maximum Weight Matching: The Approximation Guarantee of the Scaling AlgorithmResearch Paper

The maximum weight matching (MWM) problem asks, for a graph with edge weights, for a set of vertex-disjoint edges of largest total weight. It is a central problem of combinatorial optimization, with applications to transportation, assignment and scheduling, and as a subroutine for shortest paths, planar max cut, Chinese postman tours and metric TSP.…

12 thms2 active usersReviewed
Quantum Information·Captain: marwahaha

A 0.4980.4980.498-approximation for Quantum Max-CutTextbook

Quantum Max-Cut asks for a high-energy state of an antiferromagnetic spin system specified by a weighted graph. Vertices carry qubits, and an edge rewards the two qubits for occupying their antisymmetric singlet state. A single qubit participates in several interactions, so maximizing each edge separately generally gives incompatible demands. The problem…

2 thms1 active userReviewed
Quantum Information·Captain: marwahaha

A 1/21/21/2-approximation for Quantum Max-CutTextbook

Quantum Max-Cut asks for a high-energy state of an antiferromagnetic spin system specified by a weighted graph. Vertices carry qubits, and an edge rewards the two qubits for occupying their antisymmetric singlet state. A single qubit participates in several interactions, so maximizing each edge separately generally gives incompatible demands. The problem…

3 thms1 active userReviewed
Discrete GeometryLinear OptimizationOperations Research+1·Captain: iris

On the Simplex Method for 0/1-Polytopes: The Ordered Shadow Pivot Rule Reaches an Optimal Solution in at Most d Non-degenerate PivotsResearch Paper

The simplex method moves between bases of a linear program, and its running time is governed by the pivot rule that picks the next basis. Whether some pivot rule needs only polynomially many pivots is a central open question in linear optimization. It is open even for 0/1-LPs, where the feasible region is a polytope whose vertices lie in {0,1}n\{0,1\}^n{0,1}n, although…

21 thms1 active userReviewed
CombinatoricsComplexity TheoryOperations Research+1·Captain: iris

Congruency-Constrained TU Problems Beyond the Bimodular Case: A Strongly Polynomial Randomized Algorithm for Feasibility of Totally Unimodular Integer Systems with a Congruency Constraint Modulo 3Research Paper

Integer linear programs min⁡{c⊤x:Ax≤b, x∈Zn}\min\{c^\top x : Ax\le b,\ x\in\mathbb Z^n\}min{c⊤x:Ax≤b, x∈Zn} are NP-hard in general, and one of the best-known tractable classes is the one where AAA is totally unimodular (TU): every square submatrix has determinant in {−1,0,1}\{-1,0,1\}{−1,0,1}. It is a long-standing open question whether integer programs with a Δ\DeltaΔ-modular constraint matrix (full column rank,…

24 thms1 active userReviewed
Theoretical Computer Science·Captain: Goku

QMA Strong Error Reduction with No Witness-Length IncreaseResearch Paper

A QMA verifier receives a quantum witness and checks it with a circuit generated efficiently from the input. An acceptance probability separated by an inverse-polynomial gap is enough to define the class, but applications often need the probability of a wrong answer to be exponentially small. Repeating the verifier on many supplied witness registers…

3 thms1 active userReviewed
PreviousPage 4 of 4Next

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