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
Operations Research·Captain: wurtle

Single-exponential recovery and bounded-price strictness for metric k-medianResearch Paper

In metric kkk-median, a finite set JJJ (or DDD) of clients and a finite set FFF of candidate facilities lie in a common finite metric with rational distances. Given an integer k≥1k\ge1k≥1, one opens a nonempty set S⊆FS\subseteq FS⊆F with ∣S∣≤k|S|\le k∣S∣≤k and pays

25 thms2 active usersReviewed
🏆Completed
Information TheoryProbability·Captain: wurtle

Quantitative lower bounds for trace reconstructionResearch Paper

In the trace reconstruction problem an unknown binary word x∈{0,1}nx\in\{0,1\}^nx∈{0,1}n is passed repeatedly through a deletion channel: each bit is deleted independently with known probability q∈(0,1)q\in(0,1)q∈(0,1) and the surviving bits are concatenated in order. Each output, called a trace, reveals its length and its bits but not which positions survived. The question is how many…

14 thms2 active usersReviewed
🏆Completed
Discrete GeometryOptimization·Captain: wurtle

Near-square-root logarithmic integrality gaps for uniform sparsest cutResearch Paper

Sparsest cut asks for a partition of a weighted graph whose crossing capacity is small compared with the demand it separates. It is a basic graph-partitioning primitive (used for divide-and-conquer algorithms, clustering and expansion testing), and its relaxations are the main bridge between approximation algorithms and the geometry of finite metric spaces.…

5 thms2 active usersReviewed
🏆Completed
CombinatoricsMarkov Chain·Captain: wurtle

An FPRAS for Cell-Bounded Contingency TablesResearch Paper

A cell-bounded contingency table is a nonnegative integer matrix with prescribed row sums, column sums and an upper bound on each entry. Bounds of zero forbid entries (structural zeros), and bounds of one give bipartite graphs with prescribed degrees, so the model contains degree-constrained subgraph counting and perfect matchings (the permanent). Counting…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsMarkov Chain·Captain: wurtle

Exact Uniform Sampling of Contingency Tables with Arbitrary MarginsResearch Paper

A contingency table with margins r=(r1,…,rm)r=(r_1,\dots,r_m)r=(r1​,…,rm​) and c=(c1,…,cn)c=(c_1,\dots,c_n)c=(c1​,…,cn​) is a nonnegative integer matrix whose row sums are rrr and column sums are ccc. Such tables are the basic objects of categorical data analysis: conditional tests of independence (Fisher's exact test and its generalizations) compare an observed table with the uniform distribution on all…

18 thms2 active usersReviewed
🏆Completed
CombinatoricsInformation Theory·Captain: wurtle

Entropy and Face Dimension of the Perfect-Matching PolytopeResearch Paper

Prescribing the probability xex_exe​ that each edge belongs to a random perfect matching does not determine the distribution of the whole matching. The largest entropy compatible with those edge probabilities, H(x)H(x)H(x), measures how many matching choices can coexist with them, and it links three topics: lower bounds on the number of perfect matchings,…

2 thms2 active usersReviewed
🏆Completed
CombinatoricsMarkov Chain·Captain: wurtle

A Fully Polynomial Randomized Approximation Scheme for Perfect Matchings in General GraphsResearch Paper

A perfect matching of a graph is a set of edges covering every vertex exactly once. Finding one is easy — Edmonds (1965) gave a polynomial-time algorithm for general graphs — but counting them is hard: Valiant (1979) proved exact counting #P-complete already for bipartite graphs, where the count is the permanent of a 0–1 matrix. Exact counting is tractable…

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

Beyond the Square-Root Exponent for Depth-Three Boolean CircuitsResearch Paper

Proving that explicit Boolean functions need large circuits is the central problem of circuit complexity. Even for very shallow circuits the known bounds are far from what counting arguments suggest. A depth-three OR–AND–OR circuit is an OR of CNFs, with unbounded fan-in and arbitrary sharing; most functions need 2Ω(n)2^{\Omega(n)}2Ω(n) gates in this model, yet for…

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

Uniform computation of the squared-logarithmic k-server boundResearch Paper

In the kkk-server problem, kkk labelled servers occupy points of a metric space, requests arrive online, and each request is served by moving one server onto it; the cost is the total distance moved, compared with the offline optimum through the competitive ratio. A companion OpenAI preprint claims that on every metric there exists a randomized policy with…

8 thms2 active usersReviewed
🏆Completed
Operations Research·Captain: wurtle

Squared-logarithmic randomized k-server on arbitrary metricsResearch Paper

In the kkk-server problem, kkk servers sit at points of a metric space; requests arrive one at a time, and each request must be served by moving some server onto it, at a cost equal to the distance travelled. An online policy sees only the requests revealed so far, and its quality is measured by its competitive ratio: how much more it moves, in expectation,…

5 thms2 active usersReviewed
🏆Completed
Algebraic GeometryComplexity Theory·Captain: wurtle

A cubic lower bound for border determinantal complexity of the permanentResearch Paper

The permanent of an m×mm\times mm×m matrix X=(xij)X=(x_{ij})X=(xij​),

9 thms2 active usersReviewed
🏆Completed
Complexity TheoryLinear algebra·Captain: wurtle

Staggered extraction for exact matrix multiplication over every fieldResearch Paper

Multiplying two n×nn\times nn×n matrices by the schoolbook method costs about n3n^3n3 operations. The matrix-multiplication exponent ωF\omega_FωF​ of a field FFF is the infimum of exponents τ\tauτ such that n×nn\times nn×n matrices over FFF can be multiplied with O(nτ+o(1))O(n^{\tau+o(1)})O(nτ+o(1)) additions, subtractions and multiplications. It governs the asymptotic cost of a central bilinear…

322 thms2 active usersReviewed
🏆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
PreviousPage 18 of 25Next

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