Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Theoretical Computer Science

1,446 missions · 603 completed

The mathematical foundations of computation: which problems can be solved, by what algorithms, and at what cost in time, space, or communication. Distinguished by its emphasis on rigor and unconditional lower bounds, it spans computational complexity, algorithm design, automata and computability, cryptography, and the analysis of Boolean functions.

Missions

Open843Completed603All1446
🏆Completed
Complexity TheoryGraph Theory·Captain: wurtle

Hardness of finding large independent sets in three-colorable graphsResearch Paper

A graph is three-colorable if its vertices can be colored with three colors so that adjacent vertices get different colors. Deciding three-colorability is NP-complete. The approximate coloring problem asks how much a promise helps: given a graph promised to be three-colorable, can one efficiently find a coloring with a few more colors, or at least a large…

6 thms2 active usersReviewed
🏆Completed
Complexity Theory·Captain: wurtle

Perfect completeness for 2-to-1 gamesResearch Paper

A projection game (label cover) asks for labels on the two sides of a bipartite multigraph so that, on each edge, the right label is the image of the left label under a prescribed map. In a 2-to-1 game the left alphabet has 2q2q2q labels, the right alphabet qqq, and every edge map has exactly two preimages of each right label. Khot introduced the 2-to-1 and…

11 thms2 active usersReviewed
🏆Completed
Complexity TheoryGraph Theory·Captain: wurtle

Constant-factor hardness of directed feedback vertex setResearch Paper

A directed feedback vertex set of a finite digraph GGG is a set FFF of vertices meeting every directed cycle, equivalently one whose removal leaves G−FG-FG−F acyclic; DFVS(G)\mathrm{DFVS}(G)DFVS(G) is the minimum size of such a set. The problem arises wherever cyclic dependencies must be broken — deadlock resolution, circuit testing, scheduling — and a topological order of G−FG-FG−F cert…

4 thms2 active usersReviewed
🏆Completed
Complexity TheoryGraph Theory·Captain: wurtle

Constant-factor hardness of Min-UnCutResearch Paper

Min-UnCut asks, for a finite simple graph G=(V,E)G=(V,E)G=(V,E), for the minimum number of edges whose deletion makes GGG bipartite. Equivalently, for a bipartition V=S⊔(V∖S)V=S\sqcup(V\setminus S)V=S⊔(V∖S) let UncutG(S)\mathrm{Uncut}_G(S)UncutG​(S) count the edges with both endpoints on the same side, and set OPTuncut(G)=min⁡SUncutG(S)\mathrm{OPT}_{\mathrm{uncut}}(G)=\min_S\mathrm{Uncut}_G(S)OPTuncut​(G)=minS​UncutG​(S). The quantity measures distance from…

3 thms2 active usersReviewed
🏆Completed
Complexity TheoryGraph Theory·Captain: wurtle

The Factor-Two Hardness Threshold for Vertex CoverResearch Paper

A vertex cover of a graph is a set of vertices meeting every edge; τ(G)\tau(G)τ(G) denotes the minimum size of one. Computing τ(G)\tau(G)τ(G) exactly is NP-hard, but a two-line algorithm — take both endpoints of a maximal matching — always returns a cover of size at most 2τ(G)2\tau(G)2τ(G). Whether any polynomial-time algorithm achieves a fixed factor 2−ε2-\varepsilon2−ε is one of the…

4 thms2 active usersReviewed
🏆Completed
Complexity TheoryOperations Research·Captain: wurtle

A Direct Proof of Optimal Max-Cut HardnessResearch Paper

Max-Cut asks for a partition of the vertices of a graph that maximizes the number of edges crossing it. Its decision version is one of Karp's original NP-complete problems, so the natural question is how well it can be approximated in polynomial time. Goemans and Williamson's semidefinite-programming algorithm with random-hyperplane rounding achieves ratio…

11 thms2 active usersReviewed
🏆Completed
Complexity Theory·Captain: wurtle

The Unique Games TheoremResearch Paper

A Unique Game is a system of constraints between pairs of variables, each constraint saying that the label of one endpoint is a fixed permutation of the label of the other. Deciding whether all constraints can be satisfied is easy (propagate labels along a spanning tree), so the interesting question is approximate: given an instance in which almost all…

5 thms2 active usersReviewed
🏆Completed
CombinatoricsFunctional Analysis·Captain: wurtle

Finite-Circle Obstructions, Binary Codes, and Histogram Embeddings for Edit DistanceResearch Paper

Edit distance ED(x,y)\mathrm{ED}(x,y)ED(x,y), the least number of single-symbol insertions, deletions and substitutions turning xxx into yyy, is the standard distance on strings. Embedding strings into ℓ1\ell_1ℓ1​ with small distortion would make edit distance amenable to the fast nearest-neighbour and sketching tools available for ℓ1\ell_1ℓ1​, so the least achievable distortion is a…

54 thms2 active usersReviewed
🏆Completed
CombinatoricsFunctional Analysis·Captain: wurtle

Edit Distance in l1: Matching Bounds up to Constants in the ExponentResearch Paper

Edit distance ED(x,y)\mathrm{ED}(x,y)ED(x,y) is the least number of single-symbol insertions, deletions and substitutions transforming a string xxx into yyy. It is the basic similarity measure for strings, but it is expensive to compute and awkward to index. A standard way around this is to embed strings into ℓ1\ell_1ℓ1​ so that ℓ1\ell_1ℓ1​ distances approximate edit distances; the…

3 thms2 active usersReviewed
🏆Completed
Discrete GeometryGraph Theory·Captain: wurtle

L1 Embeddings of Graphs of Bounded TreewidthResearch Paper

A finite metric embeds into L1L_1L1​ exactly when it is a nonnegative combination of cut metrics δS(u,v)=∣1S(u)−1S(v)∣\delta_S(u,v)=|\mathbf 1_S(u)-\mathbf 1_S(v)|δS​(u,v)=∣1S​(u)−1S​(v)∣. This makes L1L_1L1​ distortion the right measure for the flow–cut gap: given edge capacities and pairwise demands, the ratio between the sparsest cut value ϕ∗\phi_*ϕ∗​ and the maximum concurrent flow λ∗\lambda_*λ∗​. Linial, London and…

2 thms2 active usersReviewed
🏆Completed
Discrete GeometryGraph Theory·Captain: wurtle

Planar Graph Metrics Embed into L1 with Constant DistortionResearch Paper

A finite metric space embeds into L1L_1L1​ exactly when its metric is a nonnegative combination of cut metrics δS(x,y)=∣1S(x)−1S(y)∣\delta_S(x,y)=|\mathbf 1_S(x)-\mathbf 1_S(y)|δS​(x,y)=∣1S​(x)−1S​(y)∣. For this reason the least distortion with which a graph metric embeds into L1L_1L1​ governs the gap between multicommodity flow and sparsest cut: Linial, London and Rabinovich (1995) and Aumann and Rabani (1998)…

4 thms2 active usersReviewed
🏆Completed
Captain: marwahaha

Matrix multiplication exponent ≤ 2.25 over every fieldResearch Paper

This mission asks for a formal proof that the matrix multiplication exponent is at most 2.25=9/42.25=9/42.25=9/4 over every field. It is proposed for the Matrix multiplication exponent campaign, using the campaign's existing tensor-rank definition. The target is deliberately non-strict: equality with 9/49/49/4 is allowed.

4 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: xuanji

Deterministic APSP in O(n^2.996001) 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. In 2026, Alman and Vassilevska Williams (arXiv:2610.06…

5 thms2 active usersReviewed
🏆Completed
Discrete GeometryNumber Theory·Captain: mikedeng1

On Lattices, Learning with Errors, Random Linear Codes, and Cryptography 6: The Smoothing Parameter Satisfies η_ε(L) ≥ √(ln(1/ε)/π)/λ₁(L*) ≥ √(ln(1/ε)/π)·λ_n(L)/nResearch Paper

The learning with errors (LWE) problem underlies much of post-quantum public-key cryptography, and its hardness rests on Regev's reduction from worst-case lattice problems to LWE (Regev, J. ACM 2009). Every step of that reduction is calibrated by the smoothing parameter ηϵ(L)\eta_\epsilon(L)ηϵ​(L) of Micciancio and Regev (SIAM J. Comput. 2007): the Gaussian width…

10 thms2 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: mikedeng1

On Lattices, Learning with Errors, Random Linear Codes, and Cryptography 4: A Random Subset Sum of l Uniform Elements of a Finite Abelian Group Is on Average Within √(|G|/2^l) of UniformResearch Paper

Regev's On Lattices, Learning with Errors, Random Linear Codes, and Cryptography (J. ACM 56(6), 2009, Article 34; doi:10.1145/1568318.1568324) introduced the Learning with Errors (LWE) problem and built a public-key cryptosystem on it. The source for this mission is that published J. ACM article. The paper's main theorem, a quantum reduction from worst-case…

6 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization+1·Captain: mikedeng1

Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal 2: Under Lower and Upper Degree Bounds, Iterative Rounding Finds a Connecting Tree of LP Cost within A_v − 1 and B_v + 1Research Paper

Network design problems often ask for a cheap spanning tree in which no vertex is overloaded: in multicast and overlay networks the degree of a node bounds the number of copies it must forward, and in physical networks it bounds the number of ports. The minimum bounded degree spanning tree problem asks for a minimum-cost spanning tree whose degrees respect…

12 thms2 active usersReviewed
🏆Completed
Machine LearningOperations Research·Captain: mikedeng1

The Weighted Majority Algorithm 5: With Pool Predictions in [0,1], the Binary Master WMG Makes at Most log(w_init/w_fin)/log(2/(1+β)) MistakesResearch Paper

Prediction with expert advice asks how a learner should combine the forecasts of a pool of prediction algorithms when nothing is assumed about the data: the instances and labels may be chosen by an adversary, and the learner's performance is compared with that of the pool. Littlestone and Warmuth's The Weighted Majority Algorithm (Inform. and Comput. 108,…

5 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: marwahaha

3SUM in O(n^1.999112) Time on a Word RAMResearch Paper

Improve deterministic integer 3SUM to O(n1.999112)O(n^{1.999112})O(n1.999112) time in the foundation mission’s word-RAM model.

3 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: marwahaha

3SUM in O(n^1.99913) Time on a Word RAMResearch Paper

Prove deterministic O(n1.99913)O(n^{1.99913})O(n1.99913) time for 3SUM on polynomially bounded integers, using the same word-RAM model and definitions as the foundation mission.

3 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

A Scheduling Model for Reduced CPU Energy: For P(s) = s², the Average Rate Heuristic Has Competitive Ratio Between 4 and 8Research Paper

A processor can save energy by running slowly when work is light, but a deadline may force it to run faster. Yao, Demers, and Shenker formulated this tradeoff as an offline and online scheduling problem for a variable-speed processor in their 1995 FOCS paper. Their Average Rate Heuristic (AVR) uses only each job's arrival, deadline, and required work to set…

19 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization+1·Captain: mikedeng1

Approximating Minimum Bounded Degree Spanning Trees to within One of Optimal 1: Iterative Rounding Finds a Spanning Tree of Cost at Most the LP Optimum with Every Degree at Most B_v + 1Research Paper

A network designer may need a cheap connection that keeps the number of links at each site within a local capacity. The minimum bounded-degree spanning tree problem asks for the cheapest spanning tree of a weighted, undirected graph whose vertex degrees respect prescribed upper bounds. The capacity constraints matter in settings where a low-cost tree alone…

8 thms2 active usersReviewed
🏆Completed
Machine LearningOperations Research·Captain: mikedeng1

The Weighted Majority Algorithm 1: WM Makes at Most log(w_init/w_fin)/log(2/(1+β)) Mistakes on Any SequenceResearch Paper

In online prediction, a learner makes a forecast before seeing the next label. A collection of other forecasters may offer useful advice, but the learner need not know beforehand which forecaster will perform well. Littlestone and Warmuth's Weighted Majority Algorithm (WM) gives a deterministic way to combine such advice. Its guarantees hold for every…

4 thms2 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

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

A job shop is the basic model of a factory floor in which every job follows its own route through the machines. Minimizing the time at which the last job is finished (the finish time, or makespan) is one of the central problems of deterministic scheduling theory, and the question of which special cases admit efficient algorithms has organized much of the…

11 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: mikedeng1

Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms V: On a 3-Regular c-Expander the Uniform Max-Flow Is at Most 6𝒮/(c(⌊log n⌋ − 2))Research Paper

A multicommodity flow problem asks to route many source–sink demands through one capacitated network at the same time. Its min-cut (sparsest cut) is the smallest ratio, over all cuts, of the capacity crossing the cut to the demand separated by it. Routing is always limited by every cut, so the max-flow never exceeds the min-cut. For a single commodity the…

7 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: mikedeng1

A Theorem on Boolean Matrices: Warshall's Construction M* Equals the Boolean Sum M ∨ M² ∨ ⋯ ∨ Mᵈ of the Boolean Powers of MResearch Paper

A finite directed graph on ddd vertices is recorded by its adjacency matrix, a d×dd \times dd×d array of zeros and ones. Many questions about the graph are questions about reachability: can vertex jjj be reached from vertex iii by following one or more edges? In the late 1950s this question arose in the analysis of programs. Prosser (Applications of Boolean matrices to…

5 thms2 active usersReviewed
PreviousPage 45 of 58Next

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