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
AlgebraTheoretical Computer Science·Captain: iris

Unbounded Fan-in Circuits and Associative Functions: A Finite Semigroup Has Constant-Depth, Polynomial-Size Circuits Exactly When It Is GroupfreeResearch Paper

Constant-depth circuits with unbounded fan-in are the standard model of very fast parallel computation with cheap wide gates. The lower bound of Furst, Saxe and Sipser (1984, doi:10.1007/BF01744431) shows that parity is out of reach at polynomial size, and later work sharpened it, notably Håstad (1986, doi:10.1145/12130.12132). On the other side, binary…

16 thms2 active usersReviewed
Convex OptimizationInformation Theory·Captain: iris

Exponential memory/query-complexity tradeoffs in high-accuracy feasibility problemsResearch Paper

Cutting-plane methods solve convex feasibility problems with an optimal number of separation-oracle queries, but they store a description of the current localization set, about d2log⁡(1/ϵ)d^2\log(1/\epsilon)d2log(1/ϵ) bits. Gradient-type methods need only O(dlog⁡(1/ϵ))O(d\log(1/\epsilon))O(dlog(1/ϵ)) bits but converge polynomially. Whether low memory forces a large query cost is a question about the…

79 thms2 active usersReviewed
Convex OptimizationOptimizationQuantum Information·Captain: iris

Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier RankResearch Paper

A convex body is usually available only through an oracle. In the membership oracle model, an algorithm may ask whether a point lies in a body K⊆RnK\subseteq\mathbb R^nK⊆Rn, given radii with B2(0,r)⊆K⊆B2(0,R)B_2(0,r)\subseteq K\subseteq B_2(0,R)B2​(0,r)⊆K⊆B2​(0,R), and it must return a nearly optimal point for a linear objective. Classically this costs a polynomial number of membership queries, and…

74 thms2 active usersReviewed
Algebra·Captain: arpcs

Ordinary binary polynomial multiplication below nlog⁡nn\log nnlognResearch Paper

Polynomial multiplication is a basic operation in computer algebra: two coefficient lists must be converted into the coefficient list of their product. Its bit complexity depends on the coefficient field and the permitted machine operations. For a field fixed before the input length varies, Harvey and van der Hoeven established the unconditional benchmark …

4 thms2 active usersReviewed
Convex OptimizationDiscrete GeometryOperations Research+1·Captain: iris

Tractable Relaxations of Composite Functions: For Supermodular, Concave-Extendable Outer-Functions, a Facet of the Concave Envelope over PPP Tight at Any Point Is Found in O(dnlog⁡d)O(dn\log d)O(dnlogd) OperationsResearch Paper

Global solvers for nonconvex optimization (spatial branch-and-bound) replace every nonconvex function by a convex relaxation. The standard factorable approach relaxes a composite function ϕ(f(x))\phi(f(x))ϕ(f(x)) by bounding the inner functions fif_ifi​ on intervals and convexifying the outer-function ϕ\phiϕ over the resulting box. He and Tawarmalani, building on Tawarmalani,…

59 thms2 active usersReviewed
Captain: Shuze Chen

Mastermind is NP-Complete: Mastermind satisfiability is NP-completeResearch Paper

A Mastermind player sees guesses and feedback but cannot inspect the hidden sequence of colors. Before asking which guess to make next, one can ask whether the observations are consistent with any sequence at all. This is the Mastermind satisfiability problem, or MSP. It separates the logical content of the observations from the strategic problem of…

5 thms2 active usersReviewed
Combinatorics·Captain: Shuze Chen

The Complexity of Clickomania: NP-completeness with five columns and three colorsResearch Paper

A puzzle can have simple local rules while the choice of moves has global consequences. Clickomania, also known as Same Game, is an example: a player removes adjacent blocks of one color, and the remaining blocks move into the vacated space. The computational question asks whether a given starting position can be cleared completely. Biedl, Demaine, Demaine,…

6 thms2 active usersReviewed
Mathematical Logic·Captain: LG

F_d versus F_{d+1}: fixed-depth separation of bounded-depth FregeOpen Problem

Bounded-depth Frege systems are the proof systems of propositional logic in which every formula of a proof has depth bounded by a fixed constant ddd; the resulting system is written FdF_dFd​. They are the proof-theoretic counterpart of the circuit class AC0\mathrm{AC}^0AC0 and of the bounded arithmetic theories IΔ0I\Delta_0IΔ0​ and its relatives: short FdF_dFd​-proofs of a family…

6 thms2 active usersReviewed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

Tight Complexity Bounds for Optimizing Composite Objectives II: Any Deterministic Algorithm with Gradient and Prox Oracle Access Needs Ω(m√(γB²/ε)) Queries on Sums of m Convex γ-Smooth FunctionsResearch Paper

Many problems in machine learning and statistics minimize an average of mmm convex losses, one per data point or per block of data. Incremental methods such as SAG, SVRG, SAGA, SDCA, Finito and Katyusha exploit this finite-sum structure: each step touches one component fif_ifi​ instead of the whole average, and for smooth components the best of them reach accuracy …

12 thms2 active usersReviewed
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
PreviousPage 14 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