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
Combinatorics·Captain: marwahaha

Block Sensitivity vs. Sensitivity: Depth-20 ImprovementResearch Paper

Certify α≥2.006470828\alpha\ge2.006470828α≥2.006470828 by specializing OpenAI's general seed theorem to d=20d=20d=20 and M=921M=9^{21}M=921.

39 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Scheduling Problems with Two Competing Agents 7: PARTITION Reduces to Two Agents Each Bounding Their Own Makespan in the Two-Machine Flow Shop and Open ShopResearch Paper

In multi-agent scheduling, several decision makers share one processing resource, and each one cares only about the completion of its own jobs. Agnetis, Mirchandani, Pacciarelli and Pacifici (Oper. Res. 52(2), 2004) set up the two-agent version of this problem and classified its complexity for most combinations of classical objectives. Typical settings are…

14 thms5 active usersReviewed
🏆Completed
Graph TheoryLinear algebraTheoretical Computer Science·Captain: mikedeng1

Most Tensor Problems Are NP-Hard 2: Graph 3-Colorability Reduces to Tensor Bilinear Feasibility over the Reals and over the Complex NumbersResearch Paper

A matrix A∈Cn×nA \in \mathbb C^{n\times n}A∈Cn×n is singular exactly when the pair of linear systems x⊤A=0\mathbf x^\top A = 0x⊤A=0, Ay=0A\mathbf y = 0Ay=0 has a solution with both x\mathbf xx and y\mathbf yy nonzero, and this is decided in polynomial time by Gaussian elimination. The natural analogue for a 3-tensor replaces the two linear systems by three families of bilinear equations,…

25 thms5 active usersReviewed
🏆Completed
Graph TheoryLinear algebraTheoretical Computer Science·Captain: mikedeng1

Most Tensor Problems Are NP-Hard 1: Graph 3-Colorability Reduces to Deciding Whether 0 Is an Eigenvalue of a Rational 3-Tensor over the RealsResearch Paper

Eigenvalues of matrices are computable in polynomial time to any accuracy, and numerical linear algebra rests on that fact. Higher-order tensors appear in statistics (moment and cumulant tensors), signal processing, quantum information and polynomial optimization, and several notions of tensor eigenvalue were proposed for them, independently by Lim and by…

23 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

An O(√nL)-Iteration Homogeneous and Self-Dual Linear Programming Algorithm 1: In O(√nL) Predictor-Corrector Iterations It Finds LP and Dual Optima or Detects InfeasibilityResearch Paper

Interior-point methods solve linear programs in polynomially many iterations, but the classical analyses assume something about the instance before the algorithm starts: a known strictly feasible primal–dual pair, a nonempty interior, or a big-MMM bound on the feasible region of order 2L2^L2L, where LLL is the bit length of the data. In practice none of this is…

22 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

On Adaptive-Step Primal-Dual Interior-Point Algorithms for Linear Programming 3: The Potential-Reduction Algorithm in N∞⁻(β) with ρ − n of Order n² Attains Precision t in O(nt) IterationsResearch Paper

Primal–dual interior-point methods solve a linear program by following, approximately, the central path of strictly feasible primal–dual pairs. Two families dominate the theory. Path-following methods keep the iterates in a neighbourhood of the path and measure progress by the duality gap. Potential-reduction methods measure progress by a merit function,…

12 thms5 active usersReviewed
🏆Completed
ProbabilityQuantum InformationTheoretical Computer Science·Captain: mikedeng1

Strengths and Weaknesses of Quantum Computing I: Relative to a Random Oracle, a Quantum Algorithm Needs Ω(2^{n/2}) Queries to Decide Whether 1ⁿ Has a PreimageResearch Paper

Grover's algorithm (Grover 1996) finds a marked item among NNN with O(N)O(\sqrt N)O(N​) queries, a quadratic speed-up over any classical algorithm. Whether quantum computers can do substantially better on search, and so solve NP-type problems by brute force in polynomial time, was settled in the negative by Bennett, Bernstein, Brassard and Vazirani (arXiv:quant-ph/9701…

9 thms5 active usersReviewed
🏆Completed
Linear algebraOperations ResearchOptimization·Captain: mikedeng1

Some NP-Complete Problems in Quadratic and Nonlinear Programming: Copositivity Testing Is NP-Hard via Subset SumResearch Paper

Nonlinear programming algorithms are routinely advertised as finding a local minimum. Most of them only certify first-order conditions (a KKT point), and the natural next question is whether a given feasible point is in fact a local minimum. For smooth problems where the Hessian is nonsingular this is a second-order test, but in the degenerate case the test…

16 thms5 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

On the Complexity of Symmetric Boolean Functions in Multiparty Private Simultaneous MessagesResearch Paper

Secure distributed computation asks parties to disclose enough information to evaluate a function while limiting what the evaluator can learn about their individual inputs. In the private simultaneous messages model, the parties share randomness hidden from the evaluator, each sends one message, and the evaluator recovers the answer. Even when each party…

30 thms4 active usersReviewed
🏆Completed
Algebraic GeometryLinear algebra·Captain: mikedeng1

A Quadratic Lower Bound on Determinantal ComplexityResearch Paper

Determinantal representations are a basic model of algebraic computation. Valiant showed that every polynomial has one and made the size of the smallest such representation central to algebraic complexity, where proving a superpolynomial bound for the permanent is the algebraic analogue of P versus NP (Valiant 1979). Even super-linear bounds in the number…

20 thms4 active usersReviewed
🏆Completed
Discrete GeometryOperations ResearchOptimization·Captain: mikedeng1

Mixed-integer Quadratic Programming is in NP: Every Feasible Mixed-Integer Quadratic System Has a Feasible Solution of Polynomial Bit-SizeResearch Paper

Mixed-integer quadratic programming (MIQP) asks to minimize a quadratic function over the points of a polyhedron whose first ppp coordinates are integers. It contains integer linear programming, quadratic programming and combinatorial problems such as max-cut.

9 thms4 active usersReviewed
🏆Completed
Combinatorics·Captain: Abhishek Anand

Block Sensitivity vs. Sensitivity: Reach 2.127294Open Problem

Prove a separation exponent of 2.127294, building on Robin Kothari’s 2.075 construction and yousofy’s 2.105 proof with twelve nested predicates and sharper joint boundary bounds.

6 thms4 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: marwahaha

Integer multiplication: κ = 1/2^154 (OpenAI construction, frozen-154 constants)Open Problem

Multiplying two nnn-bit integers on a multitape Turing machine takes O(nlog⁡n)O(n\log n)O(nlogn) steps by the algorithm of Harvey and van der Hoeven (2021), and nlog⁡nn\log nnlogn was long conjectured to be optimal. The OpenAI manuscript Integer multiplication below nlog⁡nn\log nnlogn (September 2026) gives a machine running in time O(n L(n)1−κ)O(n\,L(n)^{1-\kappa})O(nL(n)1−κ) with κ=2−182\kappa = 2^{-182}κ=2−182, which beats nlog⁡nn\log nnlogn…

22 thms4 active usersReviewed
🏆Completed
Combinatorics·Captain: Robin Kothari

Block Sensitivity vs. Sensitivity: Reach 2.10Open Problem

Sensitivity and block sensitivity measure two ways that a Boolean function can react to changes in its input. Both are basic measures in query complexity, where the input is accessed one coordinate at a time. Their relationship asks how much a function's response to changes involving several coordinates can exceed its response to individual coordinate…

5 thms4 active usersReviewed
🏆Completed
Combinatorics·Captain: marwahaha

Block Sensitivity vs. Sensitivity: Reach 2.007Open Problem

Establish the separation exponent α≥2.007\alpha\ge2.007α≥2.007 for total Boolean functions, improving on the depth-20 specialization of OpenAI's construction.

38 thms4 active usersReviewed
🏆Completed
Number Theory·Captain: mikedeng1

Integer Factorization: Why Two-Item Joint Replenishment Is Hard 4: For Primes p_i Near 2^(λa_i), ∏p_i Has a Divisor in [⌈L⌉, ⌊U⌋] iff the a_i Split into Two Equal-Sum PartsResearch Paper

The RangeDivisor problem asks whether an integer has a divisor in a specified short interval. It is the decision problem connecting number theory to the two item periodic joint replenishment model studied by Schulz and Telha. Their Appendix starts with Partition, the problem of splitting a list of positive integers into two groups of equal sum, and…

10 thms4 active usersReviewed
🏆Completed
Quantum Information·Captain: mikedeng1

Fixed-Point Quantum Search with an Optimal Number of Queries: The Phases of Eq. (11) Give Success Probability 1 − δ²T_L(T_{1/L}(1/δ)√(1−λ))²Research Paper

Quantum search starts with a state that has some overlap with a desired target. Standard Grover iterations can increase that overlap quickly, but their success probability oscillates with the number of iterations. If the initial overlap is unknown, a sequence chosen for one value can pass the target and perform poorly at another. Earlier fixed-point…

10 thms4 active usersReviewed
🏆Completed
Algorithmic Game Theory·Captain: mikedeng1

Settling the Complexity of Computing Approximate Two-Player Nash Equilibria: An (ε, δ)-WeakNash of a Bipartite Polymatrix Game Yields a (√ε(√ε + 5), δ)-Well-Supported WeakNashResearch Paper

Computing an approximate Nash equilibrium of a two-player game is one of the central questions of algorithmic game theory. For a constant approximation ϵ\epsilonϵ, the algorithm of Lipton, Markakis and Mehta runs in quasi-polynomial time nO(log⁡n/ϵ2)n^{O(\log n/\epsilon^2)}nO(logn/ϵ2), and for a long time it was unknown whether polynomial time is possible. A. Rubinstein, Settling…

10 thms4 active usersReviewed
🏆Completed
AlgebraCombinatoricsTheoretical Computer Science·Captain: mikedeng1

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy 1: Folded Symmetric PCSPs Avoiding Parity, Majority and Alternating-Threshold Have Only C-Fixing PolymorphismsResearch Paper

A constraint satisfaction problem (CSP) asks whether variables can be assigned values so that every constraint, drawn from a fixed finite set of relations, holds. The algebraic approach to CSPs explains their complexity through polymorphisms, the operations that preserve all constraint relations; this programme culminated in the CSP dichotomy theorem of…

35 thms4 active usersReviewed
🏆Completed
AlgebraLinear OptimizationTheoretical Computer Science·Captain: mikedeng1

Algebraic Approach to Promise Constraint Satisfaction 3: BLP Solves PCSP(A, B) iff Pol(A, B) Has Symmetric Functions of All Arities iff Q_conv Maps to Pol(A, B)Research Paper

A promise constraint satisfaction problem PCSP(A,B)\mathrm{PCSP}(\mathbf A,\mathbf B)PCSP(A,B) is given by two finite relational structures with a homomorphism A→B\mathbf A\to\mathbf BA→B. An instance is a finite structure I\mathbf II over the same signature, promised to map to A\mathbf AA; the task is to find a homomorphism to the weaker structure B\mathbf BB (or, in the decision…

17 thms4 active usersReviewed
🏆Completed
AlgebraCombinatoricsTheoretical Computer Science·Captain: mikedeng1

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy 3: Pol(Γ) ⊆ Pol(Γ′) Implies Γ′ Is ppp-Definable from ΓResearch Paper

A constraint satisfaction problem (CSP) asks for an assignment of values from a finite domain DDD to variables so that every constraint, a tuple of variables required to lie in a fixed relation, is satisfied. The algebraic theory of CSPs rests on a Galois correspondence: the complexity of CSP(Γ)\mathrm{CSP}(\Gamma)CSP(Γ) is determined by the set Pol(Γ)\mathrm{Pol}(\Gamma)Pol(Γ) of…

8 thms4 active usersReviewed
🏆Completed
AlgebraCombinatoricsTheoretical Computer Science·Captain: mikedeng1

Algebraic Approach to Promise Constraint Satisfaction 1: A Minion Homomorphism Pol(A₁, B₁) → Pol(A₂, B₂) Exists iff (A₂, B₂) Is pp-Constructible from (A₁, B₁)Research Paper

A promise constraint satisfaction problem PCSP(A,B)\mathrm{PCSP}(\mathbf A,\mathbf B)PCSP(A,B) is given by two finite relational structures with a homomorphism A→B\mathbf A\to\mathbf BA→B. An instance is a third structure I\mathbf II, and the task is to answer yes if I→A\mathbf I\to\mathbf AI→A and no if I↛B\mathbf I\not\to\mathbf BI→B; the promise is that one of the two holds. Approximate…

12 thms4 active usersReviewed
🏆Completed
AlgebraTheoretical Computer Science·Captain: mikedeng1

The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs II: BLP+Affine Solves PCSP(A, B) Exactly When Pol(A, B) Has Block-Symmetric Polymorphisms of Arbitrarily High WidthResearch Paper

A promise constraint satisfaction problem PCSP(A,B)\mathrm{PCSP}(\mathbf A,\mathbf B)PCSP(A,B) asks to distinguish instances that are satisfiable in a structure A\mathbf AA from instances that are not even satisfiable in a weaker structure B\mathbf BB. Approximate graph colouring (tell 3-colourable graphs from graphs that are not 5-colourable) and …

12 thms4 active usersReviewed
🏆Completed
Linear OptimizationTheoretical Computer Science·Captain: mikedeng1

The Power of the Combined Basic LP and Affine Relaxation for Promise CSPs I: BLP+Affine Correctly Solves Every PCSP with Symmetric Polymorphisms of Arbitrarily Large AritiesResearch Paper

A constraint satisfaction problem (CSP) asks whether variables can be assigned values from a finite domain so that every constraint, drawn from a fixed list of allowed relations, is satisfied. A promise CSP (PCSP) relaxes the question: given two templates A\mathbf AA and B\mathbf BB with a homomorphism A→B\mathbf A\to\mathbf BA→B, distinguish instances satisfiable in …

11 thms4 active usersReviewed
🏆Completed
ProbabilityTheoretical Computer Science·Captain: mikedeng1

On the (Im)possibility of Obfuscating Programs 3: A Random Injection G : [K] → [L], L ≥ K², Fools Every K^δ-Query Distinguisher with Oracle G up to 1/K^δ, Except with Probability 2^(−K^δ)Research Paper

Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan and Yang proved that general-purpose program obfuscation in the virtual black-box sense is impossible (J. ACM 59(2), 2012). A natural question is whether the impossibility proof relativizes, that is, whether it survives when every party gets access to the same oracle. Proposition 4.14 of the paper shows…

9 thms4 active usersReviewed
PreviousPage 2 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