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

Delegating Computation with Approximate Arithmetic: Interactive Proofs for WizardsResearch Paper

Interactive proofs let a computationally weak verifier check a computation carried out by an untrusted prover (Goldwasser–Micali–Rackoff 1989, Babai 1985). The protocol of Goldwasser, Kalai and Rothblum (GKR, JACM 2015) makes this efficient for both parties for arithmetic circuits over a finite field: the prover runs in time polynomial in the circuit size,…

26 thms2 active usersReviewed
cryptographyQuantum Information·Captain: iris

Quantum Advantage has Few Complexity ImplicationsResearch Paper

A proof of quantumness (PoQ) is an interactive protocol in which a classical verifier becomes convinced that its counterpart is quantum: an efficient quantum prover passes, and no efficient classical prover does. Every known construction, starting with Brakerski, Christiano, Mahadev, Vazirani and Vidick (2018), rests on a cryptographic assumption, and all…

75 thms2 active usersReviewed
Linear algebraQuantum InformationTheoretical Computer Science·Captain: iris

The Quartic Gap Between Quantum and Dequantized Algorithms for Linear Algebra Is TightResearch Paper

Quantum algorithms for linear algebra access a dense matrix AAA through quantum random access memory and prepare a state proportional to the solution of a linear system (Harrow, Hassidim, Lloyd 2009; Kerenidis, Prakash 2017; Gilyén, Su, Low, Wiebe 2019). Their cost depends on the normalized Frobenius norm ρ=∥A∥F/∥A∥\rho = \|A\|_F/\|A\|ρ=∥A∥F​/∥A∥ and the condition number …

32 thms2 active usersReviewed
AlgebraTheoretical Computer Science·Captain: iris

Cube-Root Soundness Is Optimal for the Line–versus–Point TestResearch Paper

The Reed–Muller code RMq(m,d)\mathrm{RM}_q(m,d)RMq​(m,d) consists of the evaluation tables of polynomials Q∈Fq[X1,…,Xm]Q\in\mathbb F_q[X_1,\dots,X_m]Q∈Fq​[X1​,…,Xm​] of total degree at most ddd. Restricted to an affine line, such a polynomial becomes a univariate polynomial of degree at most ddd. The line–versus–point test checks exactly this local property. It is a two-query consistency test: given a…

29 thms2 active usersReviewed
Theoretical Computer Science·Captain: iris

Algebraic methods in the theory of lower bounds for Boolean circuit complexity: MODrMOD_rMODr​ Needs exp⁡(Ω(n1/2k))\exp(\Omega(n^{1/2k}))exp(Ω(n1/2k)) AND and OR Gates at Depth kkk with MODpMOD_pMODp​, for rrr Not a Power of pppResearch Paper

Constant-depth circuits with unbounded fan-in are the simplest model of parallel computation in which nontrivial lower bounds are known. The class AC0AC^0AC0 of polynomial-size, constant-depth circuits of AND, OR and NOT gates cannot compute PARITY: this was shown by Furst, Saxe and Sipser and by Ajtai, and sharpened to exponential size by Yao and Håstad. A…

19 thms2 active usersReviewed
Theoretical Computer Science·Captain: iris

The Ultimate Karp-Lipton CollapseResearch Paper

The Karp–Lipton theorem says that if every NP problem has polynomial-size circuits, the polynomial hierarchy collapses. Karp and Lipton proved the collapse to Σ2P\Sigma^{\mathrm P}_2Σ2P​ (KL80); every later improvement replaced Σ2P\Sigma^{\mathrm P}_2Σ2P​ by a smaller class C\mathcal CC with

81 thms2 active usersReviewed
Mathematical LogicTheoretical Computer Science·Captain: iris

Relational Queries Computable in Polynomial Time: On Ordered Databases, Relational Calculus with One Least Fixpoint Expresses Exactly the Polynomial-Time QueriesResearch Paper

Relational calculus, the first-order query language of relational databases (Codd, 1972), cannot express the transitive closure of a relation, so "is xxx an ancestor of yyy?" is not a first-order query (Aho and Ullman, 1979). Aho and Ullman proposed adding a least fixpoint operator (LFP). Chandra and Harel (1980) studied the resulting Fixpoint Hierarchy and…

19 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: iris

Pseudorandom Functions in NC¹ from LWE/LPN/CDH (Or: How to Build Low-Depth PRFs, Generically)Research Paper

A pseudorandom function (PRF) is a keyed family {Fk}\{F_k\}{Fk​} that no small circuit with oracle access can distinguish from a truly random function, even when the circuit chooses its queries adaptively. PRFs are the basic object of symmetric cryptography: encryption, message authentication and many protocols are built from them. Their circuit depth, the parallel…

23 thms2 active usersReviewed
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
🏆Completed
Captain: marwahaha

Fourier and integer-convolution runtime transferTextbook

When a faster multiplication algorithm becomes available, its consequences depend on which problems reduce to multiplication and how the reduction changes input size. A displayed runtime bound alone does not identify this connection. The surrounding computation can also consume the improvement if its cost is omitted or underestimated.

22 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: marwahaha

Integer multiplication: κ = 1/2^129Open Problem

Multiplying two binary integers is a basic task in computational complexity. The relevant resource here is the number of individual steps made by a machine whose tapes can only be accessed through moving heads. Harvey and van der Hoeven established an O(nlog⁡n)O(n\log n)O(nlogn) bound in this model. The OpenAI manuscript proposes a positive saving in the exponent of the…

2 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: xuanji

Integer multiplication: κ = 1/2^182 (OpenAI manuscript construction)Open Problem

Multiplying two binary integers is a basic task in computational complexity. The relevant resource here is the number of individual steps made by a machine whose tapes can only be accessed through moving heads. Harvey and van der Hoeven established an O(nlog⁡n)O(n\log n)O(nlogn) bound in this model. The OpenAI manuscript proposes a positive saving in the exponent of the…

2 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: marwahaha

Block Sensitivity vs. Sensitivity: Classical Quadratic BoundResearch Paper

Certify the classical quadratic separation between sensitivity and block sensitivity: α≥2\alpha\ge2α≥2.

4 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
🏆Completed
AlgebraLinear algebraTheoretical Computer Science·Captain: mikedeng1

Most Tensor Problems Are NP-Hard 4: A Rational 2×2×2 Tensor Has Smaller Rank over the Reals Than over the RationalsResearch Paper

The rank of a matrix does not depend on the field in which its entries are read: a rational matrix has the same rank over Q\mathbb QQ, R\mathbb RR and C\mathbb CC, because rank is computed by Gaussian elimination, which never leaves the field of the entries. For 3-tensors, arrays A=[ ⁣[aijk] ⁣]\mathcal A = [\![a_{ijk}]\!]A=[[aijk​]] with three indices, this fails. Tensor rank governs the…

8 thms2 active usersReviewed
🏆Completed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

New Techniques for Noninteractive Zero-Knowledge 2: On a Perfectly Hiding Key the Circuit-SAT Proof from a Homomorphic Proof Commitment Is Perfect Zero-KnowledgeResearch Paper

A non-interactive zero-knowledge (NIZK) proof lets a prover convince a verifier that a statement is true by sending a single message, computed from a common reference string σ\sigmaσ that both parties share, without revealing anything beyond the truth of the statement. NIZK proofs were introduced by Blum, Feldman and Micali (STOC 1988) and are a building…

10 thms2 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: mikedeng1

New Techniques for Noninteractive Zero-Knowledge 1: The Circuit-SAT Proof from a Homomorphic Proof Commitment Is Perfectly Complete, Perfectly Sound and a Perfect Proof of Knowledge on Binding KeysResearch Paper

A non-interactive zero-knowledge (NIZK) proof lets a prover convince a verifier that a statement is true by sending a single message, computed from a common reference string σ\sigmaσ that both parties share, without revealing why the statement is true. NIZK proofs were introduced by Blum, Feldman and Micali (STOC 1988). They are a basic component of…

9 thms2 active usersReviewed
🏆Completed
Quantum Information·Captain: marwahaha

Regular trajectories, pruning and quantum parityOpen Problem

The parity function tests whether a shallow quantum circuit can combine information from all input bits. Polynomially many ancillary qubits make the measured-output formulation substantially stronger than a restriction to clean final registers. The pinned manuscript supplies the research context.

19 thms2 active usersReviewed
PreviousPage 18 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