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

76–100 of 582
Open92Completed490All582
🏆Completed
CombinatoricsGraph TheoryOptimization·Captain: iris

Finding Hall Blockers by Matrix Scaling: without a perfect matching, (1/4)n² log(mA_max/A_min) Sinkhorn iterations and a sort of the scaling vectors output a Hall blockerResearch Paper

Matrix scaling asks for positive diagonal matrices that turn a nonnegative matrix into one with prescribed row and column sums. The Sinkhorn algorithm, which alternately normalizes rows and columns, is the standard method; it appears in statistics (iterative proportional fitting), entropic optimal transport, and combinatorial optimization. For the doubly…

16 thms4 active usersReviewed
CombinatoricsComplexity Theory·Captain: Shuze Chen

Hard Tiling Problems with Simple Tiles: Decision and counting completeness for right trominoes and square tetrominoesResearch Paper

A tiling problem asks whether copies of a few shapes can cover a specified region without overlap or gaps. Even when the shapes are small and fixed in advance, the region can encode a substantial combinatorial constraint. This makes tiling a useful setting for distinguishing local geometric simplicity from computational tractability. It also separates two…

11 thms4 active usersReviewed
Complexity TheoryComputational Geometry·Captain: Shuze Chen

Terrain Guarding is NP-Hard: NP-hardness of discrete and continuous terrain guardingResearch Paper

Selecting a small collection of sites with line of sight to an entire landscape is a geometric coverage problem. In the one-dimensional terrain model, the landscape is represented by a polygonal profile in the plane. The optimization question asks how many guards are needed to see every point of that profile. Applications motivating the model include road…

10 thms4 active usersReviewed
Algorithmic Game TheoryCombinatoricsOperations Research·Captain: iris

Efficient Black-Box Reductions for Separable Cost Sharing: In Matroid Games with Subadditive Costs, Algorithm 1 Turns Any Profile into a No Costlier Enforceable Profile Within n·m·rk IterationsResearch Paper

In a cost sharing game each player chooses a set of resources, and the cost of every resource has to be divided among the players who use it. A designer who wants a cheap outcome to be stable chooses the division rule, the cost sharing protocol, so that the cheap outcome becomes a pure Nash equilibrium. Practical protocols should be separable: the share a…

13 thms4 active usersReviewed
Algorithmic Game TheoryAnalysisOperations Research·Captain: iris

Existence and Complexity of Approximate Equilibria in Weighted Congestion Games: Polynomial Games of Degree d With No α-PNE for Any α < α(d), Where α(d) ≥ √d/(2 ln d) for Large dResearch Paper

Weighted congestion games model players of different sizes sharing resources whose cost grows with load: traffic of different volumes on network links, jobs of different lengths on machines. Rosenthal (1973) showed that unweighted congestion games always have a pure Nash equilibrium, but weighted games may have none, already with polynomial costs. The…

28 thms4 active usersReviewed
Operations Research·Captain: Shuze Chen

Dynamic Stochastic Matching Under Limited Time: Constant-factor reward approximation on arbitrary and bipartite graphsResearch Paper

A matching platform must decide whether to pair available agents now or wait for a more valuable partner. Waiting creates an opportunity and a risk: an agent may leave before that partner arrives. Ride sharing, service exchanges and matching markets motivate models in which arrivals continue indefinitely and departure times are not announced in advance. A…

23 thms4 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: Shuze Chen

Online Matching and Ad Allocation: MSVV attains the optimal small-bids competitive ratioResearch Paper

An advertising platform must decide which advertiser receives each arriving opportunity before it knows what will arrive later. A bidder offering a high payment now may also be the only bidder interested in a later request. Spending that bidder’s budget immediately can therefore reduce the total money collected over the day. This tension is the Adwords…

16 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

Minimum Label s-t Cut has Large Integrality Gaps: Nearly cube-root integrality gap for the strengthened relaxationResearch Paper

A network failure can remove several connections at once. When the connections share a physical resource, paying for or disabling that resource acts on an entire class of edges. The minimum label s-t cut problem captures this distinction: edges carry labels, and the cost of removing a label is paid once, regardless of how many edges have that label. Zhang…

14 thms4 active usersReviewed
Complexity TheoryComputational Geometry·Captain: Shuze Chen

Orthogonal Terrain Guarding is NP-complete: NP-completeness of orthogonal terrain guardingResearch Paper

Terrain guarding asks how many observation sites are needed to see an entire landscape represented by a polygonal chain. The input specifies both the terrain and the number of guards available. A solution chooses observation sites whose combined visibility covers the whole landscape. Restricting the chain to horizontal and vertical edges simplifies its…

6 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryComputational ComplexityOperations Research·Captain: Shuze Chen

When Are Elections with Few Candidates Hard to Manipulate?: Non-plurality positional scoring is NP-complete to manipulate with three candidatesResearch Paper

A voting rule aggregates submitted preferences into a collective choice. A coalition can sometimes change that choice by coordinating its submitted rankings. The computational question is whether it can efficiently determine how to make a particular candidate win. This matters in collective decision systems where an agent's voting weight can represent…

6 thms4 active usersReviewed
🏆Completed
Operations ResearchStochastic SystemsTheoretical Computer Science·Captain: mikedeng1

Tail-Optimized Caching for LLM Inference: Expected-Tail-Optimized LRU Is an Optimal Online Caching Policy for Tail Excess Latency in the Stochastic Conversation ModelResearch Paper

A large language model serving a multi-turn conversation re-reads the whole conversation history at every turn. The intermediate attention state of that history, the KV cache, can be stored in GPU memory and reused, so that only the uncached part of the prompt must be recomputed before the first output token appears. GPU memory is scarce, so a server must…

8 thms4 active usersReviewed
🏆Completed
Group TheoryQuantum InformationTheoretical Computer Science·Captain: mikedeng1

The Solovay-Kitaev algorithm: every gate in SU(d) is ε-approximated by a sequence of O(log^{ln 5/ln(3/2)}(1/ε)) gates from any instruction setResearch Paper

A quantum computer executes a fixed, finite instruction set of gates, while quantum algorithms are written with arbitrary gates. Every algorithm must therefore be compiled: each gate UUU is replaced by a sequence of available instructions whose product approximates UUU. If an accuracy δ\deltaδ required sequences of length O(1/δ)O(1/\delta)O(1/δ), compiling an mmm-gate…

14 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Pipeline Interventions: The Budget-Splitting Dynamic Program over an ε-Net of the Simplex Attains Social Welfare at Least OPT − 3(k−1)ε‖R‖∞Research Paper

Many consequential outcomes (a faculty position, a high-paying job) are the end of a long pipeline of earlier stages: neighbourhood, elementary school, high school, college, graduate school. Inequities that compound along such a pipeline are hard to correct by intervening only at its last stage, and a planner with a limited budget would like to decide where…

8 thms4 active usersReviewed
🏆Completed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Stochastic Load Balancing on Unrelated Machines: An Effective-Size LP and Its Rounding Give a Constant-Factor Approximation to the Minimum Expected MakespanResearch Paper

Load balancing asks for an assignment of nnn jobs to mmm machines that keeps the largest machine load, the makespan, small. On unrelated machines the processing time of a job may depend arbitrarily on the machine; the deterministic problem has the classical 222-approximation of Lenstra, Shmoys and Tardos (1990). In many applications (virtual-circuit routing,…

16 thms4 active usersReviewed
🏆Completed
ProbabilityQuantum InformationTheoretical Computer Science·Captain: mikedeng1

Simulating Large Quantum Circuits on a Small Quantum Computer: A (K, d)-Clustered Circuit Is Simulated to Precision ε with Probability 2/3 by O(2^{4K} r/ε²) Runs of d-Qubit PiecesResearch Paper

Near-term quantum processors have few qubits, while the circuits one would like to run (variational eigensolvers, sampling benchmarks, error-mitigated algorithms) often need more qubits than any single device has. Peng, Harrow, Ozols and Wu (arXiv:1904.00102, Phys. Rev. Lett. 125, 150504, 2020) show that a circuit which is only loosely connected (a few…

16 thms4 active usersReviewed
🏆Completed
Linear algebraQuantum InformationTheoretical Computer Science·Captain: mikedeng1

Quantum Singular Value Transformation and Beyond: Exponential Improvements for Quantum Matrix Arithmetics: Singular Value Transformation by Real Polynomials via Alternating Phase ModulationResearch Paper

Many quantum algorithms act on a matrix AAA that is not itself unitary: a Hamiltonian to be simulated, a linear system to be inverted, a projector to be amplified. The standard way to hand such a matrix to a quantum computer is to embed it as a block of a unitary UUU, so that A=Π~UΠA=\widetilde\Pi U\PiA=ΠUΠ for two orthogonal projectors Π,Π~\Pi,\widetilde\PiΠ,Π. The question is…

15 thms4 active usersReviewed
🏆Completed
Linear algebraOptimizationQuantum Information+1·Captain: mikedeng1

Optimization by Decoded Quantum Interferometry 2: With an Imperfect Decoder and Uniform v, 𝔼_v⟨f⟩ ≥ wᵀ[A − 2ε(m+1)]w / Σ_k w_k²(1 − ε_k) for max-XORSATResearch Paper

A max-XORSAT instance asks for a binary assignment that satisfies as many parity constraints as possible. A matrix specifies the parity check in each constraint, while a second binary vector specifies the desired parity. The objective can be written as the number of satisfied constraints minus the number violated, so an assignment with a high objective…

10 thms4 active usersReviewed
🏆Completed
Linear algebraQuantum InformationTheoretical Computer Science·Captain: mikedeng1

Learning Stabilizer States by Bell Sampling: Algorithm 1 Identifies an n-Qubit Stabilizer State from 5n+2 Copies, Failing with Probability at Most 2⁻ⁿResearch Paper

Determining an unknown quantum state of nnn qubits to good accuracy requires, in general, a number of copies of the state exponential in nnn; this follows from Holevo's theorem. One way around this barrier is to restrict the class of states. Stabilizer states are the natural candidate: they are the states produced from ∣0n⟩|0^n\rangle∣0n⟩ by Clifford circuits, they…

14 thms4 active usersReviewed
CombinatoricsOperations ResearchOptimization+2·Captain: mikedeng1

Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes I: With Patience at Least 2, Attenuated Random-Order Probing Gives Every Edge a(e)·Pr[e Is Free] ≥ β*Research Paper

In offline stochastic matching a graph is given in which every edge is present only with some known probability, and the only way to find out is to probe it: a probed edge that turns out to be present must be added to the matching at once. Each vertex may also limit how many of its edges are probed (its patience). The model captures applications in which a…

14 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability+1·Captain: mikedeng1

Algorithms for Online Matching, Assortment, and Pricing with Tight Weight-Dependent Competitive Ratios II: In the Deterministic Case Multi-price Ranking Is minᵢ F(𝒫ᵢ)-CompetitiveResearch Paper

Online matching models a platform that must commit resources to requests as they arrive, without knowing the future. In revenue management the resources are items in limited supply and the requests are customers, and the firm also chooses the price. Ma and Simchi-Levi (arXiv:1905.04770, Oper. Res. 2020, DOI 10.1287/opre.2019.1957) give algorithms whose…

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

Optimal Approximation for Submodular and Supermodular Optimization with Bounded Curvature I: Swap-Local Optima of the Non-Oblivious Potential Are (1 − c/e)-Approximate for Submodular MaximizationResearch Paper

Maximizing a monotone submodular function over the bases of a matroid is the standard model for coverage, facility location, sensor placement and welfare maximization. The best possible approximation factor in the value-oracle model is 1−1/e1 - 1/e1−1/e (Nemhauser–Wolsey 1978; Călinescu–Chekuri–Pál–Vondrák 2011). Many functions met in practice are far from the worst…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsLinear algebraMarkov Chain+1·Captain: mikedeng1

High Order Random Walks: Beyond Spectral Gap 2: On a Two-Sided λ-Local Spectral Expander, Spec(M⁺_k) ⊆ {1} ∪ ⋃_j [(k+1−j)/(k+2) ± √(k+1)·ε_k/(k+2)] and Eigenvectors Lie Near U^j_kResearch Paper

High-dimensional expanders are simplicial complexes whose local structure forces global mixing. Random walks on their kkk-dimensional faces, the high order random walks, are used to analyse sampling algorithms: the bases-exchange walk on the bases of a matroid is such a walk, and its spectral analysis by Anari, Liu, Oveis Gharan and Vinzant (arXiv:1811.01816)…

15 thms4 active usersReviewed
🏆Completed
CombinatoricsLinear algebraMarkov Chain+1·Captain: mikedeng1

High Order Random Walks: Beyond Spectral Gap 1: On a One-Sided λ-Local Spectral Expander, ‖M⁺_k φ‖ ≤ ((k+1)/(k+2) + (k+1)λ/2)‖φ‖ for Every k-Cochain φ Orthogonal to the ConstantsResearch Paper

A high dimensional expander is a simplicial complex whose local structure forces global expansion. The high order random walks on such a complex move from a kkk-face to a kkk-face through a common (k+1)(k+1)(k+1)-face. They were studied for their connection to agreement tests in probabilistically checkable proofs (Dinur–Kaufman 2017; Kaufman–Mass 2017), and they later…

14 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Joint Assortment Optimization and Customization under a Mixture of Multinomial Logit Models 1: Augmented Greedy Earns a (1 − 1/e) Fraction of the Optimal Revenue from the Complete Customer TypesResearch Paper

Retailers that carry a limited range of products often know something about a customer before choosing which of those products to display. The customized assortment problem asks which products to carry when the displayed assortment may be tailored to the arriving customer's type. This separates the first-stage capacity decision from the later offer…

9 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability+1·Captain: mikedeng1

Greed Works – Online Algorithms For Unrelated Machine Stochastic Scheduling 2: Greedy Assignment With Nominal Start Times Is (7.216 + 3.608Δ)h(Δ)-Competitive in the Online-Time ModelResearch Paper

Scheduling jobs on parallel machines to minimize the total weighted completion time ∑jwjCj\sum_j w_jC_j∑j​wj​Cj​ is a basic model of service and computing systems. Two features of practice are hard to combine with performance guarantees: jobs are not known in advance but arrive over time, and their processing times are random, with only their distributions known when they…

12 thms4 active usersReviewed
PreviousPage 4 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