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
Combinatorics·Captain: Shuze Chen

Kernelization lower bound for Permutation Pattern Matching: No polynomial kernel unless NP is contained in co-NP/polyResearch Paper

A long ordering can contain a much shorter ordering without sharing any of its numerical values. What matters is the relative order of selected entries. Researchers studying permutation patterns ask both how many permutations avoid a prescribed pattern and how efficiently an occurrence can be found. The algorithmic question has a second dimension: whether a…

15 thms3 active usersReviewed
Combinatorics·Captain: mikedeng1

NP-Hardness of Coloring 222-Colorable 333-Uniform Hypergraphs with Ω~(log⁡log⁡n)\tilde{\Omega}(\sqrt{\log \log n})Ω~(loglogn​) ColorsResearch Paper

A hypergraph coloring assigns a color to each vertex and requires that every edge contain at least two colors. Even when a coloring with two colors exists, finding a coloring with a larger permitted palette can be computationally difficult. For ordinary graphs the two-colorability promise permits an efficient algorithm. For edges of size three, it leads to…

26 thms3 active usersReviewed
Graph Theory·Captain: mikedeng1

Pfaffian Recognition is in coRPResearch Paper

A perfect matching is a set of edges covering each vertex exactly once. Deciding whether one exists is possible in polynomial time, but counting all perfect matchings is #P-complete even for bipartite graphs. This distinction matters in counting complexity and in the combinatorics of dimers: a graph can have an efficiently detectable matching while its full…

19 thms3 active usersReviewed
Quantum Information·Captain: iris

Separating QMA from QCIP with a Classical Oracle, or, the Power of Quantum Proofs over Classical Interaction for Quantum VerifiersResearch Paper

QMA is the class of problems whose yes-instances have a quantum proof: a polynomial-size quantum state that an efficient quantum verifier can check. QCMA is the same with a classical proof. Whether quantum proofs are more powerful than classical ones is a basic question of quantum complexity theory, and since an unconditional answer would separate classes…

76 thms3 active usersReviewed
Group TheoryTheoretical Computer Science·Captain: iris

Testing isomorphism of finite groups in time polynomial in the group orderResearch Paper

Deciding whether two finite groups are isomorphic is one of the basic problems of computational algebra and of complexity theory. When the groups are given by their Cayley tables (multiplication tables), the input has size about N2N^2N2 for groups of order NNN, and the natural question is whether isomorphism can be tested in time polynomial in NNN. Group…

39 thms3 active usersReviewed
Combinatorics·Captain: mikedeng1

Exhaustive Search Is Hard to Beat in Constant Depth for Hyperclique and Orthogonal VectorsResearch Paper

Detecting a large mutually connected set is a basic test of what limited computational models can express efficiently. A hyperclique generalizes a graph clique: instead of requiring every pair of selected vertices to be an edge, it requires every selected subset of a fixed size to be an edge. Exhaustive search tests each candidate vertex set separately.…

20 thms3 active usersReviewed
CombinatoricsGraph TheoryLinear algebra·Captain: mikedeng1

Counting Hamiltonian Cycles in Bipartite Digraphs Deterministically in O(1.9526n)O(1.9526^n)O(1.9526n) TimeResearch Paper

The Hamiltonian-cycle counting problem asks how many directed cycles visit every vertex of a graph exactly once. Exact counts distinguish a graph with one spanning cycle from one with many, and deciding whether the count is positive decides Hamiltonicity. The cost of this computation is a central question in exact exponential algorithms: a bound with…

16 thms3 active usersReviewed
CombinatoricsProbability·Captain: mikedeng1

Faster Approximate Text-to-Pattern Hamming Distances via Near-Optimal Sumset EstimationResearch Paper

A text search can ask how closely a pattern agrees with each window of a longer text. The Hamming distance counts positions containing different symbols. Computing the distance at every alignment is a basic string algorithm problem, and the number of distinct symbols can grow with the input. The classical exact algorithms have approximately a three-halves…

23 thms3 active usersReviewed
cryptographyQuantum Information·Captain: mikedeng1

Compressed Oracle Duality: A simple framework for knowing what quantum adversaries knowResearch Paper

A collision in a function is a pair of distinct inputs with the same output. In the random-oracle model, the function is chosen uniformly from all functions with a prescribed finite domain and range. Quantum algorithms can query such a function on a superposition of inputs, so counting queries alone does not describe the memory needed to find a collision.…

23 thms3 active usersReviewed
Quantum Error CorrectionQuantum Information·Captain: mikedeng1

The color code, the surface code, and the transversal CNOT: NP-hardness of minimum-weight decodingResearch Paper

A quantum error-correcting code stores information in a subspace detected by commuting parity checks. A syndrome records which checks report an error. A decoder must turn that information into a recovery operation. Since a quantum computer generates check outcomes throughout its operation, the classical computation required for recovery is part of its…

16 thms3 active usersReviewed
ProbabilityQuantum Information·Captain: mikedeng1

Nearly Linear Sample Bounds for Testing Product-State Satisfiability of Dense Quantum kkk-SATResearch Paper

A constraint satisfaction problem asks whether one assignment can meet every local requirement in a large system. Property testing asks a different question: can a small random induced subsystem distinguish a satisfiable instance from one requiring many constraint deletions? The distinction matters when the number of variables is large but the allowed error…

18 thms3 active usersReviewed
AlgebraLinear algebra·Captain: mikedeng1

Approximating commutative rank of matrix spaces in NCResearch Paper

A collection of rational matrices describes many possible matrices: any rational linear combination of the given matrices is allowed. A basic algorithmic question asks for a combination whose rank is as large as possible. This question includes algebraic formulations of matching and related combinatorial optimization problems. An approximation should return…

33 thms3 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Ruling out Fast Approximation Algorithms for Clique, Biclique, Collinearity, and Arithmetic ProgressionsResearch Paper

A clique is a collection of vertices in a graph with an edge between every pair. Detecting a fixed small clique is a basic graph algorithm problem. A natural approximation question asks whether a promise of a much larger clique helps detect a smaller one. In particular, could a program distinguish a graph containing a large fixed clique from a graph…

25 thms3 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Arc Kayles is PSPACE-completeResearch Paper

Arc Kayles is a two-player game on a finite undirected graph. The players alternate, and a move picks an edge uvuvuv of the current graph and deletes both endpoints. Under normal play the first player without a legal move loses. The winner is the player who plays the last edge of a maximal matching of the original graph, so Arc Kayles is to maximal matchings…

19 thms3 active usersReviewed
Algorithmic Game TheoryTheoretical Computer Science·Captain: iris

The Complexity of Correlated Equilibria Beyond Normal-Form GamesResearch Paper

A correlated equilibrium (CE) is a distribution over strategy profiles from which no player gains by applying any swap deviation, a map that replaces each recommended strategy by another one. In normal-form games (finitely many pure strategies) CE are the solutions of a linear program, and in games of polynomial type exact CE can be computed in polynomial…

48 thms3 active usersReviewed
Quantum Information·Captain: iris

Strong Selective and List-Decoding Direct Product Theorems for Quantum Query ComplexityResearch Paper

A direct product theorem says that solving kkk independent instances of a problem is kkk times as hard as solving one, and that an algorithm with fewer resources fails on the kkk-fold problem with probability exponentially close to 111 in kkk. The second, "strong" form is what lower-bound applications need. Time-space tradeoffs in the style of Borodin and Cook cut a…

48 thms3 active usersReviewed
Information TheoryProbability·Captain: iris

Can Many Instances Be Cheaper Than One? The Price of Agreement in EliminationResearch Paper

Direct-sum and direct-product questions ask how the cost of solving kkk independent instances of a communication problem relates to the cost of one. Elimination asks for much less than computing: given kkk instances, the parties only have to output some answer vector σ∈{0,1}k\sigma\in\{0,1\}^kσ∈{0,1}k that is not the true one. Guessing a uniformly random σ\sigmaσ already errs…

36 thms3 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

Settling Nondeterministic Communication Complexity of Graph ConnectivityResearch Paper

In the two-party communication model, Alice and Bob each hold part of an input and exchange bits to compute a function of the whole input; the cost is the number of bits exchanged in the worst case. Graph properties are a standard test bed for the model, and connectivity is the most studied of them: Alice and Bob hold disjoint edge sets EAE_AEA​, EBE_BEB​ of an NNN-vert…

30 thms3 active usersReviewed
Graph TheoryQuantum InformationTheoretical Computer Science·Captain: iris

Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is HardResearch Paper

The welded trees problem is the standard example of an exponential quantum speedup for a problem defined by a graph given only through a neighbor oracle. Childs, Cleve, Deotto, Farhi, Gutmann and Spielman showed in 2003 (doi:10.1145/780542.780552) that a continuous-time quantum walk started at the entrance of a randomly welded pair of binary trees reaches…

34 thms3 active usersReviewed
cryptographyTheoretical Computer Science·Captain: iris

Does Witness Indistinguishability Require Cryptography?Research Paper

Witness indistinguishability (WI), introduced by Feige and Shamir, is a privacy guarantee for interactive proofs: no efficient verifier can tell which of two valid witnesses the prover holds. It is weaker than zero knowledge, but it is preserved under parallel composition and has low-round realizations, and it is a building block of zero-knowledge…

43 thms3 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

The Complexity of Choosing Parity ProjectionsResearch Paper

In a cube attack on a stream cipher (Dinur and Shamir, 2009), an attacker sums a Boolean function over all assignments to a small set of inputs. A cube whose sum, the superpoly, is a simple function of the key yields an equation in the key bits, and enough such cubes recover the key of a reduced-round cipher. Dutta, Rajasree and Sarkar (EasyChair Preprint…

49 thms3 active usersReviewed
CombinatoricsLinear algebraTheoretical Computer Science·Captain: iris

An Explicit 4n−O(log(n)) Size Lower Bound against General Boolean CircuitsResearch Paper

Almost every Boolean function on nnn variables needs circuits of size Ω(2n/n)\Omega(2^n/n)Ω(2n/n) (Shannon, 1949). For functions that can be computed explicitly, for instance in NP\mathbf{NP}NP or even in P\mathbf{P}P, the best known lower bounds against general circuits are only linear in nnn, with a small constant. Better bounds are a step in Sipser's programme for separating …

69 thms3 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: iris

Differentially Private Verification of Distribution PropertiesResearch Paper

A distribution property verifier has sample access to an unknown distribution DDD and wants to decide whether DDD has a property PPP (uniformity, independence, a bounded support size) or is far from every distribution with that property. Testing alone can need many samples; an untrusted prover who knows DDD can sometimes cut the cost, provided the verifier can…

27 thms3 active usersReviewed
Representation TheoryTheoretical Computer Science·Captain: iris

The asymptotic spectrum of tensors is connectedResearch Paper

The matrix multiplication exponent ω\omegaω is the infimum of the real numbers τ\tauτ such that two n×nn\times nn×n matrices can be multiplied with O(nτ)O(n^\tau)O(nτ) arithmetic operations. Strassen placed this problem in a theory of tensors in which computational reductions are encoded by a preorder, and in which a compact space of monotone functions, the asymptotic spectrum,…

43 thms3 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

NP-hardness for Bipartite Colorings up to the Maximum DegreeResearch Paper

Counting the proper qqq-colorings of a graph of maximum degree Δ\DeltaΔ is the central test case of approximate counting. Since Jerrum (1995) it has been conjectured that an FPRAS exists for general graphs whenever q≥Δ+1q\ge\Delta+1q≥Δ+1, and the rapid-mixing bounds for Glauber dynamics have moved from q>2Δq>2\Deltaq>2Δ toward that threshold. On the hardness side, Galanis,…

31 thms3 active usersReviewed
PreviousPage 6 of 17Next

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