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
AlgebraAlgebraic Geometry·Captain: mikedeng1

Approximate Polynomial Satisfiability is in the Counting HierarchyResearch Paper

An exact polynomial system asks for values making every output zero. Problems in algebraic complexity also ask whether zero can be approached by outputs of a polynomial map, even when no input gives zero exactly. Approximate polynomial satisfiability, abbreviated APS, expresses this second question using algebraic closure rather than numerical tolerances.…

26 thms3 active usersReviewed
cryptographyProbabilityTheoretical Computer Science·Captain: iris

New Results in Adaptively-Secure Broadcast Encryption and Succinct Computational Secret Sharing from Standard LatticesResearch Paper

A programmable pseudorandom set sampler (PPS) is a dual-mode functional encryption scheme in which a secret key belongs to a set SSS of indices and a ciphertext belongs to one index iii. Ciphertexts can be produced in two modes: a public-key mode that needs no secret and encrypts nothing useful, and a secret-key mode that encrypts a message μ\muμ. The two modes…

93 thms3 active usersReviewed
Graph TheoryProbability·Captain: Shuze Chen

Semi-Streaming Matching in a Single Pass II: Greedy is OptimalResearch Paper

A large graph can have far more edges than vertices. Keeping every edge in memory may therefore be impractical even when retaining a few records for each vertex is affordable. The semi-streaming model asks what can be computed under this limitation when edges arrive sequentially. For maximum matching, a simple greedy procedure retains an arriving edge…

22 thms3 active usersReviewed
Theoretical Computer Science·Captain: Shuze Chen

Finite Automata Intersection Non-Emptiness: Parameterized Complexity Revisited: W[1]-completeness of DFA intersection non-emptiness for languages in w1∗w2∗⋯wm∗w_1^*w_2^*\cdots w_m^*w1∗​w2∗​⋯wm∗​Research Paper

DFA intersection non-emptiness asks whether a given collection of deterministic finite automata accepts a common word. It is one of the basic decision problems of automata theory: it is the emptiness test for a product automaton whose size is exponential in the number of factors, and it is PSPACE-complete in general (Kozen 1977, reference [14] of arXiv:2108.…

12 thms3 active usersReviewed
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
🏆Completed
CombinatoricsProbabilityTheoretical Computer Science·Captain: mikedeng1

Top-Down Lower Bounds for All DepthsResearch Paper

A Boolean circuit computes a function by composing gates. Parity asks whether an input word contains an odd number of ones. It is a basic test of the power of bounded-depth computation: unrestricted AND and OR gates can inspect many bits at once, yet computing parity at fixed depth requires exponentially many wires. The quantitative lower-bound form…

21 thms3 active usersReviewed
🏆Completed
CombinatoricsProbabilityTheoretical Computer Science·Captain: mikedeng1

Approximate Counting of kkk-Paths in O∗(2k)O^*(2^k)O∗(2k) TimeResearch Paper

A directed kkk-path in a directed graph is an ordered tuple (v1,…,vk)(v_1,\dots,v_k)(v1​,…,vk​) of pairwise distinct vertices in which every consecutive pair (vi,vi+1)(v_i,v_{i+1})(vi​,vi+1​) is an arc. Deciding whether a kkk-path exists is a benchmark problem of parameterized algorithms, while counting kkk-paths exactly is #W[1]-hard for directed and undirected graphs (Flum–Grohe 2004). Approximate…

46 thms3 active usersReviewed
🏆Completed
AlgebraTheoretical Computer Science·Captain: mikedeng1

A Width Hierarchy of Monotone Algebraic Branching ProgramsResearch Paper

Algebraic complexity studies how much arithmetic is needed to produce a polynomial from its variables and constants. A monotone computation uses only nonnegative coefficients, so terms cannot disappear by cancellation. This restriction makes resource lower bounds accessible while retaining models that distinguish addition, multiplication, and reuse of…

22 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
🏆Completed
Algebraic Geometry·Captain: iris

Multivariate Resultants: Complexity and Applications to Real FeasibilityResearch Paper

Valiant's hypothesis VP≠VNP\mathrm{VP}\neq\mathrm{VNP}VP=VNP is the algebraic analogue of P≠NP\mathrm{P}\neq\mathrm{NP}P=NP: it asserts that the permanent, and with it every polynomial family defined by exponential sums of easy polynomials, has no polynomial-size arithmetic circuits (Valiant 1979; Bürgisser 2000). Hardness results under this hypothesis tell which natural…

59 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
🏆Completed
Algebra·Captain: mikedeng1

Hitting sets From Derivations: Waring Rank and Noncommutative ABPsResearch Paper

Polynomial identity testing asks whether a polynomial presented by a computation is identically zero. In its blackbox form, only evaluations of that computation are available. A hitting set for a class of polynomials is a fixed finite set of evaluation points on which every nonzero member has a nonzero value. Such a set turns identity testing for that class…

20 thms3 active usersReviewed
🏆Completed
Quantum Information·Captain: mikedeng1

QMA has perfect completenessResearch Paper

In a Merlin–Arthur proof system, an all-powerful prover sends a proof to an efficient verifier, who accepts or rejects an input. QMA is the version in which the proof is a polynomial-size quantum state and the verifier is an efficient quantum circuit. A system has perfect completeness if every YES instance admits a proof accepted with probability exactly…

53 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
PreviousPage 8 of 23Next

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