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
Optimization·Captain: mikedeng1

Polynomial-Time Algorithms for Nuclear Tensor Norms and Multipartite Quantum SeparabilityResearch Paper

A real tensor is an array with several indices. Its size grows exponentially with its number of indices, but algorithms are measured against that explicit array size. A basic geometric question asks whether the array belongs to the unit ball of the nuclear norm, which measures the cost of expressing it as a sum of product arrays. Bernasconi and Malavolta…

31 thms2 active usersReviewed
Quantum Information·Captain: iris

Depth-Optimal Quantum CompilationResearch Paper

A quantum algorithm is usually written with arbitrary single-qubit rotations, while fault-tolerant hardware and the circuit classes of complexity theory offer only a fixed, finite gate set. Every rotation therefore has to be compiled: replaced by a circuit over the fixed set that approximates it to some precision ε\varepsilonε. The Solovay–Kitaev theorem and…

42 thms2 active usersReviewed
Algorithmic Game TheoryLinear algebraTheoretical Computer Science·Captain: Shuze Chen

Finding a Positive Index Nash Equilibrium is PPADS-CompleteResearch Paper

Every finite game has a Nash equilibrium, but equilibria are not all alike. In a nondegenerate two-player game, each equilibrium carries a Shapley index of +1+1+1 or −1-1−1, a local orientation that sums to +1+1+1 over all equilibria. The index is an established selection criterion: an isolated equilibrium is sustainable exactly when it has index +1+1+1 (Govindan et al.,…

38 thms2 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

Sounder, shorter, and simpler PCPs from HDX neighborhoodsResearch Paper

A two-query probabilistically checkable proof (PCP) lets a verifier check membership in an NP language by reading two symbols of a proof. Its three parameters are the soundness error ε\varepsilonε (the largest acceptance probability on a false claim), the proof length and the alphabet size. Two-query PCPs with small soundness are the starting point of most…

18 thms2 active usersReviewed
Complexity TheoryMachine Learning·Captain: Shuze Chen

The Complexity of ReLU Network Synthesis from a Parameter MultisetResearch Paper

Training a neural network usually means fixing an architecture and searching a continuous space of weights. A different question separates the numbers from the architecture: the parameter values are supplied in advance, as a finite multiset, and one asks whether some ReLU network with a bounded number of neurons can be wired up and have those numbers placed…

19 thms2 active usersReviewed
CombinatoricsLogicTheoretical Computer Science·Captain: Shuze Chen

Polynomial Interpolation for Sherali-Adams Lower BoundsResearch Paper

Sherali-Adams is the standard proof system for refuting unsatisfiable CNF formulas with linear programming. Its refutations are linear-programming certificates over products of literals, the same objects that underlie the Sherali-Adams hierarchy of LP relaxations (Sherali–Adams 1990). It polynomially simulates Resolution, the proof system whose lines are…

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

Word Length and Diameter in Permutation GroupsResearch Paper

A finite group GGG generated by a set Σ\SigmaΣ raises a basic quantitative question: how many generators must be multiplied to reach a given element? The answer is measured by the length ℓ(g,Σ)\ell(g,\Sigma)ℓ(g,Σ) of an element and the diameter diam⁡(G,Σ)\operatorname{diam}(G,\Sigma)diam(G,Σ) of the group. Geometrically they are distances in the directed Cayley graph of GGG, and they appear in…

25 thms2 active usersReviewed
Mathematical Logic·Captain: mikedeng1

Approximate Counting and the Provability of Combinatorial PrinciplesResearch Paper

Randomized algorithm analysis repeatedly estimates the fraction of inputs accepted by a Boolean computation. A formal theory of approximate counting specifies which assertions about those estimates can be used in a proof. Its strength matters when comparing probabilistic reasoning with combinatorial principles. Korten, Li, Oliveira and Ren study this…

17 thms2 active usersReviewed
Algebraic GeometryComplexity Theory·Captain: iris

Some algebraic and geometric computations in CH via Chow formsResearch Paper

Decomposing an algebraic variety into equidimensional components is a basic task of computer algebra: most algorithms for irreducible decomposition first split a variety by dimension and then factor each piece. Andrews, Garg, Oliveira and Schost (arXiv:2611.05289) place several problems about equidimensional components in the counting hierarchy CH, where…

38 thms2 active usersReviewed
Graph TheoryQuantum Information·Captain: mikedeng1

A Quantum Lower Bound for Triangle FindingResearch Paper

A triangle is a set of three distinct vertices joined by all three possible edges. In the adjacency-matrix query model, a graph is hidden and an algorithm learns whether two vertices are adjacent by querying their pair. Triangle finding asks the algorithm to return a triangle whenever one exists. The resource being measured is the number of queries;…

20 thms2 active usersReviewed
ProbabilityQuantum InformationTheoretical Computer Science·Captain: mikedeng1

Quantum Query Lower Bounds from Classical Moment MatchingResearch Paper

Many properties studied in property testing and distribution estimation are symmetric: they depend on a function f:[N]→[N]f:[N]\to[N]f:[N]→[N] only through how often each output value occurs. Examples are the number of distinct values (support size), element distinctness, collision-freeness, and kkk-distinctness. A standard way to prove classical query lower bounds for such…

20 thms2 active usersReviewed
Quantum InformationTheoretical Computer Science·Captain: iris

Optimal Quantum Junta TestingResearch Paper

A Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} is a kkk-junta if its value depends on at most kkk of its nnn input bits. Deciding whether an unknown function has this form, or is far from every such function, is one of the basic problems of property testing: it is the test that a learner for juntas, or for functions of few relevant features, runs before it commits to a…

32 thms2 active usersReviewed
Machine LearningProbabilityStatistics+1·Captain: Shuze Chen

Average-case reductions for k-XOR and Tensor PCAResearch Paper

Planted noisy kkk-XOR and Tensor PCA are two canonical average-case problems. Both have a hidden sign vector, both have a wide range of parameters where the hidden vector is determined by the data but no polynomial-time algorithm is known to find it, and both are used as hardness assumptions: kkk-XOR for learning halfspaces, DNFs and tensor completion and in…

18 thms2 active usersReviewed
CombinatoricsLinear algebraTheoretical Computer Science·Captain: Shuze Chen

More on Correlation Bounds for PolynomialsResearch Paper

How well can low-degree polynomials over F2\mathbb F_2F2​ predict an explicit Boolean function? Small correlation with all degree-ddd polynomials is the input to the polynomial method for circuit lower bounds (Razborov, Smolensky) and a prerequisite for progress on questions in multiparty communication, matrix rigidity and pseudorandomness (see Viola's survey [5], …

24 thms2 active usersReviewed
AlgebraAlgebraic GeometryInformation Theory·Captain: Shuze Chen

Quasilinear Encoding at the Quadratic Alphabet Scale via Short Cartier BasesResearch Paper

A linear code over a finite field FQ\mathbb F_QFQ​ encodes KKK message symbols as NNN codeword symbols; its minimum distance ddd guarantees recovery from ttt errors and eee erasures whenever 2t+e<d2t+e<d2t+e<d. The Singleton bound gives d≤N−K+1d\le N-K+1d≤N−K+1. For a target gap 0<ε<10<\varepsilon<10<ε<1 one asks for codes with

19 thms2 active usersReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: Shuze Chen

Tight Bounds for Conservative Pointer JumpingResearch Paper

In the number-on-the-forehead (NOF) model of communication of Chandra, Furst and Lipton (CFL83), an input is split into kkk parts and each of kkk players sees every part except the one on its own forehead. Lower bounds in this model are hard to prove because the players' views overlap so much, and they would be valuable: by Yao (Yao90), Håstad and Goldmann (HG91…

19 thms2 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

Constrained Directed Separation: Algorithms and ClassificationsResearch Paper

Directed Multicut asks to delete at most kkk nonterminal vertices of a digraph so that no directed path remains from the first to the second terminal of any demand. Olkowski and Ramanujan study what happens when the deleted vertices must also satisfy a structural condition: the subdigraph they induce must belong to a fixed hereditary class H\mathcal HH.…

27 thms2 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

Once-Paid Subsequences and the Cost of Min-Plus ApproximationResearch Paper

Many sequence problems are solved by a prefix recurrence that uses only minimum and addition, and such a recurrence, once its structure is fixed before the costs are known, is a min-plus circuit. Lower bounds on min-plus circuits therefore say which recurrences cannot exist, independently of how clever the choice of states is (Jukna–Seiwert 2020).

18 thms2 active usersReviewed
Complexity Theory·Captain: mikedeng1

From a finite subgroup of SO(3)SO(3)SO(3): C2C_2C2​ leads to a Holant dichotomyResearch Paper

A graph can describe a counting problem through local rules. For example, assigning a bit to each edge and requiring exactly one incident bit to be one at each vertex counts perfect matchings. More general rules attach a weight to each local assignment, and the answer sums products of these weights over all edge assignments. A Holant problem asks for this…

30 thms2 active usersReviewed
Graph Theory·Captain: mikedeng1

Exact Mean Certificates under Sparse Graph CorruptionResearch Paper

A network of sensors can report a plausible average even when a few individual readings are arbitrary. A known bound on how much the true value changes across an edge supplies information beyond the reports. The question is then how much uncertainty about the network mean survives a particular observation. The distinction matters when an application needs…

32 thms2 active usersReviewed
Quantum Information·Captain: mikedeng1

Optimal Quantum Algorithms for Ordered SearchResearch Paper

Finding the first occurrence of a target in a sorted list is a basic comparison problem. Classical binary search uses logarithmically many comparisons. A quantum query can compare a superposition of positions, so the relevant question is how much this changes the coefficient of the logarithm when the answer must be correct with certainty. The held…

19 thms2 active usersReviewed
Optimization·Captain: mikedeng1

One-point value of a combinatorial generating series as a complexity measureResearch Paper

Many combinatorial problems ask for a cheapest feasible object, while their counting versions ask how many objects exist. The number of objects attaining the minimum is a third quantity: knowing one minimum value does not itself report its multiplicity. This mission concerns a generating function that records every feasible object's cost and asks what…

25 thms2 active usersReviewed
Linear algebraProbabilityTheoretical Computer Science·Captain: Shuze Chen

Quadratic ExtractorsResearch Paper

Randomized algorithms, cryptography and distributed protocols assume access to uniform random bits, while physical sources of randomness are biased and correlated. A randomness extractor is a deterministic function that turns samples of such a weak source into nearly uniform bits. No single extractor works for every source with a given amount of entropy:…

25 thms2 active usersReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

Deterministic Connectivity Sketches Under Edge DeletionsResearch Paper

A graph is to be compressed so that, after any set of its edges is deleted, one can still tell whether the remaining graph is connected. The question links one-way communication, fault-tolerant connectivity oracles, and single-pass dynamic graph streaming. With randomness it is well understood: the linear sketches of Ahn, Guha and McGregor (AGM12) use …

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

Deterministic Algorithms for Low Individual Degree Factors of Sparse PolynomialsResearch Paper

Factoring multivariate polynomials is a basic task of computer algebra. For polynomials given by circuits or as black boxes it has efficient randomized algorithms (Kaltofen; Kaltofen–Trager), surveyed in §1 of the source, but no deterministic one is known even for sparse polynomials, those with few monomials. Derandomizing factorization is tied to…

23 thms2 active usersReviewed
PreviousPage 4 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