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
CombinatoricsOperations ResearchOptimization+2·Captain: mikedeng1

Maximizing Non-Monotone Submodular Functions V: Beating 1/2 for Symmetric Functions Requires Exponentially Many Value QueriesResearch Paper

Maximizing a nonnegative submodular set function without constraints contains Max Cut, Max Directed Cut and facility-location problems as special cases. In the value-oracle model an algorithm knows nothing about the function except the values f(S)f(S)f(S) of the sets SSS it queries, and it is judged by the number of queries it makes. Feige, Mirrokni and Vondrák (SIAM…

12 thms3 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Fast Algorithms for Finding Nearest Common Ancestors I: A Lower Bound for Pointer MachinesResearch Paper

The nearest common ancestor problem asks, for a rooted tree and two of its vertices xxx and yyy, for the deepest vertex that is an ancestor of both, written nca⁡(x,y)\operatorname{nca}(x,y)nca(x,y). It appears as a subroutine in string algorithms (suffix trees), in graph algorithms (path queries, dominators) and in the analysis of set-union structures. Aho, Hopcroft and Ullman (…

8 thms3 active usersReviewed
🏆Completed
AlgebraLinear algebraTheoretical Computer Science·Captain: Shuze Chen

New lower bounds on tensor rank of (n,2,m)(n,2,m)(n,2,m) matrix multiplication with GPT-6 AstraResearch Paper

Every fast matrix multiplication algorithm starts from an identity that computes a fixed-shape product with few multiplications. Strassen's 1969 algorithm (Str69) multiplies two 2×22\times 22×2 matrices with 7 instead of 8 multiplications, and applying such an identity recursively turns RRR multiplications for a k×lk\times lk×l by l×ml\times ml×m product into an …

12 thms2 active usersReviewed
🏆Completed
Quantum Information·Captain: mikedeng1

Near-optimal quantum query lower bounds on bipartiteness and expansion testing in the bounded-degree graph modelResearch Paper

A property tester inspects a small part of an input and decides whether the input has a specified property or is far from every input having that property. For a large graph, the number of inspected adjacency entries can matter more than the time needed for computations between inspections. A quantum query permits a coherent superposition of such…

47 thms2 active usersReviewed
🏆Completed
Mathematical LogicTheoretical Computer Science·Captain: iris

Hard Instances for Strong Semantic Proof Systems: CNFs for Depth-Four PC and Deep Instances for AC0[2]\mathsf{AC}^0[2]AC0[2]-FregeResearch Paper

AC0[2]-Frege is the propositional proof system whose lines are constant-depth Boolean formulas with AND, OR and parity (XOR) gates. Superpolynomial lower bounds for the corresponding circuit class have been known since Razborov and Smolensky (1987) (Razborov 1987, Smolensky 1987), but carrying these techniques over to proofs has been open since the 1990s (Be…

64 thms2 active usersReviewed
🏆Completed
CombinatoricsInformation Theory·Captain: iris

The One-and-a-Half Johnson Bound Is Tight for Proximity Gaps of General Linear CodesResearch Paper

Hash-based succinct arguments (SNARKs) such as FRI-based and STIR/WHIR-style systems test that a committed word is close to a linear code. To keep proofs short, they test many words at once by testing a single random linear combination. This batching is sound when the code has the proximity-gaps property at radius ρ\rhoρ: if fff or ggg is far from the code CCC,…

31 thms2 active usersReviewed
🏆Completed
Information TheoryTheoretical Computer Science·Captain: iris

Fourier Entropy Bounds via ApproximationsResearch Paper

A Boolean function f:{−1,1}n→{−1,1}f:\{-1,1\}^n\to\{-1,1\}f:{−1,1}n→{−1,1} has a unique Fourier expansion f=∑S⊆[n]f^(S)χSf=\sum_{S\subseteq[n]}\widehat f(S)\chi_Sf=∑S⊆[n]​f​(S)χS​, and by Parseval's identity the squared coefficients {f^(S)2}S\{\widehat f(S)^2\}_S{f​(S)2}S​ form a probability distribution on subsets of [n][n][n]. Its Shannon entropy, the Fourier entropy H(f^2)\mathbb H(\widehat f^2)H(f​2), measures how spread out the spectrum of fff is.

21 thms2 active usersReviewed
🏆Completed
Mathematical LogicTheoretical Computer Science·Captain: iris

Progress on AC0[2]-Frege Lower BoundsResearch Paper

AC0[2]-Frege is the propositional proof system whose lines are constant-depth Boolean formulas with AND, OR, NOT and parity (MOD 2) gates. Proving superpolynomial lower bounds on the size of AC0[2]-Frege refutations of explicit unsatisfiable CNFs is one of the central open problems of proof complexity: the corresponding question for circuits was settled by…

36 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
🏆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
🏆Completed
Mathematical PhysicsQuantum Information·Captain: wurtle

QMA-hardness of continuum Coulomb energy with unit nuclear chargesResearch Paper

Computing the ground-state energy of electrons in the Coulomb field of fixed nuclei is the basic problem of quantum chemistry. In quantum complexity theory, a problem is QMA-hard if every problem with polynomial-time quantum verification of a quantum witness (the quantum analogue of NP) reduces to it. Hardness was previously known for lattice models with…

20 thms2 active usersReviewed
🏆Completed
Mathematical PhysicsQuantum Information·Captain: wurtle

Continuum Coulomb hardness with binary nuclear chargesResearch Paper

Computing the ground-state energy of a molecule — electrons moving in the Coulomb field of fixed nuclei — is the central task of quantum chemistry. Quantum complexity theory asks whether it is hard even for a quantum computer: a problem is QMA-hard if every problem verifiable by a polynomial-time quantum verifier with a quantum witness reduces to it (QMA is…

11 thms2 active usersReviewed
🏆Completed
Quantum InformationTheoretical Computer Science·Captain: wurtle

Product-projection localization and the QAC0 parity lower boundResearch Paper

Parity, PARITYn(x)=x1⊕⋯⊕xn\mathrm{PARITY}_n(x)=x_1\oplus\cdots\oplus x_nPARITYn​(x)=x1​⊕⋯⊕xn​, is the standard test of whether a shallow circuit can aggregate information from all of its inputs. Classically, constant-depth circuits with unbounded fan-in AND/OR gates (AC0\mathsf{AC}^0AC0) cannot compute it: Furst, Saxe and Sipser (Math. Systems Theory 1984) and Ajtai (APAL 1983) proved superpolynomial…

32 thms2 active usersReviewed
🏆Completed
Mathematical LogicTheoretical Computer Science·Captain: wurtle

Witnessed symmetric choice is strictly stronger than choiceless polynomial time with countingResearch Paper

A logic for unordered finite structures (graphs, databases, relational inputs given up to isomorphism) must give answers that do not depend on how the input elements are named. Many polynomial-time algorithms nevertheless make arbitrary intermediate choices, for example the pivot in Gaussian elimination, without changing their final answer. Choiceless…

4 thms2 active usersReviewed
🏆Completed
Mathematical LogicTheoretical Computer Science·Captain: wurtle

Choiceless polynomial time with counting does not capture polynomial timeResearch Paper

Descriptive complexity asks whether complexity classes can be characterized by logics, without reference to machines. Immerman and Vardi (1982) showed that on ordered finite structures, first-order logic with a least fixed-point operator expresses exactly the polynomial-time queries. On unordered structures, such as graphs given only up to isomorphism, an…

4 thms2 active usersReviewed
🏆Completed
AlgebraTheoretical Computer Science·Captain: wurtle

Homogeneous depth-five lower bounds for iterated matrix multiplicationResearch Paper

Iterated matrix multiplication asks for the (1,1)(1,1)(1,1) entry of a product of ddd matrices of size w×ww\times ww×w with independent variable entries,

4 thms2 active usersReviewed
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: wurtle

Variable-dimension Weisfeiler–Leman equivalence on general and subcubic graphsResearch Paper

Weisfeiler–Leman (WL) refinement compares two graphs by repeatedly refining colors of ordered vertex kkk-tuples. For every fixed dimension kkk this is a polynomial-time procedure, with running time nO(k)n^{O(k)}nO(k). When kkk is part of the input, that computation is no longer polynomial, and the complexity of deciding the outcome becomes a question in its own right.…

5 thms2 active usersReviewed
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: wurtle

Unconditional time lower bounds for Weisfeiler–Leman equivalenceResearch Paper

The Weisfeiler–Leman (WL) method colors kkk-tuples of vertices by repeatedly recording their local extension patterns; two graphs are kkk-WL equivalent when the stable color histograms agree. For each fixed kkk the direct algorithm runs in time nO(k)n^{O(k)}nO(k): there are nkn^knk tuples and polynomially many refinement rounds. The question is whether the growing exponent is…

5 thms2 active usersReviewed
🏆Completed
Graph TheoryTheoretical Computer Science·Captain: wurtle

The complexity of identifying a graph by Weisfeiler–Leman refinementResearch Paper

The Weisfeiler–Leman (WL) algorithm refines colors of vertex tuples to test graph isomorphism, and its dimension kkk controls how much tuple information is used. A graph's Weisfeiler–Leman dimension WLdim(G)\mathrm{WLdim}(G)WLdim(G) is the least kkk for which kkk-WL refinement identifies GGG, i.e. distinguishes it from every non-isomorphic graph. This is a standard measure of the…

3 thms2 active usersReviewed
PreviousPage 5 of 7Next

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