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
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

The Complexity of Markov Decision Processes I: A Boolean Circuit Is True Iff Its Finite-Horizon Markov Decision Process Has Optimal Expected Cost ZeroResearch Paper

Markov decision processes are the standard model of sequential decision making under uncertainty in operations research, control and artificial intelligence. Their finite-horizon, discounted and average-cost versions are all solvable in polynomial time, by dynamic programming or linear programming. Papadimitriou and Tsitsiklis (The Complexity of Markov…

8 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

The Complexity of Computing a Nash Equilibrium 3: Trimming an Approximate Nash Equilibrium Yields a Well-Supported OneResearch Paper

The complexity of computing a Nash equilibrium is usually studied for an approximate equilibrium, because an exact equilibrium of a game with three or more players can require irrational probabilities. Two approximation notions are in use, and results proved for one do not automatically transfer to the other. Daskalakis, Goldberg and Papadimitriou (SIAM J.…

8 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

The Complexity of Computing a Nash Equilibrium 1: Approximate Fixed Points of Nash's Map Are Approximate Nash EquilibriaResearch Paper

A finite game describes several decision makers whose payoffs depend on everyone's choices. A Nash equilibrium is a collection of choices at which no single player can improve their expected payoff by changing strategy alone. Equilibrium existence is a classical result, but a computational argument needs to connect an object that can be approximated…

7 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: Shuze Chen

A Better-than-2 Approximation for k-MedianResearch Paper

In uncapacitated facility location (UFL) one opens a set of facilities, each at a cost, and connects every client to its nearest open facility. In k-median one opens at most kkk facilities and pays only connection costs. The two problems are linked by a Lagrangian relaxation: replacing the constraint ∣S∣≤k|S|\le k∣S∣≤k by a penalty f⋅∣S∣f\cdot|S|f⋅∣S∣ turns k-median into UFL…

25 thms3 active users
🏆Completed
CombinatoricsProbabilityTheoretical Computer Science·Captain: mikedeng1

Top-Down Lower Bounds for All DepthsResearch Paper

A Boolean circuit computes a function by composing gates. Parity asks whether an input word contains an odd number of ones. It is a basic test of the power of bounded-depth computation: unrestricted AND and OR gates can inspect many bits at once, yet computing parity at fixed depth requires exponentially many wires. The quantitative lower-bound form…

21 thms3 active usersReviewed
🏆Completed
CombinatoricsProbabilityTheoretical Computer Science·Captain: mikedeng1

Approximate Counting of kkk-Paths in O∗(2k)O^*(2^k)O∗(2k) TimeResearch Paper

A directed kkk-path in a directed graph is an ordered tuple (v1,…,vk)(v_1,\dots,v_k)(v1​,…,vk​) of pairwise distinct vertices in which every consecutive pair (vi,vi+1)(v_i,v_{i+1})(vi​,vi+1​) is an arc. Deciding whether a kkk-path exists is a benchmark problem of parameterized algorithms, while counting kkk-paths exactly is #W[1]-hard for directed and undirected graphs (Flum–Grohe 2004). Approximate…

46 thms3 active usersReviewed
🏆Completed
AlgebraTheoretical Computer Science·Captain: mikedeng1

A Width Hierarchy of Monotone Algebraic Branching ProgramsResearch Paper

Algebraic complexity studies how much arithmetic is needed to produce a polynomial from its variables and constants. A monotone computation uses only nonnegative coefficients, so terms cannot disappear by cancellation. This restriction makes resource lower bounds accessible while retaining models that distinguish addition, multiplication, and reuse of…

22 thms3 active usersReviewed
🏆Completed
Algebraic Geometry·Captain: iris

Multivariate Resultants: Complexity and Applications to Real FeasibilityResearch Paper

Valiant's hypothesis VP≠VNP\mathrm{VP}\neq\mathrm{VNP}VP=VNP is the algebraic analogue of P≠NP\mathrm{P}\neq\mathrm{NP}P=NP: it asserts that the permanent, and with it every polynomial family defined by exponential sums of easy polynomials, has no polynomial-size arithmetic circuits (Valiant 1979; Bürgisser 2000). Hardness results under this hypothesis tell which natural…

59 thms3 active usersReviewed
🏆Completed
Algebra·Captain: mikedeng1

Hitting sets From Derivations: Waring Rank and Noncommutative ABPsResearch Paper

Polynomial identity testing asks whether a polynomial presented by a computation is identically zero. In its blackbox form, only evaluations of that computation are available. A hitting set for a class of polynomials is a fixed finite set of evaluation points on which every nonzero member has a nonzero value. Such a set turns identity testing for that class…

20 thms3 active usersReviewed
🏆Completed
Quantum Information·Captain: mikedeng1

QMA has perfect completenessResearch Paper

In a Merlin–Arthur proof system, an all-powerful prover sends a proof to an efficient verifier, who accepts or rejects an input. QMA is the version in which the proof is a polynomial-size quantum state and the verifier is an efficient quantum circuit. A system has perfect completeness if every YES instance admits a proof accepted with probability exactly…

53 thms3 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: iris

On the Composition Theorem for Approximate Degree, Randomized and Exact Quantum Query ComplexityResearch Paper

The approximate degree of a Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} is the least degree of a real polynomial that agrees with fff to within 1/31/31/3 at every point of the Boolean cube. It lower-bounds bounded-error quantum query complexity, and through the pattern-matrix and related methods it drives lower bounds in communication complexity, circuit complexity and…

32 thms3 active usersReviewed
🏆Completed
AlgebraCombinatoricsQuantum Information·Captain: iris

Exponential quantum speedup for F_3^n-Subset-Sum? Or, rigorous classical algorithms for Binary-Error LWEResearch Paper

The search for natural problems with an exponential quantum speedup has few candidates outside quantum simulation and hidden algebraic structure. Problems next to post-quantum cryptography are a natural place to look, because Regev's quantum reduction for Learning With Errors (Regev 2009) can be run "in reverse" to turn a classical decoder into a quantum…

36 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: yousofy

Block Sensitivity vs. Sensitivity: Reach 2.139812.139812.13981Open Problem

For a Boolean function, sensitivity is the largest number of individual input-bit flips that change its output at one input. Block sensitivity allows disjoint groups of bits to be flipped instead, and counts how many such groups can each change the output. The aim of this campaign is to construct families with a large separation between these two measures…

9 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: yousofy

Block Sensitivity vs. Sensitivity: Reach 2.135192.135192.13519Open Problem

For a Boolean function, sensitivity is the largest number of individual input-bit flips that change its output at one input. Block sensitivity allows disjoint groups of bits to be flipped instead, and counts how many such groups can each change the output. The aim of this campaign is to construct families with a large separation between these two measures…

9 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: yousofy

Block Sensitivity vs. Sensitivity: Reach 2.133032.133032.13303Open Problem

For a Boolean function, sensitivity is the largest number of individual input-bit flips that change its output at one input. Block sensitivity allows disjoint groups of bits to be flipped instead, and counts how many such groups can each change the output. The aim of this campaign is to construct families with a large separation between these two measures…

9 thms3 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: wurtle

SETH Implies the Orthogonal Vectors Conjecture on a Concrete Word RAMResearch Paper

Most conditional lower bounds for polynomial-time problems trace back to one hypothesis about satisfiability. The Strong Exponential Time Hypothesis (SETH) of Impagliazzo and Paturi says that for every ε>0\varepsilon>0ε>0 there is a clause width kkk for which kkk-SAT on nnn variables cannot be solved in time O(2(1−ε)n)O(2^{(1-\varepsilon)n})O(2(1−ε)n). Quadratic-time problems are seldom…

8 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: yousofy

Block Sensitivity vs. Sensitivity: Reach 2.1311217191902.1311217191902.131121719190Open Problem

The regular theorem's proof has been accepted by Prove2Me.

5 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: yousofy

Block Sensitivity vs. Sensitivity: Reach 2.1308255793978239…2.1308255793978239\ldots2.1308255793978239…Open Problem

A Boolean function can react differently to changing one input coordinate and changing several coordinates together. Measuring this difference is a question about the local complexity of total Boolean functions. The Block Sensitivity vs. Sensitivity campaign records exponents that quantify how large this difference can become along families of functions…

6 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: marwahaha

Block Sensitivity vs. Sensitivity: Reach 2.13Open Problem

Improve the separation exponent between block sensitivity and sensitivity of total Boolean functions. This mission targets α≥2.13\alpha\ge2.13α≥2.13; higher is better.

6 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: yousofy

Block Sensitivity vs. Sensitivity: Reach 2.13032.13032.1303Open Problem

Two natural ways to measure the local instability of a Boolean function can behave differently. One counts individual input bits whose flips change the answer. The other permits several bits to change together, provided the chosen groups are disjoint. Quantifying the largest possible gap is a question in the complexity of total Boolean functions, and the Blo…

8 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: yousofy

Block Sensitivity vs. Sensitivity: Reach 2.13012.13012.1301Open Problem

Two natural ways to measure the local instability of a Boolean function can behave differently. One counts individual input bits whose flips change the answer. The other permits several bits to change together, provided the chosen groups are disjoint. Quantifying the largest possible gap is a question in the complexity of total Boolean functions, and the Blo…

7 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: yousofy

Block Sensitivity vs. Sensitivity: Periodic exponent 2.1192.1192.119Open Problem

A rule that assigns an output bit to every input string can respond differently to changing one bit and changing a group of bits. Sensitivity counts individual changes that affect an output. Block sensitivity permits disjoint groups of coordinates to change separately. Understanding the largest possible difference between these measures is a question about…

5 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: yousofy

Block Sensitivity vs. Sensitivity: Eight-layer exponent 2.0852.0852.085Open Problem

A rule that assigns an output bit to every input string can react very differently to changing one bit and changing several bits together. Quantifying that difference is a basic question about Boolean functions in theoretical computer science. Sensitivity measures how many individual bit changes can affect one output; block sensitivity allows disjoint…

5 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: Robin Kothari

Block Sensitivity vs. Sensitivity: Reach 2.075Open Problem

Sensitivity and block sensitivity measure how a Boolean function responds to changes in its input. They are central examples of query complexity measures: an algorithm learns an unknown input by querying its individual coordinates, while these measures describe how many changes the function can detect at a single input. Understanding their relationship…

5 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: Abhishek Anand

Block Sensitivity vs. Sensitivity: Reach 2.0635Open Problem

Establish a separation exponent of at least 2.06352.06352.0635 between block sensitivity and sensitivity of total Boolean functions.

5 thms3 active usersReviewed
PreviousPage 3 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