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
Theoretical Computer Science·Captain: Shuze Chen

On the Complexity of Intersection Non-emptiness for Star-Free Language Classes: Logspace completeness at the first half-levelResearch Paper

Several specifications of a finite-state system may constrain the same sequence of events. Satisfying all of them requires a word accepted by every specification automaton. Intersection nonemptiness asks whether such a word exists. Its input is a list of finite automata, so the length of that list matters along with the sizes of the individual automata. The…

10 thms1 active userReviewed
Theoretical Computer Science·Captain: mikedeng1

An Explicit and Optimal Separation of BPP from NP in Number-on-Forehead Communication ComplexityResearch Paper

Communication complexity measures how many bits participants must exchange when each sees only part of an input. In the number-on-forehead model, there are kkk participants and kkk input blocks: participant iii sees every block except block iii. Their overlapping knowledge makes lower bounds difficult. A separation between randomness and nondeterminism asks whether…

13 thms1 active userReviewed
AlgebraCombinatoricsTheoretical Computer Science·Captain: iris

Private PCPs from Product ExpansionResearch Paper

The PCP theorem says that the witness of an NP problem can be written as a proof that a verifier checks by reading a few random positions. Its quantum analogue for QMA is open. A main obstacle is local indistinguishability: a witness stored in a quantum code of distance ddd cannot be read from any d−1d-1d−1 positions, so local tests cannot tell a YES witness from a…

36 thms1 active userReviewed
Captain: mikedeng1

Parity and Pattern Detection in Permutation StreamsResearch Paper

In the permutation streaming model the input π1,…,πn\pi_1,\dots,\pi_nπ1​,…,πn​ is promised to be a permutation of [n]={1,…,n}[n]=\{1,\dots,n\}[n]={1,…,n}, its values arrive one at a time, and an algorithm must decide a property of the permutation with as little memory as possible. The promise removes every problem that is invariant under reordering, so what remains are questions about the order…

15 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

The Quantumly Fast and the Classically ForriousResearch Paper

The Forrelation problem was introduced by Aaronson (STOC 2010) as a query problem that separates quantum from classical computation as strongly as possible. Two Boolean functions χf,χg:F2n→{−1,1}\chi_f,\chi_g:\mathbb F_2^n\to\{-1,1\}χf​,χg​:F2n​→{−1,1} are given as black boxes, and the task is to decide whether χg\chi_gχg​ is correlated or anticorrelated with the Fourier transform of χf\chi_fχf​. A…

19 thms1 active userReviewed
Graph TheoryProbability·Captain: mikedeng1

A Fully Polynomial Randomized Approximation Scheme for Hypergraph UnreliabilityResearch Paper

Network unreliability quantifies the risk that independent component failures disconnect a system. A hyperedge models one component connecting a whole set of vertices, so one failure can remove a connection among arbitrarily many endpoints. All-terminal unreliability is the probability that the surviving hypergraph has more than one connected component. The…

29 thms1 active userReviewed
Theoretical Computer Science·Captain: mikedeng1

Subset Sum via Partial MatchResearch Paper

Subset sum is a basic NP-complete problem and a standard test case for exact exponential algorithms: given integers and a target, decide whether some subset sums to the target. For more than fifty years the best worst-case running time had exponent n/2n/2n/2, and whether that exponent can be lowered by any constant was a long-standing open question.

26 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

The Exact Complexity of Majority in Depth-Three Circuits with Bottom Fan-in ThreeResearch Paper

Majority is the Boolean decision that accepts an input when at least half its variables are one, accepting ties. Its description is short, but the size of a circuit implementing it depends substantially on the permitted gates and depth. For a fixed architecture, an exponential upper and lower bound can still leave an exponential gap if their bases differ.…

22 thms1 active userReviewed
AlgebraComputational Complexity·Captain: mikedeng1

Factor Closure in Noncommutative Algebraic ComplexityResearch Paper

A basic structural question in algebraic complexity is whether factors of a polynomial with a small circuit also have small circuits. In the commutative setting small-circuit bounds for factors were established by Kaltofen ([10]), closure of commutative VNP in characteristic zero and sufficiently large characteristic was proved by Chou, Kumar and Solomon…

19 thms1 active userReviewed
Theoretical Computer Science·Captain: mikedeng1

Breaking the Parity Barrier for Constant-Depth CircuitsResearch Paper

A Boolean circuit computes a bit by combining input bits through logical gates. Circuit complexity asks how many gates a specified function needs when its depth is restricted. Lower bounds separate computational resources even when the function itself is easy to evaluate. For circuits using AND and OR gates with unrestricted fan-in, parity has long provided…

36 thms1 active userReviewed
Captain: mikedeng1

Computing faster with a full memory: Catalytic algorithms break time-space lower boundsResearch Paper

A catalytic algorithm, introduced by Buhrman, Cleve, Koucký, Loff and Speelman (STOC 2014), has a small clean work tape and a large dirty work tape. The dirty tape starts with arbitrary content the algorithm cannot choose, and must be returned intact at the end. The original question was whether such memory helps at all, and the first answers concerned…

8 thms1 active userReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Maximum Matching and Related Problems in Catalytic LogspaceResearch Paper

A matching in a graph is a collection of edges that share no vertices. A maximum matching has as many edges as any such collection. Matching is a basic problem in combinatorial optimization, but the computational resources needed to construct one depend on the machine model. A polynomial-time procedure can retain intermediate data that do not fit in…

28 thms1 active userReviewed
Probability·Captain: mikedeng1

Perfect Local Sampling and Subquadratic Counting below the Hard-Core Uniqueness ThresholdResearch Paper

The hard-core model samples an independent set III of a finite graph with probability proportional to λ∣I∣\lambda^{|I|}λ∣I∣; at λ=1\lambda=1λ=1 this is the uniform distribution on independent sets. It is a standard test case for the computational phase transition in counting and sampling, because the tree-uniqueness threshold …

25 thms1 active userReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

A King for Almost EveryoneResearch Paper

A collection of pairwise contests can have cyclic outcomes: one contestant defeats a second, the second defeats a third, and the third defeats the first. A useful substitute for a contestant who defeats everyone is a king: a vertex that reaches every other vertex either directly or through one intermediary. The question here concerns the information needed…

10 thms1 active userReviewed
Algebra·Captain: mikedeng1

Almost-Linear Modular Composition over Arbitrary Commutative RingsResearch Paper

Polynomial algorithms often need to substitute one polynomial into another while retaining only its remainder modulo a third polynomial. This operation is called modular composition. It describes evaluation in a polynomial quotient algebra, so it appears whenever an algebraic element is represented by a polynomial relation. Over finite fields it occurs in…

16 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

Computation in Anonymous Directed Dynamic Networks: Exact Worst-Case Termination Time and Network-Wise IntractabilityResearch Paper

Distributed systems can need to know how many participants they contain even when communication links change from round to round. Counting asks every participant to determine this number exactly and then stop. Without identifiers, equal messages need not originate from the same participant. Receiving a correct estimate is also different from having enough…

28 thms1 active userReviewed
Discrete GeometryOperations ResearchOptimization+1·Captain: mikedeng1

4-Block Integer Programming is in FPTResearch Paper

An integer program chooses integer values for variables subject to linear equations and bounds, while minimizing a specified objective. Models with repeated local constraints occur in scheduling, allocation and stochastic optimization. Their size can grow with the number of local blocks even when the form of each block stays small. A useful algorithm must…

14 thms1 active userReviewed
CombinatoricsProbability·Captain: mikedeng1

Metric Testing: A Characterization of One-Sided TestabilityResearch Paper

A matrix can be too large to inspect completely even when the property being tested is defined on small collections of its labels. A one-sided tester must accept every valid matrix with probability one while finding a violation with probability at least two thirds whenever repairing the matrix requires a fixed positive fraction of its entries to change. The…

25 thms1 active userReviewed
Harmonic AnalysisLinear algebra·Captain: mikedeng1

Lower Bounds for Memory-Efficient Differentially Private Continual CountingResearch Paper

Differentially private training of machine-learning models repeatedly releases noisy prefix sums of gradients. The mechanism with the best known accuracy for this task is the matrix mechanism: factor the prefix-sum matrix AnA_nAn​ as An=BCA_n=BCAn​=BC, and release B(Cx+z)=Anx+BzB(Cx+z)=A_nx+BzB(Cx+z)=An​x+Bz for Gaussian noise zzz. Fichtenberger, Henzinger and Upadhyay gave a lower-triangular Toeplitz sq…

37 thms1 active userReviewed
Quantum Information·Captain: mikedeng1

Exponential quantum-classical query separations for cyclic ForrelationResearch Paper

A quantum computation can encode information in the trace of a product of matrices. Understanding the classical cost of estimating that trace helps distinguish the resources supplied by quantum access from those supplied by ordinary oracle queries. The one-clean-qubit model, also called DQC1, studies computations with one initially pure qubit and an…

12 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

Monotone circuit lower bounds from spread matchingsResearch Paper

A monotone Boolean circuit computes with AND and OR gates only. Exponential lower bounds for such circuits are a long line of unconditional results in circuit complexity, and matching resisted improvement for decades. Razborov proved in 1985 that computing matching requires monotone circuits of size nΩ(log⁡n)n^{\Omega(\log n)}nΩ(logn). That bound stood until Cavalar, Göös,…

14 thms1 active userReviewed
CombinatoricsOptimization·Captain: mikedeng1

Randomized Query Lower Bounds for Submodular Function MinimizationResearch Paper

Submodular function minimization asks for a least-value subset when the only access to a set function is through queries of its values. It provides a common optimization framework for functions with diminishing marginal returns. Even after restricting attention to this structured class, the number of oracle calls needed to solve the problem remains a…

21 thms1 active userReviewed
Captain: mikedeng1

On the Complexities of Interactive Proofs of ProximityResearch Paper

A verifier checking a large object may have two limited resources: how many input positions it reads and how many bits it exchanges with an untrusted helper. Interactive proofs of proximity allow the helper to know the entire object while the verifier has only query access. The intended decision is approximate: membership must be accepted, and inputs…

10 thms1 active userReviewed
Captain: mikedeng1

Enumerating Complexity RevisitedResearch Paper

A program can describe an infinite set by printing its elements indefinitely. This makes description length meaningful even when no finite output string contains the whole object. Researchers in computability and algorithmic information theory ask how much shorter such a description can become when the program receives random bits. The relevant success…

10 thms1 active userReviewed
Theoretical Computer Science·Captain: mikedeng1

Associativity of Multiplication Is Hard for ResolutionResearch Paper

SAT and SMT solvers handle bit-vector arithmetic by bit-blasting: every bit becomes a Boolean variable and every multiplication a multiplier circuit, encoded as a CNF formula. Formulas that require reasoning about multiplication remain a known weak point of this approach in bounded model checking, arithmetic hardware verification and the verification of…

28 thms1 active userReviewed
PreviousPage 15 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