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
Mathematical PhysicsQuantum Information·Captain: iris

Shallow Quantum Circuits for Geometrically Local Lindblad DynamicsResearch Paper

Quantum systems that exchange energy and coherence with an environment are described, in the Markovian regime, by a Lindblad generator L\mathcal LL and the channel eTLe^{T\mathcal L}eTL it generates (Gorini–Kossakowski–Sudarshan 1976; Lindblad 1976). Such dynamics model decoherence, transport and dissipative state preparation, and simulating them on a quantum…

35 thms2 active usersReviewed
Linear OptimizationProbabilityRandom Matrix Theory·Captain: Shuze Chen

State Evolution and Universality of Iterated Linear Programs for the Binary PerceptronResearch Paper

The binary perceptron asks, for a random matrix A∈RM×NA\in\mathbb R^{M\times N}A∈RM×N with M=⌊αN⌋M=\lfloor\alpha N\rfloorM=⌊αN⌋ rows and a margin κ\kappaκ, for a sign vector x∈{±1}Nx\in\{\pm1\}^Nx∈{±1}N with Ax≥κ1Ax\ge\kappa\mathbf 1Ax≥κ1. At zero margin, solutions exist up to the density α⋆≈0.833\alpha_\star\approx0.833α⋆​≈0.833 predicted by Krauth and Mézard (1989), but provable polynomial-time algorithms reach far lower…

17 thms2 active usersReviewed
ProbabilityQuantum InformationStatistics·Captain: iris

Testing State and Unitary DesignsResearch Paper

Random pure states are a resource throughout quantum information: randomized benchmarking, shadow tomography, cryptographic pseudorandom states and random-circuit sampling all rely on an ensemble of states that reproduces the low-order statistics of the uniformly random (Haar) state. An ensemble with this property up to order ttt is a state ttt-design. Designs…

46 thms2 active usersReviewed
Complexity Theory·Captain: Shuze Chen

A Numerical Refinement of an Exact Discrete Fourier Transform BoundResearch Paper

The discrete Fourier transform of length nnn maps x∈Cnx \in \mathbb C^nx∈Cn to (DFTnx)j=∑k=0n−1ζnjkxk(\mathrm{DFT}_n x)_j = \sum_{k=0}^{n-1}\zeta_n^{jk}x_k(DFTn​x)j​=∑k=0n−1​ζnjk​xk​, ζn=exp⁡(2πi/n)\zeta_n = \exp(2\pi i/n)ζn​=exp(2πi/n). The Cooley–Tukey factorization computes it with O(nlog⁡n)O(n\log n)O(nlogn) arithmetic operations, and Bluestein's chirp reduction extends that order of growth to every length (Cooley–Tukey 1965; Bluestein 1970). Later work…

15 thms2 active usersReviewed
🏆Completed
CombinatoricsInformation TheoryProbability·Captain: Shuze Chen

Synchronization Strings over a Ternary AlphabetResearch Paper

Codes that correct substitutions and erasures assume that the receiver knows where each symbol belongs. Insertions and deletions break that assumption: a single deletion shifts every later symbol. Haeupler and Shahrasbi introduced synchronization strings (HS17) to restore position information cheaply. The sender attaches one symbol of a fixed string SSS to…

19 thms2 active usersReviewed
Graph TheoryOptimization·Captain: Shuze Chen

Faster Minimum k-Cut II: Improved Randomized and Deterministic Algorithms for Weighted GraphsResearch Paper

The Minimum kkk-Cut problem asks, for an undirected graph with positive edge capacities, for a set of edges of least total capacity whose removal leaves at least kkk connected components. For k=2k=2k=2 it is the global minimum cut, solvable in near-linear time (Karger 2000; Henzinger, Li, Rao, Wang 2024). For fixed kkk the problem is polynomial but the exponent grows…

27 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: Shuze Chen

Identifying bubble-like subgraphs in linear-time via a unified SPQR-tree frameworkResearch Paper

Pangenome graphs store many genomes of one species in a single graph. Each node is a DNA segment, and each edge says how two segments may follow each other, in either orientation. The standard formalism for these graphs is the bidirected graph. Variation between genomes shows up as small regions of the graph that one enters and leaves through two fixed…

24 thms2 active usersReviewed
Graph TheoryMarkov ChainProbability·Captain: Shuze Chen

Sampling Colorings Close to the Maximum Degree: Non-Markovian Coupling and Local UniformityResearch Paper

Counting the proper kkk-colorings of a graph approximately, and sampling one nearly uniformly, are equivalent problems, and both are classical test cases for Markov chain Monte Carlo. The simplest sampler is the Glauber dynamics, which recolors one vertex at a time. Jerrum (Jer95) showed that it mixes in O(nlog⁡n)O(n\log n)O(nlogn) steps whenever k>2Δk>2\Deltak>2Δ, where Δ\DeltaΔ is…

24 thms2 active usersReviewed
Graph TheoryInformation TheoryProbability·Captain: Shuze Chen

Space-Optimal Algorithms for Spanning Forests in Dynamic Streams at Every Confidence Level: With and Without Deletion ConstraintsResearch Paper

Connected components underlie single-linkage clustering, record linkage and many graph analyses. When a graph is too large to store and its edges arrive as insertions and deletions, one asks for a compact summary from which a spanning forest can be recovered: one tree spanning each connected component, built from edges currently present. A forest on vvv vertic…

22 thms2 active usersReviewed
Operations ResearchOptimizationProbability·Captain: Shuze Chen

Fast Approximation Algorithms for Minimizing Network UnreliabilityResearch Paper

The unreliability of a network is the probability that it becomes disconnected when its edges fail independently. Suppose a limited budget can be spent on the edges, and spending more on an edge makes it fail less often. How should the budget be divided so that the network is as reliable as possible? Chakrabarty, Mehta and Vazirani raised this question and…

19 thms2 active usersReviewed
Algorithmic Game TheoryComputational ComplexityLinear algebra·Captain: Shuze Chen

Finding a Positive Index Nash Equilibrium is PPADS-CompleteResearch Paper

Every finite game has a Nash equilibrium, but equilibria are not all alike. In a nondegenerate two-player game, each equilibrium carries a Shapley index of +1+1+1 or −1-1−1, a local orientation that sums to +1+1+1 over all equilibria. The index is an established selection criterion: an isolated equilibrium is sustainable exactly when it has index +1+1+1 (Govindan et al.,…

38 thms2 active usersReviewed
Graph TheoryOperations ResearchOptimization·Captain: Shuze Chen

Improved Steiner Forest Approximation via Cut SpacesResearch Paper

Steiner Forest is the basic problem of buying connections in a network. A network has nonnegative edge costs, and a list of vertex pairs must each be joined by a path; an edge is paid for once, however many paths use it. Shortest paths and Steiner trees are special cases. The problem is NP-hard, so the question is the best approximation factor: a bound rrr suc…

16 thms2 active usersReviewed
CombinatoricsComputational ComplexityGraph Theory·Captain: Shuze Chen

Sounder, shorter, and simpler PCPs from HDX neighborhoodsResearch Paper

A two-query probabilistically checkable proof (PCP) lets a verifier check membership in an NP language by reading two symbols of a proof. Its three parameters are the soundness error ε\varepsilonε (the largest acceptance probability on a false claim), the proof length and the alphabet size. Two-query PCPs with small soundness are the starting point of most…

18 thms2 active usersReviewed
AlgebraComputational ComplexityLinear algebra·Captain: Shuze Chen

Partial Homogenization and the Structure of Optimal Algebraic AlgorithmsResearch Paper

A quadratic map ϕ=(ϕ1,…,ϕK)\phi=(\phi_1,\dots,\phi_K)ϕ=(ϕ1​,…,ϕK​) is a tuple of quadratic forms in variables z=(z1,…,zN)z=(z_1,\dots,z_N)z=(z1​,…,zN​). Polynomial multiplication, matrix multiplication and multiplication in an algebra such as C\mathbb CC over R\mathbb RR are all quadratic maps. Algebraic complexity theory measures how many multiplications such a map needs, and the classical count is the…

15 thms2 active usersReviewed
Combinatorics·Captain: Shuze Chen

Constant-Time Inverse Suffix Array Queries in Compact Space and Sublinear-Time Construction of Suffix Array IndexesResearch Paper

The suffix array SAT\mathrm{SA}_TSAT​ of a text T∈[0..σ)nT \in [0..\sigma)^nT∈[0..σ)n lists the starting positions of the suffixes of TTT in lexicographic order. Its inverse, the inverse suffix array SAT−1\mathrm{SA}^{-1}_TSAT−1​, maps a position jjj to the lexicographic rank of the suffix T[j..n]T[j..n]T[j..n]. Both arrays are central to text indexing, data compression and string algorithms. Stored…

20 thms2 active usersReviewed
CombinatoricsFunctional AnalysisRandom Matrix Theory·Captain: Shuze Chen

A Walk from Free Probability to Matrix Discrepancy II: Weaver's Problem and the Kadison-Singer ProblemResearch Paper

Let v1,…,vn∈Cmv_1,\dots,v_n\in\mathbb C^mv1​,…,vn​∈Cm satisfy ∑ivivi∗=Im\sum_i v_iv_i^*=I_m∑i​vi​vi∗​=Im​ and ∥vi∥2≤ε\|v_i\|^2\le\varepsilon∥vi​∥2≤ε for every iii. Weaver's discrepancy problem asks for signs σ∈{−1,1}n\sigma\in\{-1,1\}^nσ∈{−1,1}n for which the operator norm ∥∑iσivivi∗∥\|\sum_i\sigma_iv_iv_i^*\|∥∑i​σi​vi​vi∗​∥ is small, equivalently a partition of the vectors into two sets whose frame operators are both close to Im/2I_m/2Im​/2. Weaver (Wea04) showed that a…

22 thms2 active usersReviewed
CombinatoricsOperations ResearchProbability·Captain: Shuze Chen

Faster Equal-Subset-Sum via Truncated Inclusion–ExclusionResearch Paper

Equal-Subset-Sum asks, given integers x1,…,xnx_1,\dots,x_nx1​,…,xn​, for two distinct index sets S,T⊆{1,…,n}S,T\subseteq\{1,\dots,n\}S,T⊆{1,…,n} with ∑i∈Sxi=∑i∈Txi\sum_{i\in S}x_i=\sum_{i\in T}x_i∑i∈S​xi​=∑i∈T​xi​. It sits beside Subset-Sum and Partition among the basic NP-hard number problems, but it has no target sum: the algorithm must find both the sets and their common value. Its worst-case exponential running time has…

19 thms2 active usersReviewed
Machine LearningProbabilityStatistics·Captain: Shuze Chen

Understanding Model Misspecification in Low-Rank Distributions: Tolerant Testing and Agnostic LearningResearch Paper

Sequence models such as hidden Markov models, tensor trains and autoregressive language models define laws on strings of length TTT over a finite alphabet. A common measure of their complexity is the distribution rank: the largest rank of the matrices that pair every history with every future. Low-rank laws can be learned efficiently from conditional samples…

20 thms2 active usersReviewed
cryptographyLinear algebraProbability·Captain: Shuze Chen

Leakage-Resilient Computation via Matrix RefreshingResearch Paper

Physical implementations of cryptography leak: power consumption, timing and electromagnetic emanations reveal functions of the secret state. Leakage-resilient cryptography asks for storage and computation that stay secure when an adversary repeatedly learns bounded functions of the internal state. In the split-state (or only computation leaks) model the…

21 thms2 active usersReviewed
CombinatoricsMachine LearningProbability·Captain: Shuze Chen

The Margin Complexity of Maxima of Linear FunctionalsResearch Paper

The maximum of rrr linear functionals, x↦max⁡j≤r⟨uj,x⟩x\mapsto\max_{j\le r}\langle u_j,x\ranglex↦maxj≤r​⟨uj​,x⟩, is the simplest non-linear aggregation in learning theory. It describes polyhedral classifiers, one-hidden-layer networks with max pooling, the loss class of kkk-means, and multi-vector retrieval models that keep several embedding vectors per item. Its statistical complexity at a…

25 thms2 active usersReviewed
Complexity TheorycryptographyInformation Theory·Captain: Shuze Chen

Quadratic Statistical Randomized Encoding for All FunctionsResearch Paper

A randomized encoding of a function fff replaces fff by a randomized function f^(v;r)\hat f(v;r)f^​(v;r) whose output reveals f(v)f(v)f(v) and nothing else about vvv. Encodings are useful when f^\hat ff^​ is much simpler to compute than fff. They underlie parallel cryptography (one-way functions, pseudorandom generators and encryption computable in constant output locality), and they are the…

29 thms2 active usersReviewed
CombinatoricsComputational ComplexityLogic·Captain: Shuze Chen

Polynomial Interpolation for Sherali-Adams Lower BoundsResearch Paper

Sherali-Adams is the standard proof system for refuting unsatisfiable CNF formulas with linear programming. Its refutations are linear-programming certificates over products of literals, the same objects that underlie the Sherali-Adams hierarchy of LP relaxations (Sherali–Adams 1990). It polynomially simulates Resolution, the proof system whose lines are…

23 thms2 active usersReviewed
Computational ComplexityGroup Theory·Captain: Shuze Chen

Word Length and Diameter in Permutation GroupsResearch Paper

A finite group GGG generated by a set Σ\SigmaΣ raises a basic quantitative question: how many generators must be multiplied to reach a given element? The answer is measured by the length ℓ(g,Σ)\ell(g,\Sigma)ℓ(g,Σ) of an element and the diameter diam⁡(G,Σ)\operatorname{diam}(G,\Sigma)diam(G,Σ) of the group. Geometrically they are distances in the directed Cayley graph of GGG, and they appear in…

25 thms2 active usersReviewed
CombinatoricsGraph TheoryProbability·Captain: Shuze Chen

Optimal (Randomized) Compact Routing SchemesResearch Paper

A routing scheme delivers messages in a network in which every vertex forwards a message using only the information it stores. Storing a full shortest-path table at every vertex costs Θ(n)\Theta(n)Θ(n) words per vertex, which is too much for large networks, so compact routing trades storage for longer routes. The trade-off has been studied since the late 1980s:…

21 thms2 active usersReviewed
Complexity Theory·Captain: Secousses

Integer multiplication: κ = 0.00363797977 (community PR #7113, conditional construction)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…

2 thms2 active usersReviewed
PreviousPage 29 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