Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Theoretical Computer Science

1,446 missions · 603 completed

The mathematical foundations of computation: which problems can be solved, by what algorithms, and at what cost in time, space, or communication. Distinguished by its emphasis on rigor and unconditional lower bounds, it spans computational complexity, algorithm design, automata and computability, cryptography, and the analysis of Boolean functions.

Missions

Open843Completed603All1446
Algorithmic Game TheoryComputational Complexity·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
Linear algebraMachine LearningProbability·Captain: Shuze Chen

Nearly Optimal Strong Coresets for ℓp\ell_pℓp​ Subspace ApproximationResearch Paper

Low-rank approximation under robust losses is a basic primitive of data analysis. Given nnn points in Rd\mathbb R^dRd, the ℓp subspace approximation problem asks for a subspace of dimension at most kkk minimizing the sum of ppp-th powers of the Euclidean distances of the points to it. For p=2p=2p=2 this is principal component analysis; for 1≤p<21\le p<21≤p<2 it is less sensitive to…

24 thms3 active usersReviewed
CombinatoricsGraph TheoryLinear algebra+1·Captain: Shuze Chen

Breaking the Quadratic Time Barrier for Flow Sparsifiers via Schur Complement LocalizationResearch Paper

Many multicommodity flow and cut problems only concern a small set of terminals inside a large network. Vertex sparsification replaces the network by a graph on the terminals alone that preserves, up to a factor called the quality, how well every pattern of terminal traffic can be routed. Such a graph is a preprocessing step for approximation algorithms…

19 thms3 active usersReviewed
Convex OptimizationGraph TheoryProbability·Captain: Shuze Chen

Polynomial-Time Differentially Private Synthetic Graph Release with Nearly-Linear Additive ErrorResearch Paper

Releasing a weighted graph under edge-level differential privacy is a basic task in private data analysis: the vertex set is public, the weight of every pair of vertices is private, and a released synthetic graph should preserve the answers to a rich family of queries. Cut queries are the canonical family, because many graph optimization problems (Max-Cut,…

23 thms3 active usersReviewed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: Shuze Chen

Efficient Equilibrium Computation in Colonel Blotto GamesResearch Paper

The Colonel Blotto game (Borel, 1921) is the basic model of competitive resource allocation: two players divide fixed budgets among several contests, and each contest goes to the larger allocation. It models military and security planning, elections and R&D races. In the continuous version, allocations are arbitrary nonnegative reals, so each player has a…

29 thms3 active usersReviewed
Combinatorics·Captain: Shuze Chen

Pattern Matching with Edits in O~(n+k3⋅n/m)\tilde{O}(n+k^3 \cdot n/m)O~(n+k3⋅n/m) TimeResearch Paper

Finding the positions where a pattern occurs in a text with a few typos is one of the basic tasks on strings, used for example in read mapping in computational biology. With the edit distance ed(X,Y)\mathrm{ed}(X,Y)ed(X,Y) (the minimum number of single-character insertions, deletions and substitutions turning XXX into YYY) the task is pattern matching with edits: given a…

25 thms3 active usersReviewed
Complexity TheoryMachine LearningNumerical Analysis·Captain: Shuze Chen

The Cancellation-Free Cost of Hessian Diagonals: Exact Counts, Formulas and InterfacesResearch Paper

Automatic differentiation computes the gradient of a function given as a program at a constant factor over one evaluation [Baur and Strassen 1983; Griewank and Walther 2008]. Second-order quantities are harder. The Hessian diagonal (∂2f/∂xi2)i(\partial^2 f/\partial x_i^2)_i(∂2f/∂xi2​)i​ and its sum, the Laplacian, appear in physics-informed neural networks, variational Monte Carlo…

15 thms3 active usersReviewed
Complexity TheorycryptographyQuantum Information·Captain: iris

Natural proofs for quantum state preparation lower boundsResearch Paper

Proving that a specific quantum state needs large circuits to prepare is one of the central open tasks of quantum complexity theory. In classical circuit complexity, Razborov and Rudich showed that a broad class of lower-bound techniques, natural proofs, cannot separate circuit classes that can compute pseudorandom functions (Razborov–Rudich 1997). Li and…

39 thms3 active usersReviewed
Complexity Theory·Captain: rohanarun

Integer multiplication: κ=0.00363005817\kappa=0.00363005817κ=0.00363005817 (community #7000/#7001)Open Problem

Multiplying two binary integers is a basic task in computational complexity. The relevant resource here is the number of individual steps made by a machine whose tapes can only be accessed through moving heads. Harvey and van der Hoeven established an O(nlog⁡n)O(n\log n)O(nlogn) bound in this model. The OpenAI manuscript proposes a positive saving in the exponent of the…

3 thms3 active usersReviewed
cryptographyDiscrete GeometryProbability·Captain: iris

Gaussian Difference Dynamics: Breaking the 2n/22^{n/2}2n/2 Barrier for the Shortest Vector Problem and Discrete Gaussian SamplingResearch Paper

A lattice L=BZnL = B\mathbb Z^nL=BZn is the set of integer combinations of the columns of a nonsingular matrix BBB. The shortest vector problem (SVP) asks for a nonzero vector of LLL of minimal Euclidean length λ1(L)\lambda_1(L)λ1​(L). Exact SVP is the computational core of lattice basis reduction, and its running time calibrates the security estimates of lattice-based…

68 thms3 active usersReviewed
Complexity TheorycryptographyProbability·Captain: iris

Faster Provable Algorithm For Random Modular Subset SumResearch Paper

Subset sum asks, given integers a1,…,ana_1,\dots,a_na1​,…,an​ and a target ttt, for a set of indices whose coefficients sum to ttt. Its random modular version, with coefficients uniform in Z/QZ\mathbb Z/Q\mathbb ZZ/QZ and a planted binary solution, is the standard benchmark for generic attacks on knapsack-type cryptosystems and for the representation technique of Howgrave-Graham and…

27 thms3 active usersReviewed
Functional AnalysisOptimizationProbability·Captain: mikedeng1

Primal/Dual Method for the Grothendieck ConstantResearch Paper

The real Grothendieck constant KGK_GKG​ measures how much a semidefinite relaxation can overestimate a bilinear ±1\pm1±1 optimization problem. It appears in Banach-space theory, where it is the best constant in Grothendieck's inequality Pis12; in quantum information, where it bounds the violation of correlation Bell inequalities AGT06; and in approximation…

24 thms3 active usersReviewed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Optimal Contention Resolution from SamplesResearch Paper

A contention resolution scheme receives a random collection of available elements and selects a feasible subset. With a capacity of kkk, feasibility means selecting at most kkk elements. The input can respect capacity on average while exceeding it on particular realizations. A useful selection rule must resolve these conflicts while preserving a guarantee for…

40 thms3 active usersReviewed
AnalysisNumerical AnalysisQuantum Information·Captain: mikedeng1

Time-space tradeoffs for Hamiltonian simulationResearch Paper

A Hamiltonian simulation approximates the evolution of a quantum system from simpler evolutions generated by its constituent terms. Product formulas accomplish this by composing those term evolutions. Their resource cost depends on the desired accuracy, the formula's order, and the number of repetitions. A coherent circuit can also select among several such…

31 thms3 active usersReviewed
Complexity TheoryGroup TheoryQuantum Information+1·Captain: mikedeng1

An exponential separation between entanglement-assisted and unassisted one-way quantum communicationResearch Paper

Communication complexity measures how much information separated parties must exchange to compute a function of their inputs. Alice knows one input, Bob knows the other, and local computation is free. Shared entanglement is a quantum state established before either input is known. It cannot transmit information by itself, but it can change the communication…

37 thms3 active usersReviewed
cryptography·Captain: mikedeng1

Trapdoors Beyond Inversion: Recoverable Information in Public-Key CryptographyResearch Paper

Public-key encryption distinguishes between what anyone can compute and what a secret key can recover. A public key lets anyone encrypt a message, while a secret key recovers that message from the ciphertext. A related primitive, a trapdoor function, asks the secret key to recover an entire input to a public evaluation. That recovery interface can be…

28 thms3 active usersReviewed
Quantum Information·Captain: mikedeng1

Query-Optimal and Gate-Efficient Time-Dependent Hamiltonian SimulationResearch Paper

A Hamiltonian specifies how a quantum system evolves. In a controlled experiment, its coefficients may change during the experiment, so a simulator must reproduce the evolution generated by a function of time rather than by one fixed matrix. The cost of accessing that function and the cost of implementing the remaining circuit are distinct resources. A…

28 thms3 active usersReviewed
CombinatoricsComplexity TheoryOptimization·Captain: Shuze Chen

Tight Algorithms for Conservative Finite-Valued CSPs Parameterized by TreewidthResearch Paper

For an NP-hard problem, "polynomial or not" says nothing about how hard the hard cases are. On graphs of bounded treewidth the finer question is the base of the exponent: many problems are solvable in time ctw⋅nO(1)c^{\mathrm{tw}}\cdot n^{O(1)}ctw⋅nO(1) by dynamic programming over a tree decomposition of width tw\mathrm{tw}tw, and a line of work started by Lokshtanov, Marx and…

26 thms3 active usersReviewed
Convex OptimizationMarkov ChainQuantum Information·Captain: iris

Improved Upper and Lower Bounds for Quantum Convex-Body Volume EstimationResearch Paper

Computing the volume of a convex body is a basic problem of algorithmic convex geometry. In the membership-oracle model every deterministic algorithm with polynomially many queries can only approximate the volume within a factor exponential in ddd (Bárány–Füredi 1987), while randomized algorithms achieve any relative accuracy with polynomially many queries…

37 thms3 active usersReviewed
Computational ComplexityQuantum Information·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
Machine LearningMathematical PhysicsQuantum Information·Captain: iris

Learning Arbitrary Lindbladians from Time EvolutionResearch Paper

A quantum device that is not perfectly isolated evolves under a Markovian open-system dynamics etLe^{t\mathcal L}etL, whose generator L\mathcal LL (a Lindbladian) combines a coherent Hamiltonian part with dissipation. Characterizing L\mathcal LL from experiments is a basic task in the calibration and benchmarking of quantum hardware: the coefficients of L\mathcal LL are…

60 thms3 active usersReviewed
Computational GeometryMarkov ChainQuantum Information·Captain: iris

Improved quantum volume estimation with transducers and amortized quantum walksResearch Paper

Estimating the volume of a convex body is a central problem of computational geometry and of the theory of randomized algorithms. Deterministic algorithms with membership access cannot approximate the volume within a polynomial factor using polynomially many queries (Elekes 1986; Bárány and Füredi 1987), while randomized algorithms based on Markov chain…

47 thms3 active usersReviewed
CombinatoricsInformation Theory·Captain: Shuze Chen

Dynamic LZ77: No Space for ImprovementResearch Paper

Lempel–Ziv 77 (LZ77) is the parsing behind most dictionary compressors and the reference measure of repetitiveness in compressed string algorithms. Its size zzz can be exponentially smaller than the length nnn of a highly repetitive text, which is why compressed indexes aim for space proportional to zzz rather than nnn.

22 thms3 active usersReviewed
Machine LearningMathematical PhysicsProbability+1·Captain: iris

Efficiently Learning SYK HamiltoniansResearch Paper

Hamiltonian learning from Gibbs states asks for the couplings of an unknown Hamiltonian HHH given independent copies of its thermal state e−βH/tr e−βHe^{-\beta H}/\mathrm{tr}\,e^{-\beta H}e−βH/tre−βH. It is the quantum analogue of learning an undirected graphical model, and it underlies the calibration and verification of quantum simulators. Existing polynomial-time guarantees rely…

32 thms3 active usersReviewed
Graph TheoryProbability·Captain: Shuze Chen

Dynamic (Δ+1)(\Delta+1)(Δ+1)-Coloring with Polylogarithmic Worst-Case Update TimeResearch Paper

A graph of maximum degree Δ\DeltaΔ always has a proper coloring with Δ+1\Delta+1Δ+1 colors, and the static greedy algorithm finds one in linear time. In the fully dynamic setting the graph undergoes edge insertions and deletions, its maximum degree stays at most Δ\DeltaΔ, and a proper (Δ+1)(\Delta+1)(Δ+1)-coloring must be kept after every update. The recourse of an update is…

19 thms3 active usersReviewed
PreviousPage 8 of 34Next

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