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
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
Information TheoryQuantum InformationTheoretical Computer Science·Captain: iris

Failure of Symmetry of Information for Quantum ComputationsResearch Paper

Symmetry of information is the identity K(x,y)=K(x)+K(y∣x)±O(log⁡(∣x∣+∣y∣+2))K(x,y)=K(x)+K(y\mid x)\pm O(\log(|x|+|y|+2))K(x,y)=K(x)+K(y∣x)±O(log(∣x∣+∣y∣+2)) for plain Kolmogorov complexity (Zvonkin–Levin 1970). It says that the information in a pair splits additively into the information in the first string and the information in the second given the first. Whether this survives time bounds is a long-standing question of…

22 thms1 active userReviewed
Machine LearningMathematical LogicTheoretical Computer Science·Captain: Shuze Chen

A Witnessing Duality for ReLU Network DepthResearch Paper

How many hidden layers a ReLU network needs to compute max⁡(x1,…,xn)\max(x_1,\dots,x_n)max(x1​,…,xn​) exactly is a basic question about the expressiveness of depth. Exact representation questions of this kind are studied for real, rational and integer weights. For integer weights, Haase, Hertrich and Loho (arXiv:2302.12553) proved a logarithmic depth lower bound by a modular argument…

7 thms1 active userReviewed
Captain: mikedeng1

Limits of LiftingResearch Paper

Monotone circuit lower bounds were first proved by Razborov's approximation method (Razborov 1985): every gate of a small circuit is replaced by an approximating gate, and one shows that every approximator is far from the target function. Razborov also showed that the method, in a natural general form, cannot prove more than linear lower bounds for…

15 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

Counting Square Tilings with a Fixed Set of Polyominoes Is #EXP-CompleteResearch Paper

Exact counting asks for the number of solutions rather than whether a solution exists. A tiling problem makes this distinction concrete: a region can admit tilings whose number is difficult to compute even when tileability has an efficient criterion. Restricting the pieces to one fixed family and the region to an ordinary square leaves only one varying…

14 thms1 active userReviewed
Graph TheoryOptimizationTheoretical Computer Science·Captain: mikedeng1

Shortest Disjoint Paths in Planar GraphsResearch Paper

This mission contains the full arbitrary-position search goal, all seventeen numbered milestones, thirteen local definition items and a published planarity reference. The theorem proofs are open Lean declarations.

32 thms1 active userReviewed
Theoretical Computer Science·Captain: Shuze Chen

A Numerical Refinement of an Exact Discrete Fourier Transform BoundResearch Paper

The discrete Fourier transform of length nnn maps x∈Cnx \in \mathbb C^nx∈Cn to (DFTnx)j=∑k=0n−1ζnjkxk(\mathrm{DFT}_n x)_j = \sum_{k=0}^{n-1}\zeta_n^{jk}x_k(DFTn​x)j​=∑k=0n−1​ζnjk​xk​, ζn=exp⁡(2πi/n)\zeta_n = \exp(2\pi i/n)ζn​=exp(2πi/n). The Cooley–Tukey factorization computes it with O(nlog⁡n)O(n\log n)O(nlogn) arithmetic operations, and Bluestein's chirp reduction extends that order of growth to every length (Cooley–Tukey 1965; Bluestein 1970). Later work…

15 thms1 active userReviewed
Group TheoryProbability·Captain: mikedeng1

On Testing Finite GroupsResearch Paper

A multiplication table describes a binary operation on a finite labelled set. Reading the whole table requires quadratically many entries. Property testing instead asks for a decision from substantially fewer entries: accept a genuine group and reject an operation that requires many changes to become any group. This question concerns algorithms that receive…

36 thms1 active userReviewed
Quantum Information·Captain: mikedeng1

EQP⊆IP\mathsf{EQP}\subseteq\mathsf{IP}EQP⊆IP Does Not RelativizeResearch Paper

A classical polynomial-time verifier interacting with an unrestricted prover can check every polynomial-time quantum computation: BQP⊆PSPACE=IP\mathsf{BQP}\subseteq\mathsf{PSPACE}=\mathsf{IP}BQP⊆PSPACE=IP, the equality being Shamir's theorem. Whether this containment survives relative to an arbitrary oracle decides whether it can be proved by relativizing techniques. Bouland, Huang,…

26 thms1 active userReviewed
Algorithmic Game TheoryStochastic Systems·Captain: mikedeng1

The Computational Complexity of Concurrent Stochastic Games: Exact Value and ApproximationResearch Paper

A concurrent stochastic game (CSG) is played by two players on a finite graph of states. At every stage both players choose an action simultaneously and independently, and the pair of actions together with the current state determines a probability distribution over the next state. CSGs are the standard model of two-agent interaction under uncertainty with…

30 thms1 active userReviewed
Mathematical LogicTheoretical Computer Science·Captain: Shuze Chen

The Metacomplexity Structure of Search ProblemsResearch Paper

Metacomplexity studies the complexity of computational tasks that are themselves about computation: compressing strings, estimating circuit complexity, or refuting a claimed algorithm by finding an input on which it fails. Refutation tasks appear in learning theory, in hardness magnification, in derandomization and in bounded arithmetic. A refutation task…

21 thms1 active userReviewed
CombinatoricscryptographyTheoretical Computer Science·Captain: iris

Towards Asymptotically Optimal Pseudorandom Functions: Linear-Size Circuits with Exponentially Small BiasResearch Paper

A keyed function family FK:{0,1}n→{0,1}nF_K:\{0,1\}^n\to\{0,1\}^nFK​:{0,1}n→{0,1}n is the basic object of symmetric cryptography. Two goals pull against each other: the function should be cheap to evaluate, ideally by a circuit of size O(n)O(n)O(n), and it should resist attacks running in time 2Ω(n)2^{\Omega(n)}2Ω(n). Whether both are possible at once is open in general. Dinur and Ishai settle the half that…

27 thms1 active userReviewed
Information TheoryTheoretical Computer Science·Captain: iris

The Gap Between Average-Case and Worst-Case ComplexityResearch Paper

Impagliazzo's "five worlds" ([Imp95], Structure in Complexity Theory 1995) separate two questions that complexity theory cannot yet tell apart. Is NP\mathsf{NP}NP hard in the worst case, and is it hard on average, for instances drawn from an efficiently samplable distribution? In the world called Heuristica, every problem in NP\mathsf{NP}NP is easy on average, yet…

45 thms1 active userReviewed
CombinatoricsHarmonic AnalysisProbability+1·Captain: Shuze Chen

Low Soundness Linearity Testing on Subsets of the HypercubeResearch Paper

A linearity test reads a function f:F2n→F2f:\mathbb F_2^n\to\mathbb F_2f:F2n​→F2​ at a few random points and accepts or rejects. It is perfectly complete if it always accepts linear functions. It has low soundness if, whenever it accepts with probability at least (1+δ)/2(1+\delta)/2(1+δ)/2, fff agrees with an affine function on at least a (1+s(δ))/2(1+s(\delta))/2(1+s(δ))/2 fraction of inputs, with s(δ)>0s(\delta)>0s(δ)>0…

22 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

Finding Hypercliques Faster Than Brute ForceResearch Paper

A hypergraph is a collection of subsets of a vertex set, called edges. In a (k−1)(k-1)(k−1)-uniform hypergraph, every edge contains exactly k−1k-1k−1 vertices. A kkk-hyperclique consists of kkk vertices for which every (k−1)(k-1)(k−1)-subset is an edge. Checking each possible selection gives a running time of order nkn^knk. The algebraic question behind this mission asks whether the…

19 thms1 active userReviewed
cryptographyTheoretical Computer Science·Captain: iris

Near-Optimal One-Way Functions, Direct Product Hardness and Hash Functions from iO and NP versus coNPResearch Paper

A one-way function is an efficiently computable function f:{0,1}n→{0,1}mf : \{0,1\}^n \to \{0,1\}^mf:{0,1}n→{0,1}m that no efficient algorithm can invert on a random image: given y=f(x)y = f(x)y=f(x) for uniform xxx, it is hard to find any x′x'x′ with f(x′)=yf(x') = yf(x′)=y. One-way functions are the minimal assumption of private-key cryptography, and their quantitative strength, the best inversion probability an…

65 thms1 active userReviewed
Mathematical Logic·Captain: iris

An Exponential Succinctness Gap between Three-Variable Logic and the Calculus of RelationsResearch Paper

Tarski showed in the 1940s that, over binary relational signatures, three-variable first-order logic (FO3\mathrm{FO}^3FO3) and the calculus of relations (CoR), a variable-free algebra of binary relations, define the same binary queries (Tarski 1941; Tarski–Givant 1987). The two translations are lopsided: a CoR term TTT becomes an FO3\mathrm{FO}^3FO3 formula of size O(∣T∣)O(|T|)O(∣T∣)…

22 thms1 active userReviewed
Theoretical Computer Science·Captain: Shuze Chen

On the Complexity of Intersection Non-emptiness for Star-Free Language Classes: Logspace completeness at the first half-levelResearch Paper

Several specifications of a finite-state system may constrain the same sequence of events. Satisfying all of them requires a word accepted by every specification automaton. Intersection nonemptiness asks whether such a word exists. Its input is a list of finite automata, so the length of that list matters along with the sizes of the individual automata. The…

10 thms1 active userReviewed
PreviousPage 20 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