Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Computational Complexity

136 missions · 10 completed

Missions

Open126Completed10All136
Mathematical Logic·Captain: mikedeng1

Parallelism and Adaptivity in Student-Teacher WitnessingResearch Paper

A search procedure can receive useful information even when its first proposed answer is wrong. A Student–Teacher game makes this interaction explicit: a computationally limited student proposes answers, while an unrestricted teacher supplies certificates explaining failures. Researchers in computational complexity and bounded arithmetic use these games to…

58 thms4 active usersReviewed
Probability·Captain: mikedeng1

Online Algorithms Cannot Find Isolated Perceptron SolutionsResearch Paper

The binary perceptron asks for a vector of binary weights satisfying random linear inequalities. It is a model of learning with discrete weights and a test case for average-case computational complexity. Its geometry raises a specific algorithmic question: if most solutions have no nearby solutions, which solutions can an algorithm actually find? The pinned…

27 thms4 active usersReviewed
Linear OptimizationOperations Research·Captain: mikedeng1

0/1 integer programming over polytopes of Chvátal rank one is as hard as lattice problemsResearch Paper

An integer program asks for integer coordinates satisfying linear inequalities. Cutting planes strengthen the inequalities without removing integer solutions. A Chvátal–Gomory cut takes a valid inequality with integer coefficients and rounds its right-hand side down. The Chvátal closure is the set remaining after all such cuts are imposed once. A polyhedron…

43 thms4 active usersReviewed
Quantum Information·Captain: iris

Quantum channel tomography: optimal bounds in the near-boundary regimeResearch Paper

Quantum channel tomography (also called quantum process tomography) asks for a full classical description of an unknown quantum channel, given black-box access to it. It is the standard way to certify gates and devices, and its query complexity is the basic sample-complexity question for learning quantum dynamics.

30 thms4 active usersReviewed
Mathematical PhysicsQuantum Information·Captain: iris

The Complexity of Single-Interaction HamiltoniansResearch Paper

The local Hamiltonian problem asks whether the ground energy of a sum of few-qubit terms lies below a threshold aaa or above a threshold b>ab>ab>a. It is the quantum analogue of constraint satisfaction, and its QMA-completeness (Kitaev, Shen and Vyalyi; for two-local terms Kempe, Kitaev and Regev) is the starting point of Hamiltonian complexity theory. In the…

63 thms4 active usersReviewed
Quantum Information·Captain: iris

Optimal compression with quantum retrievalResearch Paper

A sparse string x∈{0,1}mx\in\{0,1\}^mx∈{0,1}m with at most nnn ones can be stored in log⁡(mn)≈nlog⁡(m/n)\log\binom{m}{n}\approx n\log(m/n)log(nm​)≈nlog(m/n) bits, far fewer than mmm. The catch is retrieval: a data structure that answers "what is xix_ixi​?" by reading only a few bits of the stored string usually needs much more space. In classical computing this is the static set membership problem in the bit-probe…

16 thms4 active usersReviewed
Quantum Information·Captain: iris

All Unitaries Have Constant Depth Quantum CircuitsResearch Paper

The number of one- and two-qubit gates needed to implement a general nnn-qubit unitary is 2Θ(n)2^{\Theta(n)}2Θ(n): standard synthesis gives the upper bound and counting gives the lower bound. That count leaves open how far the gates can be parallelized when ancilla qubits are free. Classically, unbounded fan-in and fan-out compress any Boolean function to three layers.…

40 thms4 active usersReviewed
Quantum Information·Captain: iris

Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified RandomnessResearch Paper

Random circuit sampling experiments are at present the leading demonstrations of quantum computational advantage (Arute et al., 2019). The samples of such an experiment are scored by the linear cross-entropy benchmark, which rewards an output in proportion to the probability that the ideal circuit assigns to it. A device that knew the ideal distribution…

31 thms4 active usersReviewed
Quantum Error CorrectionQuantum Information·Captain: iris

The Heisenberg Representation of Quantum Computers: Clifford circuits with Pauli measurements and classical control are perfectly simulated in randomized classical polynomial time (Knill's theorem)Research Paper

A general nnn-qubit quantum computation is described by 2n2^n2n complex amplitudes, and following them on a classical computer costs exponential time and space. Daniel Gottesman's 1998 paper The Heisenberg Representation of Quantum Computers shows that a large and practically important class of quantum networks escapes this cost. Instead of the state, one follows…

22 thms4 active usersReviewed
Algorithmic Game TheoryEconomicsOperations Research·Captain: iris

The Complexity of Pacing for Second-Price Auctions: Finding an Approximate Pacing Equilibrium Is PPAD-HardResearch Paper

Online advertising platforms sell billions of impressions through auctions, and most advertisers face a budget for a whole campaign rather than for a single auction. Ad platforms handle this with budget pacing: each advertiser's bids are scaled down by a multiplier so that spending tracks the budget. When every advertiser paces at once, the multipliers…

26 thms4 active usersReviewed
Quantum Information·Captain: iris

Quantum Circuits with Mixed States: a circuit calling probabilistic subroutines is computed exactly by Lemma-4 dilations, their inverses, CNOT and Toffoli with n + l·O(k+r+m) gates (FQP^FQP = FQP)Research Paper

Quantum algorithms are usually written as unitary circuits on pure states, yet many natural computational steps are not unitary: measuring, discarding a register, or calling a probabilistic subroutine whose output is random even on a classical input. Aharonov, Kitaev and Nisan (arXiv:quant-ph/9806029v1, 1998) set up a circuit model in which every gate is a…

31 thms4 active usersReviewed
CombinatoricsComplexity Theory·Captain: mikedeng1

Kurodoko is NP-Complete: Deciding the Solvability of Kurodoko Puzzles Is NP-CompleteResearch Paper

Kurodoko ("where are the black squares?") is a pen-and-paper logic puzzle published by Nikoli. Its rules are short: colour some squares of a grid black so that the numbered squares stay white, no two black squares touch, the white squares stay connected, and every number counts the white squares it can see along its row and column. The computational…

15 thms4 active usersReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: iris

Genetic Algorithms with Optimization Guided OperatorsResearch Paper

Systems such as FunSearch and AlphaEvolve search for programs and constructions by repeatedly asking a language model for new candidates, for local revisions of a stored candidate, and for combinations of several stored candidates. A. Brandenberger, I. Doron-Arad and E. Mossel (Genetic Algorithms with Optimization Guided Operators, STOC 2027 submission; an…

26 thms3 active usersReviewed
cryptography·Captain: mikedeng1

Succinct Interactive Commitments and Arguments for NP from Exponentially Hard Injective One-Way FunctionsResearch Paper

Succinct arguments let a prover convince a verifier that a statement such as "this nondeterministic computation accepts" is true while communicating far less than the witness. They underlie delegation of computation and verifiable outsourcing. Kilian's protocol (Kil92) builds them from a probabilistically checkable proof (PCP) and a vector commitment, and…

24 thms3 active usersReviewed
AlgebraNumber Theory·Captain: mikedeng1

Integral 2 × 3 × 3 Tensor Isomorphism is in BQPResearch Paper

Tensor isomorphism asks whether two multi-way arrays become equal after independent invertible changes of basis on each of their factors. Over fields it underlies the classification of entanglement: two pure states of a qubit and two qutrits are SLOCC-equivalent exactly when complex local maps relate their 2×3×32\times3\times32×3×3 coefficient tensors, and matrix…

29 thms3 active usersReviewed
cryptographyQuantum Information·Captain: mikedeng1

A Hierarchy of Proofs of QuantumnessResearch Paper

A proof of quantumness is an interactive protocol in which a classical verifier, exchanging only classical messages, accepts an efficient quantum prover with noticeably higher probability than any efficient classical prover (BCM+18). Such protocols certify that a device can do some quantum computation. They say nothing about how much quantum computation the…

22 thms3 active usersReviewed
Mathematical PhysicsQuantum InformationTheoretical Computer Science·Captain: iris

Polynomial-Time Classical and Quantum Simulation of Quantum Impurity ModelsResearch Paper

Quantum impurity models describe a small, strongly interacting system (an atom, a quantum dot, a defect) coupled to a large non-interacting fermionic reservoir. They are the original setting of the Kondo problem and of Wilson's numerical renormalization group (Wilson 1975), and they are the subproblem that embedding methods such as dynamical mean-field…

32 thms3 active usersReviewed
Quantum Information·Captain: mikedeng1

Hamiltonian locality testing and certification do not achieve the Heisenberg limitResearch Paper

A Hamiltonian describes the interactions governing a quantum system's time evolution. Learning every interaction can require much more information than deciding whether the interactions have a particular structure. Locality testing asks whether every interaction involves at most a specified number of qubits, or whether the Hamiltonian is quantitatively far…

25 thms3 active usersReviewed
cryptographyTheoretical Computer Science·Captain: mikedeng1

Hardness of Unique Shortest Vectors and Bounded Distance DecodingResearch Paper

Short lattice vectors and nearby lattice points are the basic computational objects of lattice algorithms and lattice-based cryptography [MG02]. Two promises are expected to make them easier to find. In the unique shortest vector problem (uSVP), every lattice vector off the line of a shortest vector is longer by a fixed factor Γ\GammaΓ. In bounded distance…

32 thms3 active usersReviewed
Computational GeometryOperations ResearchTheoretical Computer Science·Captain: Shuze Chen

Near-Optimal Makespan and Parameterized Hardness for Multi-Robot Motion PlanningResearch Paper

Moving several robots through a shared workspace without collisions is a basic problem of robotics and computational geometry. Deciding whether one arrangement of robots can be transformed into another is PSPACE-hard when the number of robots is part of the input, so attention turns to a small number kkk of robots. Known algorithms for kkk square robots in a…

25 thms3 active usersReviewed
Quantum Information·Captain: iris

Depth-Optimal Quantum CompilationResearch Paper

A quantum algorithm is usually written with arbitrary single-qubit rotations, while fault-tolerant hardware and the circuit classes of complexity theory offer only a fixed, finite gate set. Every rotation therefore has to be compiled: replaced by a circuit over the fixed set that approximates it to some precision ε\varepsilonε. The Solovay–Kitaev theorem and…

42 thms3 active usersReviewed
Algorithmic Game TheoryTheoretical Computer Science·Captain: Shuze Chen

Settling the Complexity of Hylland–Zeckhauser EquilibriaResearch Paper

Assigning dormitory rooms to students or shifts to workers is a one-sided matching market: nnn agents must share nnn indivisible goods, each agent receives exactly one good, and money cannot change hands. Randomization restores fairness when several agents want the same good: a random assignment gives each agent a probability of receiving each good, and by the…

29 thms3 active usersReviewed
Quantum InformationTheoretical Computer Science·Captain: iris

unitaryQIP = unitaryPSPACEResearch Paper

Quantum complexity theory has long classified decision problems, and more recently it has classified state synthesis (preparing a target quantum state) and unitary synthesis (applying a target unitary to an unknown input state). For decision problems, interactive proofs capture polynomial space: QIP=PSPACE\mathsf{QIP}=\mathsf{PSPACE}QIP=PSPACE (Jain, Ji, Upadhyay, Watrous 2011)…

53 thms3 active usersReviewed
Quantum Information·Captain: iris

On Random Purifications of Isometries and ChannelsResearch Paper

Lower bounds for quantum algorithms that query an unknown unitary or channel are much harder to prove than lower bounds for algorithms that query a classical function, because the oracle's answers are quantum states. A recurring difficulty is that an isometry V:H([N])→H([M])V:\mathcal H([N])\to\mathcal H([M])V:H([N])→H([M]), which models a state-preparation procedure or the purification…

62 thms3 active usersReviewed
Quantum Information·Captain: iris

Computational Work Extraction: The Complexity of CatalystsResearch Paper

A catalyst in quantum computation is an auxiliary register that an algorithm may use but must, in the end, return. Catalysts are studied in quantum thermodynamics, where they model resources that enable a transformation without being consumed, and in space-bounded computation, where a full but "borrowed" memory can be more useful than a small clean one.…

34 thms3 active usersReviewed
PreviousPage 2 of 6Next

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