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
Information TheoryTheoretical Computer Science·Captain: mikedeng1

On the Inherent Intractability of Certain Coding Problems: COSET WEIGHTS (Decoding a Binary Linear Code) and SUBSPACE WEIGHTS (a Codeword of Given Weight) Are NP-CompleteResearch Paper

A binary linear code is used on a noisy channel by transmitting codewords and correcting the errors at the receiver. If HHH is a parity-check matrix of the code and yyy is the received word, the receiver computes the syndrome s=yHs = yHs=yH and must find a minimum-weight error pattern zzz with zH=szH = szH=s. A second basic question is whether a code has a codeword of a given…

20 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
Numerical AnalysisOptimizationQuantum Information·Captain: mikedeng1

Optimizing Quantum Optimization Algorithms via Faster Quantum Gradient Computation: an ε-Accurate Gradient of a Smooth Analytic Function from Õ(c√d/ε · log(d/δ)) Phase-Oracle QueriesResearch Paper

Many proposed quantum optimization and machine-learning methods (variational quantum eigensolvers, QAOA, quantum classifiers) tune the real parameters of a circuit by gradient descent on an objective f:Rd→Rf:\mathbb R^d\to\mathbb Rf:Rd→R that is only accessible as a black box. Classically, a finite-difference estimate of ∇f\nabla f∇f costs on the order of ddd evaluations of fff…

14 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
🏆Completed
Combinatorics·Captain: @bwdaugherty

Block Sensitivity vs. Sensitivity: α ≥ 2.0391Open Problem

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

5 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: Leo Shaposhnik

Block Sensitivity vs. Sensitivity: Reach 2.0205Open Problem

For every ε>0\varepsilon>0ε>0 and every integer S≥2S\ge2S≥2, there exists a total Boolean function fff with s(f)≥Ss(f)\ge Ss(f)≥S and bs(f)≥s(f)2.0205−εbs(f)\ge s(f)^{2.0205-\varepsilon}bs(f)≥s(f)2.0205−ε.

15 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: marwahaha

Block Sensitivity vs. Sensitivity: OpenAI BaselineResearch Paper

Certify the separation exponent α≥2.000252407\alpha\ge2.000252407α≥2.000252407 using OpenAI's construction. Sensitivity s(f)s(f)s(f) counts individual bit flips that change the output; block sensitivity bs(f)bs(f)bs(f) counts disjoint sensitive blocks. Both are maximized over inputs. The notation bs(f,x)bs(f,x)bs(f,x) fixes one input, and 000 denotes the all-zero input.

40 thms3 active usersReviewed
🏆Completed
Theoretical Computer Science·Captain: avi

Fast Integer Multiplication on Multitape Turing Machines: Schönhage–Strassen and the ToolkitResearch Paper

Every fast integer-multiplication algorithm in the literature is stated for the multitape Turing machine. The algorithms are built from a small set of standard subroutines whose costs are usually quoted as "well known":

15 thms3 active usersReviewed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

Tight Complexity Bounds for Optimizing Composite Objectives III: Any Deterministic Algorithm with Gradient and Prox Oracles Needs Ω(m√(γ/λ)·log(λε₀/(γε))) Queries on Smooth Strongly Convex SumsResearch Paper

Many problems in machine learning and statistics minimize an average of component losses, F(x)=1m∑i=1mfi(x)F(x)=\frac1m\sum_{i=1}^m f_i(x)F(x)=m1​∑i=1m​fi​(x): one term per training example, per data shard, or per block of a decomposed objective. Incremental methods such as SAG, SVRG, SAGA, SDCA and their accelerated variants touch one component at a time, so the natural measure of their work…

10 thms3 active usersReviewed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

Tight Complexity Bounds for Optimizing Composite Objectives I: Any Deterministic Algorithm with Gradient and Prox Oracle Access Needs Ω(mLB/ε) Queries on Sums of m Convex L-Lipschitz FunctionsResearch Paper

Many optimization problems minimize the average of component losses: one loss per observation, machine, or term in an objective. When an algorithm can inspect one component at a time, the number of component queries is a useful measure of work. A component oracle can provide more than a value or subgradient: a proximal point summarizes a global minimization…

8 thms3 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationTheoretical Computer Science·Captain: mikedeng1

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy 2: The LP Algorithm Decides PCSPs with Majority or Alternating-Threshold Polymorphisms of All Odd AritiesResearch Paper

A constraint satisfaction problem (CSP) asks whether variables can be assigned values so that every constraint of a given instance holds. Feder and Vardi conjectured, and Bulatov and Zhuk proved in 2017, that every CSP over a finite set of relations is either polynomial-time solvable or NP-complete, and that the answer is governed by the polymorphisms of…

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

Promise Constraint Satisfaction: Algebraic Structure and a Symmetric Boolean Dichotomy 4: F = Pol(Γ) for a Finite Γ iff F Is Projection-Closed, Finitizable and Contains the IdentityResearch Paper

A constraint satisfaction problem (CSP) asks whether variables ranging over a finite domain DDD can be assigned values so that every constraint from a fixed finite list of relations is satisfied. A central organizing principle of the algebraic theory of CSPs is that the complexity of CSP(Γ)\mathrm{CSP}(\Gamma)CSP(Γ) is governed by its polymorphisms, the functions …

6 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: mikedeng1

Algebraic Approach to Promise Constraint Satisfaction 2: Pol(K_k, K_{2k−1}) Has No Olšák Function, So It Maps by a Minion Homomorphism to Pol(H₂, H_K)Research Paper

Given a graph that is promised to be kkk-colourable, how many colours are needed to find a proper colouring in polynomial time? The decision version asks to distinguish kkk-colourable graphs from graphs that are not even ccc-colourable. It has been studied since Garey and Johnson (1976) and is conjectured to be NP-hard for all fixed 3≤k≤c3 \le k \le c3≤k≤c. This is the appr…

9 thms3 active usersReviewed
🏆Completed
AlgebraCombinatoricsTheoretical Computer Science·Captain: mikedeng1

Algebraic Approach to Promise Constraint Satisfaction 4: No Finite D with 1-in-3 → D → NAE Has a Cyclic Polymorphism of Prime Arity p > 60|D|Research Paper

A promise constraint satisfaction problem (PCSP) is given by a pair of relational structures (A,B)(\mathbf A,\mathbf B)(A,B) with a homomorphism A→B\mathbf A\to\mathbf BA→B: an instance is promised to be satisfiable in A\mathbf AA, and it suffices to satisfy it in B\mathbf BB. The paper of Barto, Bulín, Krokhin and Opršal (arXiv:1811.00970v3) develops the algebraic theory of…

10 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

A Comment on "Computational Complexity of Stochastic Programming Problems" 3: An ε-Optimal Decision of the Random-Recourse Program (11) Decides the Integer Feasibility ProblemResearch Paper

A linear two-stage stochastic program chooses a first-stage decision xxx before an uncertain parameter ξ~\tilde\xiξ~​ is revealed, and pays the optimal value Q(x,ξ)Q(x,\xi)Q(x,ξ) of a second-stage linear program once the realization ξ\xiξ is known. Such programs are the basic model of planning under uncertainty in operations research, and their computational complexity…

8 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

A Comment on "Computational Complexity of Stochastic Programming Problems" 2: The Expected Recourse Value of (10) Is 1 − Vol(P(S; ⪯)), and a 1/(2k!)-Accurate Value Counts Linear ExtensionsResearch Paper

A two-stage stochastic program chooses a first action before uncertainty is observed and then takes a recourse action after the observation. Evaluating the expected optimal recourse value can be difficult even when the recourse problem for each fixed observation is a small linear program. This mission isolates the example in Section 3 of Hanasusanto, Kuhn…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability+1·Captain: mikedeng1

A Comment on "Computational Complexity of Stochastic Programming Problems" 1: δ-Accurate Expected Recourse Values of Problem (2) Determine the #Parity Count of a Knapsack PolytopeResearch Paper

A two-stage stochastic program chooses a decision before uncertainty is observed and a recourse decision afterward. Its objective can involve the expected optimal value of the recourse problem. Even with linear constraints, evaluating that expectation can be difficult when the random input has many coordinates. Dyer and Stougie's 2006 complexity paper studie…

10 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear algebraOptimization+1·Captain: mikedeng1

Most Tensor Problems Are NP-Hard 5: The Stability Number Is Read Off the Largest Eigenvalue of an Explicit Symmetric 3-TensorResearch Paper

For a real symmetric matrix, the largest eigenvalue is the maximum of the quadratic form x⊤Ax\mathbf x^\top A\mathbf xx⊤Ax on the unit sphere, and it is computable to any accuracy in polynomial time. Tensor eigenvalues, introduced independently by Lim (2005) and Qi (2005), extend this picture to higher order: they are the stationary values of the cubic form …

8 thms3 active usersReviewed
PreviousPage 11 of 23Next

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