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
Captain: mikedeng1

Multi-Access Randomness Saves Space, Even for Halting AlgorithmsResearch Paper

Space complexity asks how much writable memory a computation needs. Randomness introduces another resource: a machine can consult a tape of independent fair bits without paying for those bits as work space. Whether it may return to an earlier random bit, and whether it must halt on every possible tape, affect the resulting model. These distinctions matter…

21 thms2 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

k-Coloring is Faster than Computing the Chromatic NumberResearch Paper

Graph coloring is one of the basic NP-complete problems, and its exact exponential-time complexity has been studied for decades. Computing the chromatic number χ(G)\chi(G)χ(G) of an nnn-vertex graph takes O∗(2n)O^*(2^n)O∗(2n) time by the inclusion–exclusion algorithm of Björklund, Husfeldt and Koivisto (SIAM J. Comput. 2009), where O∗O^*O∗ hides factors polynomial in the input size.…

17 thms2 active usersReviewed
Linear algebra·Captain: mikedeng1

Explicit tensors beyond the linear flattening barrierResearch Paper

A three-dimensional array describes a bilinear computation: fixing two input vectors and contracting against two coordinates produces an output vector. A decomposition of the array into simple products gives a way to perform this computation with a specified number of products of linear forms. Tensor rank measures the shortest such decomposition. Border rank…

20 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

An EPTAS for Max-Cut on Interval GraphsResearch Paper

In Max-Cut one is given a graph G=(V,E)G=(V,E)G=(V,E) and asks for a set S⊆VS\subseteq VS⊆V maximizing cutG(S)\mathrm{cut}_G(S)cutG​(S), the number of edges with exactly one endpoint in SSS; mc(G)\mathrm{mc}(G)mc(G) denotes the maximum. On general graphs the Goemans–Williamson algorithm achieves the ratio αGW≈0.878\alpha_{GW}\approx0.878αGW​≈0.878, and beating it is NP-hard under the Unique Games Conjecture; …

31 thms2 active usersReviewed
Quantum Information·Captain: mikedeng1

Quantum Advantage with Sign-Free Proofs: An Oracle Separation between StoqMA and MAResearch Paper

A proof system combines a claim, a witness, and a verifier that decides whether to accept the witness. Classical randomized verification allows the verifier to toss private coins while receiving an ordinary bit string. Quantum verification can also receive a quantum state and perform coherent operations. Determining which of these resources increases…

32 thms2 active usersReviewed
Linear algebra·Captain: mikedeng1

Worst-Case to Average-Case Reductions for Basic Linear AlgebraResearch Paper

Matrix multiplication, inversion, solving linear systems, rank and the determinant have closely related worst-case running times: fast multiplication gives fast algorithms for the others through classical reductions. Average-case behaviour is a different matter, because the standard reductions pass through highly structured matrices, on which an algorithm…

19 thms2 active usersReviewed
Theoretical Computer Science·Captain: mikedeng1

Lifting to Unary Sherali–Adams over ParitiesResearch Paper

A propositional proof system certifies that a collection of Boolean constraints has no satisfying assignment. Its resources depend on the language in which certificates are written. For Sherali–Adams, a certificate uses a polynomial identity together with nonnegative combinations of conjunctions of literals. Bounds on polynomial degree alone do not control…

27 thms2 active usersReviewed
ProbabilityStatistics·Captain: mikedeng1

The Polynomial-Time Low-Degree Conjecture is FalseResearch Paper

The low-degree method studies whether a statistic given by a polynomial of bounded degree can distinguish a structured random observation from an unstructured one. In statistical inference and average-case complexity, failure of such tests is often used as evidence that efficient algorithms will also fail. The polynomial-time conjecture considered here adds…

18 thms2 active usersReviewed
Captain: mikedeng1

Derandomizing (Fragments of) Arthur–Merlin with Range AvoidanceResearch Paper

An Arthur–Merlin protocol lets a computationally limited verifier inspect a claim with help from a prover. The verifier first sends random bits publicly; the prover then supplies a response. Perfect completeness means that every random challenge on a YES input admits an accepting response. Soundness limits how often any response can succeed on a NO input.…

20 thms2 active usersReviewed
Algebra·Captain: mikedeng1

An Algebraic Polynomial Evaluation Datastructure for Fields of Large CharacteristicResearch Paper

A polynomial evaluation datastructure stores a precomputed encoding of a multivariate polynomial so that the polynomial can be evaluated at any point by reading only a few cells of the encoding. Such structures were introduced for univariate polynomials in the cell-probe literature (Miltersen 1995) and were developed for multivariate polynomials as a tool…

18 thms2 active usersReviewed
Algorithmic Game TheoryTheoretical Computer Science·Captain: mikedeng1

Tarski Fixed Points in Quasi-FPT QueriesResearch Paper

Tarski's fixed point theorem says that every monotone map on a complete lattice has a fixed point. On the finite grid [n]k={1,…,n}k[n]^k=\{1,\dots,n\}^k[n]k={1,…,n}k with the coordinatewise order, finding such a fixed point captures several problems whose complexity is open: pure Nash equilibria of supermodular games, and the reductions of parity games, mean-payoff games, Condon's…

27 thms2 active usersReviewed
Quantum Information·Captain: mikedeng1

Quantum interaction can superactivate cheating under parallel repetitionResearch Paper

Parallel repetition is the standard way to amplify soundness: if two non-communicating provers cannot win a game with certainty, one expects them to be even less able to win many independent copies played at once. For classical games this is Raz's parallel repetition theorem. Bhattacharyya, Mančinska and Zhao show that this intuition fails badly for quantum…

20 thms2 active usersReviewed
Machine Learning·Captain: mikedeng1

Polynomial-Time Mistake-Bounded Language GenerationResearch Paper

Language generation in the limit (Kleinberg and Mullainathan, 2024) asks a learner who sees a stream of words of an unknown language LLL from a known family to output, from some point on, words of LLL it has not yet seen. Unlike Gold's identification in the limit, generation is possible for every countable family. Kleinberg, Peale and Reingold (arXiv:2605.10809,…

9 thms2 active usersReviewed
Captain: mikedeng1

Witness Isolation with Inverse-Polylogarithmic Success Implies NP in P/polyResearch Paper

A witness is a binary string certifying that an instance has a positive answer. For a Boolean circuit, a witness is an assignment on which the circuit outputs one. Many reductions in complexity theory become useful when exactly one witness survives. Witness isolation therefore asks for a procedure that restricts a satisfiable instance while retaining…

21 thms2 active usersReviewed
Probability·Captain: mikedeng1

Random (log⁡n\log{n}logn)-CNF Formulas Are Hard for Depth-222 Frege with Modular GatesResearch Paper

A propositional contradiction can have very different proof lengths in different systems. Polynomial calculus measures the algebraic complexity of a contradiction by the largest polynomial degree needed to derive the constant one from its equations. For random formulas, the relevant question is whether many constraints make a contradiction easy to certify…

26 thms2 active usersReviewed
Graph Theory·Captain: mikedeng1

Testability of General Graphs with Weak Query OraclesResearch Paper

A graph property tester examines a small part of a graph and distinguishes graphs having a property from graphs requiring many changes to acquire it. Researchers studying sublinear graph algorithms need to know which properties admit a query bound independent of the number of vertices. That question depends on what a query reveals. An adjacency query can…

23 thms2 active usersReviewed
Algorithmic Game Theory·Captain: mikedeng1

Hardness Amplification of Approximate Nash Equilibrium with Constantly Many PlayersResearch Paper

Computing a Nash equilibrium asks for a probability distribution over each player's actions such that no player benefits from changing its own distribution. An approximate equilibrium permits a specified additive improvement. The approximation parameter matters: when payoffs lie between zero and one, allowing improvement one makes every profile acceptable.…

24 thms2 active usersReviewed
CombinatoricsOperations Research·Captain: mikedeng1

Closing All-Exp Gaps in Local Search for the Traveling Salesman Problem and Maximum Constraint AssignmentResearch Paper

Local search is the oldest heuristic for the Traveling Salesman Problem (TSP): start from a tour and keep replacing it by a better neighboring tour until no neighbor is better. For the 2-opt neighborhood, studied by Croes in 1958, a move replaces two edges of the tour by two other edges. The method is used in practice, and the number of its iterations is…

29 thms2 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

A Near-Linear Element-Kernel for d-Hitting SetResearch Paper

ddd-Hitting Set is a central covering problem of parameterized complexity: many deletion problems whose obstructions have bounded size (Cluster Vertex Deletion, Feedback Vertex Set in Tournaments, Split Vertex Deletion, ddd-Path Vertex Cover) are instances of it. A kernel shrinks an instance in polynomial time to an equivalent one whose size depends on the…

38 thms2 active usersReviewed
Quantum Information·Captain: iris

Quantum State Search with Classical Interactive AdviceResearch Paper

Unstructured search over 2n2^n2n items needs Θ(2n/2)\Theta(2^{n/2})Θ(2n/2) quantum queries (Grover; Bennett, Bernstein, Brassard and Vazirani), and a prover who knows the marked item removes that cost by sending its nnn-bit address. The question behind this mission is whether classical communication helps in the same way when the hidden object is a quantum state.

39 thms2 active usersReviewed
Theoretical Computer Science·Captain: iris

Non-signaling PCPs as Algebraic Proofs, and Total Coefficients Lower Bounds for Sherali–AdamsResearch Paper

Succinct non-interactive arguments (SNARGs) for NP from standard cryptographic assumptions are a central open problem in cryptography. Devadas, Hopkins, Kalai, Kothari, Lombardi and Mathialagan (DHK+26) showed that non-signaling PCPs for NP whose completeness has short Extended Frege proofs yield SNARGs for NP from LWE. Chen and Jin (STOC 2027 submission)…

35 thms2 active usersReviewed
Theoretical Computer Science·Captain: iris

Towards a Doubly Efficient IP = PSPACEResearch Paper

An interactive proof lets a verifier with limited resources check a claim "x∈Lx \in Lx∈L" by exchanging messages with a prover. The theorem IP=PSPACE\mathrm{IP} = \mathrm{PSPACE}IP=PSPACE of Lund, Fortnow, Karloff and Nisan and of Shamir (1992) shows that every time-TTT, space-SSS computation can be checked by a poly(S,n)\mathrm{poly}(S, n)poly(S,n)-time verifier. In those protocols the honest prover…

24 thms2 active usersReviewed
Quantum Information·Captain: iris

Square-root queries can helpResearch Paper

A quantum algorithm is usually modelled as a circuit: a sequence of discrete gates. A natural test of that modelling choice is whether an operation that is easy to apply can also be applied "halfway". Question 4 on Aaronson's list of annoying questions in quantum computing [Aar06] asks: if a unitary UUU can be applied in polynomial time, can some square root…

30 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: iris

Between CPA and CCA: Security Hierarchies for Restricted DecryptionResearch Paper

Deployed systems rarely hand an attacker a full decryption oracle, yet they rarely hand it nothing. A server may reveal whether a ciphertext decrypted correctly, whether a padding check passed, whether a decrypted record equals a candidate value, or the contents of a few fields of the record. Attacks that exploit such responses, from padding and format…

42 thms2 active usersReviewed
Quantum Information·Captain: iris

XOR Lifting for One-Query Hybrid Algorithms and the Complexity of AND–OR TreesResearch Paper

Many quantum query algorithms keep their state coherent across many queries, and their speedups come from interference that accumulates across those queries. Near-term devices lose coherence quickly, which raises the question of which quantum speedups survive when the state must be measured completely after every few queries. Query complexity is a setting…

63 thms2 active usersReviewed
PreviousPage 11 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