Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Complexity Theory

570 missions · 156 completed

Missions

Open414Completed156All570
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: wurtle

Parity lifts and bounded-treewidth witnesses for Weisfeiler–Leman equivalenceResearch Paper

The Weisfeiler–Leman (WL) method is the standard combinatorial heuristic for graph isomorphism: it repeatedly refines colors of kkk-tuples of vertices, and two graphs it cannot tell apart are called kkk-WL equivalent. It is equivalent to counting-logic indistinguishability and, by results of Dvořák (2010) and Dell, Grohe and Rattan (2018), to equality of…

31 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: wurtle

A superquadratic separation between sensitivity and block sensitivityResearch Paper

Sensitivity and block sensitivity are two of the basic complexity measures of a Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1}. Sensitivity counts how many single-bit flips change the value; block sensitivity allows disjoint groups of bits to be flipped together. Block sensitivity is polynomially related to decision-tree complexity, certificate complexity, degree…

34 thms2 active usersReviewed
🏆Completed
Linear algebraTheoretical Computer Science·Captain: wurtle

Finite tensor savings and exact Fourier circuitsResearch Paper

The discrete Fourier transform of length nnn is computed by the fast Fourier transform with O(nlog⁡n)O(n\log n)O(nlogn) arithmetic operations, and this has been the benchmark since Cooley and Tukey (1965). Whether Ω(nlog⁡n)\Omega(n\log n)Ω(nlogn) operations are necessary is one of the basic open questions of algebraic complexity theory. Lower bounds of order nlog⁡nn\log nnlogn are known only under…

8 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: wurtle

An exponential two-way deterministic state lower bound for one-way livenessResearch Paper

Two-way deterministic finite automata (2DFAs) recognize exactly the regular languages (Rabin and Scott; Shepherdson, 1959), but letting the head revisit the input can change how much finite control is needed. In 1978 Sakoda and Sipser asked for the state cost of converting one-way and two-way nondeterministic automata into 2DFAs: is a polynomial number of…

18 thms2 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: wurtle

A Polynomial-Time 2-Approximation for Shortest Common SuperstringResearch Paper

Given a finite collection S\mathcal SS of strings, the shortest common superstring (SCS) problem asks for a shortest string TTT that contains every member of S\mathcal SS as a contiguous substring. It is a basic model of sequence assembly (reconstructing a long DNA sequence from overlapping fragments) and of data compression, and it is a standard test problem for…

2 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: wurtle

The approximation threshold 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

22 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·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
Operations ResearchTheoretical Computer Science·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
Algebraic GeometryTheoretical Computer Science·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
Linear algebraTheoretical Computer Science·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
Graph TheoryTheoretical Computer Science·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
Theoretical Computer Science·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
Graph TheoryTheoretical Computer Science·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
Graph TheoryTheoretical Computer Science·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
Graph TheoryTheoretical Computer Science·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
Operations ResearchTheoretical Computer Science·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
Theoretical Computer Science·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
CombinatoricsGraph TheoryOperations Research·Captain: mikedeng1

On Metric Generators of Graphs 2: The Gadget Graph of a 3-Dimensional Matching Instance Has a Minimum T-Join With at Most q Components Exactly When a Matching ExistsResearch Paper

Let GGG be a connected graph and TTT a set of vertices of even cardinality. A TTT-join is a set of edges FFF in which exactly the vertices of TTT have odd degree. A TTT-cut is a cut δ(X)\delta(X)δ(X) with ∣X∩T∣|X\cap T|∣X∩T∣ odd. Write τ(G,T)\tau(G,T)τ(G,T) for the minimum size of a TTT-join and ν(G,T)\nu(G,T)ν(G,T) for the maximum number of pairwise disjoint TTT-cuts. Every TTT-cut meets every TTT-join, so …

8 thms2 active usersReviewed
🏆Completed
Dynamic ProgrammingMathematical LogicOperations Research·Captain: mikedeng1

The Complexity of Markov Decision Processes V: A Quantified Boolean Formula Is True Iff Its Partially Observed Markov Decision Process Has a Zero-Cost PolicyResearch Paper

A Markov decision process is the standard model of sequential decision making under uncertainty: a controller observes the state of a finite system, chooses a decision, pays a cost, and the system moves to a random next state. In many applications (maintenance, inventory with unreliable records, robotics, medical treatment) the controller does not see the…

8 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: hao jia

Weighted Falsifiability of Unambiguous DNFsOpen Problem

A disjunctive normal form (DNF) is a disjunction of terms, each term a conjunction of Boolean literals. An unambiguous DNF has pairwise disjoint terms: no Boolean assignment satisfies two different terms. This restriction makes several tasks easy. In particular, the cited open-problem entry records polynomial-time algorithms for weighted satisfiability on…

4 thms2 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Market Equilibrium under Separable, Piecewise-Linear, Concave Utilities II: An Exact 3-Cover Exists iff the Constructed Market Has an EquilibriumResearch Paper

Market equilibrium is the central solution concept of general equilibrium theory: prices at which every agent buys a utility-maximizing bundle and supply meets demand. Arrow and Debreu (1954) proved that equilibria exist under mild conditions on endowments and utilities, and a line of work in algorithmic game theory asks how hard it is to compute them. For l…

12 thms2 active usersReviewed
🏆Completed
Algebraic GeometryRepresentation Theory·Captain: LG

Geometric Complexity Theory: No Occurrence ObstructionsResearch Paper

The permanent versus determinant problem asks how large an nnn must be for the permanent of an m×mm \times mm×m matrix to be written as the determinant of an n×nn \times nn×n matrix whose entries are affine linear functions of the m2m^2m2 input variables. Valiant showed that some finite nnn always works and conjectured in 1979 that the least such nnn, the determinantal complexity…

12 thms2 active usersReviewed
🏆Completed
Quantum Information·Captain: Goku

Shallow Quantum Circuits and Causal ConesTextbook

A quantum circuit of depth ddd built from gates of fan-in at most two cannot let an output wire depend on more than 2d2^d2d input wires. The argument is folklore and takes a paragraph on paper: the causal cone of the measured wire grows by at most a factor of two per layer. Formalizing it exposes a subtlety that the paper argument hides, and that is what this…

9 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: WizardOfMenlo

Nearly Optimal Hardness for CVP and NCP with PreprocessingResearch Paper

In the nearest codeword problem (NCP) one is given a linear code C⊆FM\mathcal C \subseteq \mathbb F^MC⊆FM over a finite field and a target word t∈FMt \in \mathbb F^Mt∈FM, and must find a codeword closest to ttt in Hamming distance. In the closest vector problem (CVP) one is given a full-rank lattice Λ⊆RM\Lambda \subseteq \mathbb R^MΛ⊆RM and a target t∈RMt \in \mathbb R^Mt∈RM, and must find…

34 thms1 active userReviewed
🏆Completed
Mathematical LogicTheoretical Computer Science·Captain: kmehltretter82

A New Recursion-Theoretic Characterization of the Polytime Functions (Bellantoni & Cook, Computational Complexity 1992)Research Paper

Cobham's seminal 1965 characterization of the polynomial-time computable functions (FP\mathsf{FP}FP) by bounded recursion on notation required an explicit a priori polynomial size bound f(x,y⃗)≤b(x,y⃗)f(x, \vec{y}) \le b(x, \vec{y})f(x,y​)≤b(x,y​) attached to every recursive definition, embedding a semantic growth check directly into the syntax of function definitions. Bellantoni and Cook (C…

8 thms1 active userReviewed
PreviousPage 6 of 7Next

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