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: iris

Short Non-Interactive Proofs for Time-Space ComputationsResearch Paper

An interactive proof lets a slow prover convince a fast verifier. Merlin–Arthur (MA) protocols remove the interaction: the prover sends one message, and the verifier tosses coins and decides. For circuit satisfiability and related problems, a line of work gives MA protocols that run faster than the known algorithms, starting from Williams, 2016, who gave a …

55 thms5 active usersReviewed
Theoretical Computer Science·Captain: iris

Deterministic Parameterized Inapproximability of the Shortest Vector and Minimum Distance ProblemsResearch Paper

The Shortest Vector Problem (SVP) asks for a shortest nonzero vector of an integer lattice. It is the basic computational problem of lattice-based cryptography and of the geometry of numbers. In the parameterized setting the natural parameter is the distance threshold ddd: exhaustive search over integer vectors with at most dpd^pdp nonzero coordinates solves SVP…

33 thms5 active usersReviewed
Theoretical Computer Science·Captain: iris

Recursive Call-Count Sequences: Structural Realisability, Periodic Branching, and Partial-Observation ReconstructionResearch Paper

A terminating recursive procedure that calls itself twice on smaller inputs has a call-count sequence CnC_nCn​: the number of invocations made on input nnn, root call included. Naive Fibonacci recursion is the standard example, with C0=C1=1C_0=C_1=1C0​=C1​=1 and Cn=1+Cn−1+Cn−2C_n=1+C_{n-1}+C_{n-2}Cn​=1+Cn−1​+Cn−2​, so Cn=2Fn+1−1C_n=2F_{n+1}-1Cn​=2Fn+1​−1. The forward problem, computing costs from a recursive specification, is…

50 thms5 active usersReviewed
AlgebraCombinatoricsTheoretical Computer Science·Captain: iris

Conservative Modular Counting at Every Odd PrimeResearch Paper

A constraint satisfaction problem over a fixed finite relational template H=(D;R1,…,Rs)H=(D;R_1,\dots,R_s)H=(D;R1​,…,Rs​) asks about assignments of values in DDD to variables subject to constraints Ri(v1,…,vk)R_i(v_1,\dots,v_k)Ri​(v1​,…,vk​). Counting the satisfying assignments exactly is the subject of the Dyer–Richerby dichotomy (DR): for every template it is either in FP or #P-complete, and the tractable…

31 thms5 active usersReviewed
Theoretical Computer Science·Captain: iris

d-DNNF is Not Polynomially Closed Under NegationResearch Paper

Deterministic decomposable negation normal form circuits (d-DNNFs) are a central target language of knowledge compilation: a d-DNNF supports exact model counting, weighted model counting and sampling in time polynomial in its size (Darwiche–Marquis 2002). Compiling a CNF into a d-DNNF and then counting is a standard approach to #SAT, and d-DNNFs are used…

52 thms5 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: iris

Improved NP-Hardness of Approximation for Max-3-Cut and for Max-k-Cut with Small kResearch Paper

In Max-kkk-Cut one is given a graph with non-negative edge weights and must colour its vertices with kkk colours so as to maximise the total weight of the edges whose endpoints receive different colours. For k=2k = 2k=2 this is Max-Cut. For k≥3k \ge 3k≥3 the best polynomial-time algorithms round the semidefinite relaxation of Frieze and Jerrum (Algorithmica 1997); for k=3k = 3k=3…

54 thms5 active usersReviewed
Operations ResearchProbability·Captain: iris

Impatience Makes Matching NP-HardResearch Paper

Ride-hailing platforms, online labour marketplaces, organ-allocation systems and quantum switches all match two sides of a market whose agents do not wait forever. The standard abstraction is a bipartite queueing system: agents of finitely many types arrive over time, the platform decides which compatible pairs to match, and an unmatched agent leaves when…

32 thms5 active usersReviewed
Graph TheoryOperations ResearchTheoretical Computer Science·Captain: iris

Approximation and Hardness for the Data Validation ProblemResearch Paper

Precedence-constrained scheduling takes a partial order on tasks as input, yet in practice the order is rarely known with full confidence. In product design, assembly, project scheduling and construction, the relation between two tasks is often not documented, and an expert must be consulted to determine it. For automotive assembly, probing direct…

36 thms5 active usersReviewed
Convex OptimizationTheoretical Computer Science·Captain: iris

Near-Quadratic Lower Bounds for Convex Optimization with Binary First-Order QueriesResearch Paper

Classical oracle complexity counts how many exact first-order answers — a value f(y)f(y)f(y) and a subgradient g∈∂f(y)g\in\partial f(y)g∈∂f(y) — a method needs to minimize a convex function. With exact real answers, O(dlog⁡(MR/ε))O(d\log(MR/\varepsilon))O(dlog(MR/ε)) queries suffice in dimension ddd, attained by the center of gravity method and by modern cutting-plane methods. A computer, however, reads…

62 thms5 active usersReviewed
CombinatoricsOperations Research·Captain: iris

Additive Ω(log⁡∗OPT)\Omega(\log^* OPT)Ω(log∗OPT) Gap for Bin Packing with Three Items per BinResearch Paper

In bin packing, items with sizes in (0,1](0,1](0,1] must be partitioned into bins of total size at most one, using as few bins as possible; OPT(I)\mathrm{OPT}(I)OPT(I) is that minimum. The problem is strongly NP-hard even in the 3-partition regime, where every size lies in (1/4,1/2)(1/4,1/2)(1/4,1/2) and a bin holds at most three items, so research has concentrated on additive guarantees …

28 thms5 active usersReviewed
Algorithmic Game TheoryOperations Research·Captain: iris

Efficient Fair Division with Minimal Sharing: For Fixed nnn, Sharing-Minimal Fair fPO Allocations Are Computable in O(3n(n−1)Dv/2mn(n−1)/2+2)O(3^{n(n-1)D_v/2} m^{n(n-1)/2+2})O(3n(n−1)Dv​/2mn(n−1)/2+2) Operations and NP-Hard at Polynomial DegeneracyResearch Paper

Fair division of divisible resources is usually solved by convex optimization or market equilibrium, and the resulting allocations typically split many objects among several agents. In practice splitting is costly: a house, a car or a work shift is shared only by co-ownership or time-sharing. Sandomirskiy and Segal-Halevi (arXiv:1908.01669v3, Operations…

22 thms5 active usersReviewed
Graph Theory·Captain: Shuze Chen

Identification, Location-Domination and Metric Dimension on Interval and Permutation Graphs. II. Algorithms and Complexity: NP-completeness at diameter twoResearch Paper

A network can be monitored by selecting a set of vertices and recording which selected vertices are near a possible event. A useful selection must provide coverage, so that an event is observed, and identification, so that different event locations give different observations. The number of selected vertices measures the resources required for these two…

27 thms5 active usersReviewed
Combinatorics·Captain: Abhishek Anand

Block Sensitivity vs. Sensitivity: Reach 2.15Open Problem

Prove a block-sensitivity versus sensitivity separation exponent of 2.15.

24 thms5 active usersReviewed
Linear OptimizationOperations Research·Captain: mikedeng1

On Linear Characterizations of Combinatorial Optimization Problems I: A Small Facial Description in NP Puts the Decision Problem in co-NPResearch Paper

Polyhedral combinatorics attacks a combinatorial optimization problem by replacing its finite set of feasible solutions with the convex hull of that set and describing the hull by linear inequalities. Once such a description is known, the problem becomes a linear program, and linear programming duality supplies optimality certificates. For matchings,…

12 thms5 active usersReviewed
cryptographyQuantum InformationTheoretical Computer Science·Captain: Shuze Chen

Information Loss Is All You Need: TC^0 Pseudorandomness from Worst-Case LatticesResearch Paper

Learning with errors (LWE) is the standard source of post-quantum hardness: given many noisy inner products As+e mod qA s + e \bmod qAs+emodq of a secret sss, distinguish them from uniform. Regev showed in 2005 that this is as hard, for quantum algorithms, as worst-case approximate lattice problems (Reg05). Removing the random error makes the samples deterministic: learning…

52 thms4 active usersReviewed
Quantum Information·Captain: mikedeng1

A classical oracle separation between QMA and QMA(2)Research Paper

QMA is the quantum analogue of NP: a polynomial-time quantum verifier receives a quantum proof (a witness) from an all-powerful prover. QMA(2) is the variant in which the verifier receives two quantum proofs that are promised to be unentangled, i.e. the joint witness is a product state ∣ψ1⟩⊗∣ψ2⟩|\psi_1\rangle\otimes|\psi_2\rangle∣ψ1​⟩⊗∣ψ2​⟩ (KMY03). Whether this promise adds…

32 thms4 active usersReviewed
Information TheoryNumber Theory·Captain: mikedeng1

NP-Hardness of Bounded Distance Decoding for Reed–Solomon CodesResearch Paper

A Reed–Solomon code stores a message as the values of a low-degree polynomial at distinct points of a finite field. Decoding asks whether a received word is close to some codeword. The complexity of this question depends on how many errors are allowed, the field and the evaluation set. Unique decoding up to half the minimum distance and Guruswami–Sudan list…

23 thms4 active usersReviewed
Graph TheoryOptimization·Captain: mikedeng1

A Simple Subquadratic Cut Query Protocol for Directed ReachabilityResearch Paper

A directed reachability question asks whether a sequence of directed edges leads from a specified source vertex to a specified target. Ordinary graph search answers it when outgoing neighbours can be inspected. A different question arises when the graph is hidden and an oracle reports only how many edges leave a chosen vertex set. This outgoing-cut oracle re…

29 thms4 active usersReviewed
OptimizationTheoretical Computer Science·Captain: Shuze Chen

Optimal Approximation Algorithms For Satisfiable Ordering CSPsResearch Paper

An ordering problem asks for a single ranking that satisfies many local requirements. A requirement might say that one variable precedes another, or that one lies between two others. Even when a perfect ranking is promised to exist, an efficient algorithm may have difficulty finding it. Approximation asks what fraction of the requirements can always be…

29 thms4 active usersReviewed
Graph TheoryOptimizationProbability·Captain: Shuze Chen

An O(n0.1537)O(n^{0.1537})O(n0.1537)-Coloring Algorithm for 333-Colorable GraphsResearch Paper

A graph is 3-colorable if its vertices can be labelled with three colors so that adjacent vertices get different labels. Deciding 3-colorability is NP-complete, and finding a 3-coloring of a graph known to be 3-colorable is no easier. The natural algorithmic question is therefore approximate: given a 3-colorable graph on nnn vertices, how few colors suffice…

28 thms4 active usersReviewed
cryptographyTheoretical Computer Science·Captain: Shuze Chen

PPAD Hardness from SISResearch Paper

PPAD is the class of total search problems whose solutions are guaranteed by a parity argument on a directed graph of in- and out-degree at most one: if a source exists, another endpoint must exist. Computing a Nash equilibrium of a finite game is complete for it (Daskalakis–Goldberg–Papadimitriou 2009; Chen–Deng–Teng 2009). Since every instance has a…

24 thms4 active usersReviewed
cryptographyProbabilityTheoretical Computer Science·Captain: iris

Fast Provable Algorithms for Approximate CVP and Exact SVP on Random qqq-ary LatticesResearch Paper

Lattice-based cryptography rests on two problems over a uniformly random matrix H∈(Z/qZ)m×nH\in(\mathbb Z/q\mathbb Z)^{m\times n}H∈(Z/qZ)m×n: SIS, find a short nonzero xxx with Hx≡0(modq)Hx\equiv0\pmod qHx≡0(modq), and ISIS, find a short xxx with Hx≡t(modq)Hx\equiv t\pmod qHx≡t(modq). Both are questions about the q-ary lattice of HHH. The best provable algorithms for the closest vector problem on general lattices take time …

29 thms4 active usersReviewed
CombinatoricsLinear algebraTheoretical Computer Science·Captain: Shuze Chen

Counting Exact-One Hitting Sets in Subexponential TimeResearch Paper

Exact-One Hitting Set asks for a set of elements that meets every member of a given family exactly once. It is one of Karp's 21 NP-complete problems (Karp 1972, Problem 15), and in the language of satisfiability it is monotone exact satisfiability (XSAT): every set imposes the constraint "exactly one of these variables is true". Positive one-in-three…

17 thms4 active usersReviewed
cryptographyQuantum Information·Captain: iris

No linear stretching of single-copy quantum pseudorandomnessResearch Paper

A pseudorandom state generator (PRS) maps a classical key k∈{0,1}nk\in\{0,1\}^nk∈{0,1}n to an efficiently prepared quantum state ∣ϕk⟩|\phi_k\rangle∣ϕk​⟩ that no efficient algorithm can tell apart from a Haar-random state, given polynomially many copies (JLS18). PRS belong to Microcrypt: primitives that suffice for quantum cryptographic protocols but are potentially weaker than…

31 thms4 active usersReviewed
Probability·Captain: Shuze Chen

Optimal Black-Box Hardness Amplification for Integer SumsResearch Paper

A function can be difficult to predict on a small fraction of inputs while still allowing a predictor to be correct most of the time. Hardness amplification asks for a transformation that turns this limited unpredictability into a task on which small circuits rarely succeed. Integer summation is a particularly direct transformation: draw several independent…

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