Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Computational Complexity

136 missions · 6 completed

Missions

Open130Completed6All136
AlgebraLinear algebraTheoretical Computer Science·Captain: Shuze Chen

Hitting Sets for Polynomials with Small Hasse Derivative Space over Arbitrary Characteristic FieldsResearch Paper

Polynomial identity testing (PIT) asks whether a polynomial given by an algebraic circuit is the zero polynomial. In the blackbox setting the circuit can only be evaluated. A hitting set supplies a fixed family of queries that detects every nonzero polynomial in the class. A standard way to do so is a hitting set generator: a low-degree polynomial map GGG in…

24 thms2 active usersReviewed
AlgebraTheoretical Computer Science·Captain: Shuze Chen

Uniform Subpower Membership for Finite Mal'tsev AlgebrasResearch Paper

A finite algebra AAA is a finite set with finitely many operations. Given tuples g1,…,gm∈Ang^1, \dots, g^m \in A^ng1,…,gm∈An, the subpower membership problem asks whether a target tuple can be obtained from them by applying the operations of AAA coordinatewise, any number of times. The set of obtainable tuples, Sg(G)\mathrm{Sg}(G)Sg(G), can have exponentially many elements in nnn, so the…

13 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: Shuze Chen

A Little Derandomization Goes a Long Way: Unconditional Circuit Lower Bounds using Low-Degree PITResearch Paper

Two lower-bound questions have resisted decades of work. The first is Boolean: does every problem solvable in nondeterministic exponential time have small Boolean circuits? The second is algebraic: Valiant's conjecture that VP≠VNP\mathrm{VP}\neq\mathrm{VNP}VP=VNP, i.e. that some explicit polynomials (the permanent, the Hamiltonian cycle polynomial) cannot be computed…

22 thms2 active usersReviewed
Algorithmic Game TheoryProbability·Captain: Shuze Chen

On the Computation of Sparse Equilibria in Normal-Form GamesResearch Paper

Correlated equilibria (CE) and coarse correlated equilibria (CCE) of a normal-form game are computable in polynomial time by linear programming, and no-regret dynamics converge to them. The price is the representation: an equilibrium found this way may correlate the players arbitrarily, through a joint distribution over action profiles whose support grows…

31 thms2 active usersReviewed
CombinatoricsGraph TheoryLinear algebra+1·Captain: Shuze Chen

Entrywise Logarithmic Matrix Algebra and Dichotomy of Planar Graph HomomorphismsResearch Paper

A graph homomorphism partition function assigns to a symmetric weight matrix M∈Rn×nM\in\mathbb R^{n\times n}M∈Rn×n and a graph G=(V,E)G=(V,E)G=(V,E) the number

23 thms2 active usersReviewed
CombinatoricsLinear algebra·Captain: mikedeng1

Kadison–Singer in Deterministic Polynomial TimeResearch Paper

Matrix discrepancy asks how to assign plus and minus signs to a collection of matrices so their signed sum is small. A bound independent of the matrix dimension is useful when the matrices represent many simultaneous quadratic measurements: cancellation must hold in every direction, rather than for a single scalar sum. The Kadison–Singer problem, in its…

20 thms2 active usersReviewed
Captain: mikedeng1

Better Upper Bounds for Square-Root-Sum and Straight-Line Program PositivityResearch Paper

A short arithmetic computation can describe an integer too long to write out efficiently. Repeated squaring already produces this effect using only the literal 1, addition and multiplication. Determining the sign of the resulting integer is therefore a separate computational question from evaluating it in binary. This question matters in exact numerical…

9 thms2 active usersReviewed
cryptographyQuantum InformationTheoretical Computer Science·Captain: iris

Quantum Multi-Collision Lower Bounds for Arbitrary Bounded TypesResearch Paper

Collision finding is a basic benchmark of quantum query complexity and of post-quantum security: the cost of finding inputs with equal outputs bounds the security of hash functions and of protocols built from them against quantum attackers. Two refinements matter in practice. One asks for many collisions at once (security reductions for multi-instance…

31 thms2 active usersReviewed
Group TheoryTheoretical Computer Science·Captain: Shuze Chen

Faster Isomorphism for Groups of Class 2Research Paper

The group isomorphism problem asks whether two finite groups, given by their Cayley tables (multiplication tables), are isomorphic. It lies in NP, is not known to be in P or NP-complete, and is a recognised bottleneck for graph isomorphism: Babai's quasipolynomial-time algorithm for graphs does not carry over, and the classical bound for groups of order NNN is…

24 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: Shuze Chen

Exact Parallel Sampling without Maximal Independent SetsResearch Paper

A counting oracle for a distribution μ\muμ on [q]n[q]^n[q]n answers a query (S,y)(S,y)(S,y) with the marginal probability Pr⁡X∼μ[XS=y]\Pr_{X\sim\mu}[X_S=y]PrX∼μ​[XS​=y]. Any-order autoregressive and masked diffusion models provide exactly this access. With it, μ\muμ can be sampled coordinate by coordinate, but that takes nnn sequential rounds. The question of parallel sampling is how many adaptive rounds…

23 thms2 active usersReviewed
Quantum Information·Captain: mikedeng1

IQP circuits for 2-ForrelationResearch Paper

Quantum query algorithms can access a function on a superposition of addresses. Their advantage can depend on the order in which they apply transformations between oracle calls. Instantaneous Quantum Polynomial-time circuits, abbreviated IQP circuits, restrict this freedom: between two complete Hadamard layers, every gate is diagonal in the computational…

22 thms2 active usersReviewed
Complexity Theory·Captain: mikedeng1

Approximating Polynomials for De Morgan Formulas with Optimal Coefficient L1-Norm BoundsResearch Paper

Polynomial approximations of Boolean functions are a basic tool in complexity theory. A real polynomial PPP pointwise approximates a Boolean function FFF if ∣P(x)−F(x)∣≤1/3|P(x)-F(x)|\le 1/3∣P(x)−F(x)∣≤1/3 on every input of the Boolean cube. Two measures of PPP matter: its degree, which governs quantum query lower bounds and learning algorithms, and its coefficient ℓ1-norm ∥P∥1\|P\|_1∥P∥1​, the sum of…

19 thms2 active usersReviewed
Combinatorics·Captain: mikedeng1

Breaking the 2n2^n2n barrier for graph kkk-coloringResearch Paper

A proper coloring assigns colors to vertices so that adjacent vertices receive different colors. Exact algorithms for deciding whether a graph admits a specified number of colors are studied in computational complexity because their running times measure how much of an exponential search can be avoided. The relevant parameter here is the number of vertices,…

12 thms2 active usersReviewed
Convex OptimizationQuantum InformationRandom Matrix Theory·Captain: mikedeng1

Quantum lower bounds for convex optimization and real matrix-vector query problemsResearch Paper

Convex optimization asks for a feasible point whose objective value is close to the smallest feasible value. When the objective is available only through queries, the number of queries describes how much information an algorithm needs about an unknown function. Quantum algorithms can query superpositions of points, so a classical query lower bound does not…

30 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Triangle-Freeness: Estimation Is as Easy as TestingResearch Paper

An algorithm examining a large graph may have time to inspect only a small part of its adjacency matrix. Property testing asks whether the graph has a specified property or requires a substantial number of edge changes to acquire it. Distance estimation asks how many changes are needed, to a prescribed additive accuracy. For triangle-freeness, a tester can…

17 thms2 active usersReviewed
Machine Learning·Captain: mikedeng1

Spatial Communication Complexity of Agnostic Halfspace LearningResearch Paper

Moving data costs energy, and in a circuit the cost grows with the distance a bit travels. Grover's bit-meter measure charges every transmitted bit by the length of the wire it crosses (Grover 2015); with it, Blake and Kschischang proved that decoding positive-rate codes over a binary erasure channel with exponentially small block error probability needs …

23 thms2 active usersReviewed
Machine Learning·Captain: Shuze Chen

Training a 3-node neural network is NP-complete: NP-completeness of exact training on Boolean inputsResearch Paper

Training a classifier asks for parameters that fit observed examples. Even when the data can be classified perfectly, the task of finding suitable parameters can have substantial computational cost. The question here concerns exact training: deciding whether any parameter choice makes zero mistakes on the entire supplied data set. It concerns computation on…

7 thms2 active usersReviewed
AlgebraLinear algebra·Captain: mikedeng1

The sum-of-squares complexity of linear-algebraic principlesResearch Paper

A real matrix of rank greater than rrr cannot be a product of an n×rn\times rn×r matrix and an r×nr\times nr×n matrix. This elementary obstruction becomes a different question when the permitted certificate is a polynomial identity of bounded degree. Researchers studying algebraic proof complexity ask how much degree a specified certificate system needs to express such…

10 thms1 active userReviewed
AlgebraLinear algebraTheoretical Computer Science·Captain: Shuze Chen

Partial Homogenization and the Structure of Optimal Algebraic AlgorithmsResearch Paper

A quadratic map ϕ=(ϕ1,…,ϕK)\phi=(\phi_1,\dots,\phi_K)ϕ=(ϕ1​,…,ϕK​) is a tuple of quadratic forms in variables z=(z1,…,zN)z=(z_1,\dots,z_N)z=(z1​,…,zN​). Polynomial multiplication, matrix multiplication and multiplication in an algebra such as C\mathbb CC over R\mathbb RR are all quadratic maps. Algebraic complexity theory measures how many multiplications such a map needs, and the classical count is the…

15 thms1 active userReviewed
AlgebraTheoretical Computer Science·Captain: iris

A Circuit Complexity Trichotomy For Regular LanguagesResearch Paper

Unbounded fan-in Boolean circuits are the standard model of parallel computation, and finite automata the standard model of sequential computation with constant memory. Regular languages sit where the two meet: they separate AC0\mathsf{AC}^0AC0 from NC1\mathsf{NC}^1NC1 (Furst, Saxe, Sipser 1984), any separation of ACC0\mathsf{ACC}^0ACC0 or TC0\mathsf{TC}^0TC0 from NC1\mathsf{NC}^1NC1 is…

51 thms1 active userReviewed
Machine Learning·Captain: mikedeng1

Depth Lower Bounds for ReLU Networks with Binary InputsResearch Paper

A ReLU network repeatedly forms affine combinations of available values and applies the function ReLU⁡(t)=max⁡(0,t)\operatorname{ReLU}(t)=\max(0,t)ReLU(t)=max(0,t). Its depth measures the number of computational layers, while its width measures the largest number of computed units in one layer. Researchers studying neural-network expressiveness ask how much width is needed when depth is…

10 thms1 active userReviewed
Quantum Information·Captain: mikedeng1

Exponential Quantum Advantage in Number-on-Forehead CommunicationResearch Paper

A communication problem distributes an input among several participants and asks how many bits they must exchange to compute an answer. In the number-on-forehead model, each participant sees every input block except their own. With three participants, these views overlap substantially: a fact hidden from one participant is visible to the other two. Lower…

24 thms1 active userReviewed
Harmonic AnalysisProbability·Captain: mikedeng1

Testing Fourier Sparsity Near OptimallyResearch Paper

A Boolean function f:F2n→{−1,+1}f:\mathbb F_2^n\to\{-1,+1\}f:F2n​→{−1,+1} is sss-Fourier-sparse when at most sss of its Fourier coefficients are nonzero. Sparse functions include parities and kkk-juntas (which have at most 2k2^k2k nonzero coefficients), so sparsity is one of the basic "concise representation" classes of learning theory and property testing. A tester for this class reads fff at a…

16 thms1 active userReviewed
Linear algebra·Captain: mikedeng1

Polynomial-time Tensor Decomposition under the Kruskal Condition and the Lovitz–Petrov GeneralizationResearch Paper

A tensor decomposition expresses a multidimensional array as a sum of outer products of vectors. Its factors describe separate contributions in each coordinate direction. In applications such as latent-variable estimation and spectral data analysis, a decomposition is useful when those contributions can be distinguished from other explanations of the same…

17 thms1 active userReviewed
Operations ResearchOptimization·Captain: mikedeng1

Settling the Approximability of Submodular Facility LocationResearch Paper

Submodular facility location asks how to assign clients to facilities when the cost of serving a group has diminishing marginal increments. All facilities share the same cost function. This homogeneous setting distinguishes the question from variants with a different function at each facility. It allows economies of scale while retaining the geometric…

25 thms1 active userReviewed
PreviousPage 5 of 6Next

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