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
Complexity TheoryOptimizationProbability·Captain: Shuze Chen

Sharp Power Loss Thresholds for Vector Min UncutResearch Paper

Vector Min Uncut asks for unit vectors, one per vertex of a weighted graph, such that the endpoints of every heavy edge are nearly antipodal. At rank one the vectors are signs ±1\pm1±1 and the problem is classical Min Uncut, the complement of Max-Cut, for which Agarwal, Charikar, Makarychev and Makarychev gave an O(log⁡∣V∣)O(\sqrt{\log |V|})O(log∣V∣​)-approximation (STOC 2005).…

22 thms3 active usersReviewed
Operations ResearchOptimization·Captain: Shuze Chen

A Unified Framework for Parameterized Approximation of Clustering Objectives via Distance MappingsResearch Paper

Center-based clustering asks for kkk centers in a metric space that serve a finite set of data points well. The classical objectives (k-median, k-means, k-center, min-sum of radii) and their variants with fault tolerance, capacities, penalties or outliers have mostly been studied one at a time, each with its own algorithm. In structured metrics (bounded…

16 thms3 active usersReviewed
CombinatoricsMarkov ChainProbability·Captain: Shuze Chen

Fast Almost-Uniform Sampling of Random kkk-SAT SolutionsResearch Paper

A random kkk-SAT formula with nnn variables and m=⌊αn⌋m=\lfloor\alpha n\rfloorm=⌊αn⌋ clauses is the standard model of a typical constraint satisfaction instance. Below the satisfiability threshold, which is near 2kln⁡22^k\ln 22kln2 clauses per variable, such a formula has exponentially many solutions. Sampling one of them almost uniformly is a basic algorithmic task: it gives…

27 thms3 active usersReviewed
Algorithmic Game TheoryOptimizationProbability·Captain: Shuze Chen

Correlated Forest Rounding for Unweighted Nash Social WelfareResearch Paper

In the Nash social welfare (NSW) problem, mmm indivisible items are divided among nnn agents with valuations vi:2M→R≥0v_i:2^M\to\mathbb R_{\ge0}vi​:2M→R≥0​, and the goal is to maximize the geometric mean (∏ivi(Si))1/n\big(\prod_i v_i(S_i)\big)^{1/n}(∏i​vi​(Si​))1/n of the agents' values. The objective sits between utilitarian welfare and max-min fairness and is invariant under rescaling any single valuation,…

16 thms3 active usersReviewed
Algebraic TopologyCombinatoricsComplexity Theory+1·Captain: Shuze Chen

Polynomial Swap Coboundary Expansion with Applications to LTCs and PCPsResearch Paper

Agreement tests, locally testable codes and probabilistically checkable proofs share one step: local functions that agree on most overlaps must be stitched into one global function. On high-dimensional expanders this step is controlled by swap coboundary expansion. That notion asks the faces complex of a simplicial complex to be a coboundary expander with…

29 thms3 active usersReviewed
🏆Completed
CombinatoricsMachine LearningProbability·Captain: Shuze Chen

Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper LearningResearch Paper

In binary classification, every PAC learnable class can be learned by a proper learner, one that always outputs a member of the class: empirical risk minimization does it, and learnability is characterized by the VC dimension. With many labels the picture changes. Daniely and Shalev-Shwartz introduced the DS dimension and conjectured that it characterizes…

11 thms3 active usersReviewed
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
🏆Completed
CombinatoricsGraph TheoryLinear algebra·Captain: Shuze Chen

A Sharp Rigidity Law for Effective ResistanceResearch Paper

Effective resistances summarize a weighted graph as an electrical network: the resistance RuvR_{uv}Ruv​ between two vertices is the voltage needed to send one unit of current from uuu to vvv. They govern commute times and are the sampling probabilities of spectral sparsification (Spielman–Srivastava 2011), and they form a metric on the vertices.

10 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
PreviousPage 14 of 58Next

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