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
CombinatoricsGraph Theory·Captain: iris

Forgetting Alternation and BlossomsResearch Paper

A maximum cardinality matching of a general graph can be found by repeatedly augmenting the current matching along a maximal set of vertex-disjoint shortest augmenting paths. Hopcroft and Karp showed that O(n)O(\sqrt n)O(n​) such phases suffice, so the whole difficulty is to compute one maximal set of disjoint shortest augmenting paths in nearly linear time. In…

29 thms3 active usersReviewed
Algorithmic Game TheoryComplexity Theory·Captain: iris

The Complexity of Correlated Equilibria Beyond Normal-Form GamesResearch Paper

A correlated equilibrium (CE) is a distribution over strategy profiles from which no player gains by applying any swap deviation, a map that replaces each recommended strategy by another one. In normal-form games (finitely many pure strategies) CE are the solutions of a linear program, and in games of polynomial type exact CE can be computed in polynomial…

48 thms3 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: iris

Linear Max Load and Additive StructureResearch Paper

A hash function compresses a large universe into a small number of bins, and its quality is judged by how evenly it spreads a set of inputs. For a set SSS of nnn items hashed into nnn bins by a fully random function, the expected size of the fullest bin, the expected max load, is (1+o(1))ln⁡n/ln⁡ln⁡n(1+o(1))\ln n/\ln\ln n(1+o(1))lnn/lnlnn. Fully random functions are expensive in time, space and…

28 thms3 active usersReviewed
Information TheoryQuantum Information·Captain: iris

Structural Lower Bounds with Persistent Quantum MemoryResearch Paper

How many copies of an unknown quantum state does a learner need to estimate many expectation values Tr⁡(ρGj)\operatorname{Tr}(\rho G_j)Tr(ρGj​) at once? The answer depends sharply on the learner's quantum memory. A learner that measures each copy and keeps only classical records can need exponentially more copies than one that stores many copies and measures them jointly (C…

27 thms3 active usersReviewed
Operations ResearchOptimization·Captain: iris

Online Metric Problems via Randomly Perturbed Work FunctionsResearch Paper

In metric allocation a unit of mass is spread over the nnn points of a metric space and must be redistributed online as convex cost functions arrive at the points, paying for transport and for service. The problem was introduced by Bansal and Coester [BC22] (ESA 2022) as a common generalization of fractional kkk-server and of metrical task systems (MTS), and it…

25 thms3 active usersReviewed
CombinatoricsInformation TheoryQuantum Information·Captain: iris

Binary code rate bounds via classical-quantum channelsResearch Paper

A binary error-correcting code of length nnn is a set C⊆{0,1}n\mathcal C\subseteq\{0,1\}^nC⊆{0,1}n of codewords. Its minimum distance dmin⁡(C)d_{\min}(\mathcal C)dmin​(C), the least Hamming distance between two distinct codewords, guarantees correction of every pattern of fewer than dmin⁡/2d_{\min}/2dmin​/2 bit flips, wherever they occur. How many codewords such a guarantee allows is measured by the asymp…

25 thms3 active usersReviewed
Machine LearningProbabilityStatistics·Captain: iris

The Conditional Geometry of Statistical VerificationResearch Paper

A learner that hands over a classifier can be asked to justify it. In statistical verification an untrusted prover proposes a hypothesis and a verifier, using its own private labeled samples, either accepts a hypothesis whose risk is within ε\varepsilonε of the best in the class or rejects. The question is how many private samples verification needs compared…

46 thms3 active usersReviewed
Graph TheoryOptimization·Captain: iris

Faster Semi-Streaming and Dynamic Approximate Maximum Weight Matchings in General Graphs: A Unified FrameworkResearch Paper

A semi-streaming algorithm reads the edges of an nnn-vertex graph as a stream, possibly several times, and keeps only O(n polylog n)O(n\,\mathrm{polylog}\,n)O(npolylogn) bits of memory. Matching is the central problem of this model: the output itself can have Θ(n)\Theta(n)Θ(n) edges, so the model allows just enough memory to write it down, and the question is how many passes over the stream a …

24 thms3 active usersReviewed
CombinatoricsOperations ResearchOptimization·Captain: iris

Constant-factor approximation of MinCostCSP with a conservative majority polymorphismResearch Paper

In the minimum cost constraint satisfaction problem MinCostCSP(A)\mathrm{MinCostCSP}(\mathbf A)MinCostCSP(A) every variable carries a unary cost function and the task is to find a satisfying assignment of minimum total cost. Fixing the template A\mathbf AA gives a family of problems that contains minimum-cost homomorphism problems for graphs and digraphs and many deletion and…

40 thms3 active usersReviewed
CombinatoricsComplexity Theory·Captain: iris

Settling Nondeterministic Communication Complexity of Graph ConnectivityResearch Paper

In the two-party communication model, Alice and Bob each hold part of an input and exchange bits to compute a function of the whole input; the cost is the number of bits exchanged in the worst case. Graph properties are a standard test bed for the model, and connectivity is the most studied of them: Alice and Bob hold disjoint edge sets EAE_AEA​, EBE_BEB​ of an NNN-vert…

30 thms3 active usersReviewed
Complexity TheoryGraph TheoryQuantum Information·Captain: iris

Algorithmic Wave-Particle Duality: Pathfinding in Welded Trees is HardResearch Paper

The welded trees problem is the standard example of an exponential quantum speedup for a problem defined by a graph given only through a neighbor oracle. Childs, Cleve, Deotto, Farhi, Gutmann and Spielman showed in 2003 (doi:10.1145/780542.780552) that a continuous-time quantum walk started at the entrance of a randomly welded pair of binary trees reaches…

34 thms3 active usersReviewed
CombinatoricsProbabilityRandom Matrix Theory·Captain: iris

Stable and Online Algorithms for Random Matrix DiscrepancyResearch Paper

Matrix discrepancy asks for signs σ∈{−1,1}N\sigma\in\{-1,1\}^Nσ∈{−1,1}N that make a signed sum of matrices small in operator norm. The worst-case question is the Matrix Spencer conjecture. This mission is about the average case: the matrices are independent random symmetric Gaussian matrices, and the question is at what density a polynomial-time algorithm finds good signs (Kı…

24 thms3 active usersReviewed
Complexity Theorycryptography·Captain: iris

Does Witness Indistinguishability Require Cryptography?Research Paper

Witness indistinguishability (WI), introduced by Feige and Shamir, is a privacy guarantee for interactive proofs: no efficient verifier can tell which of two valid witnesses the prover holds. It is weaker than zero knowledge, but it is preserved under parallel composition and has low-round realizations, and it is a building block of zero-knowledge…

43 thms3 active usersReviewed
CombinatoricsComplexity Theory·Captain: iris

The Complexity of Choosing Parity ProjectionsResearch Paper

In a cube attack on a stream cipher (Dinur and Shamir, 2009), an attacker sums a Boolean function over all assignments to a small set of inputs. A cube whose sum, the superpoly, is a simple function of the key yields an equation in the key bits, and enough such cubes recover the key of a reduced-round cipher. Dutta, Rajasree and Sarkar (EasyChair Preprint…

49 thms3 active usersReviewed
CombinatoricsMathematical PhysicsProbability·Captain: iris

On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten–StigumResearch Paper

The antiferromagnetic Ising model is a standard test case for the complexity of approximate counting. On graphs of maximum degree ddd the picture is settled: polynomial-time approximate counting, rapid mixing of Glauber dynamics, strong spatial mixing and the absence of zeros of the partition function all hold up to the uniqueness threshold …

35 thms3 active usersReviewed
CombinatoricsComplexity TheoryLinear algebra·Captain: iris

An Explicit 4n−O(log(n)) Size Lower Bound against General Boolean CircuitsResearch Paper

Almost every Boolean function on nnn variables needs circuits of size Ω(2n/n)\Omega(2^n/n)Ω(2n/n) (Shannon, 1949). For functions that can be computed explicitly, for instance in NP\mathbf{NP}NP or even in P\mathbf{P}P, the best known lower bounds against general circuits are only linear in nnn, with a small constant. Better bounds are a step in Sipser's programme for separating …

69 thms3 active usersReviewed
Algorithmic Game TheoryGraph Theory·Captain: iris

The Price of Stability in Undirected Network Design: Lower Bounds and Structural GuaranteesResearch Paper

In a network design game with equal cost sharing, players connect their terminals through a shared network and split the cost of every edge equally among its users. An optimal network can be unstable: one player may lower her own share by rerouting while the total cost rises. The price of stability (PoS) measures how much a stable outcome must cost: the…

28 thms3 active usersReviewed
Linear algebraNumerical Analysis·Captain: iris

Solving Linear Systems in O~(mnlog⁡κϵ)\tilde{O}(m n \log \frac{\kappa}{\epsilon})O~(mnlogϵκ​) Bit OperationsResearch Paper

Solving a square linear system Ax=bAx = bAx=b to a prescribed relative residual is a basic task of numerical computation, and its cost in bit operations is the honest measure of that task: it charges for the length of every number the algorithm touches. For a sparse matrix with mmm nonzero entries, conjugate-gradient type methods use O(mn)O(mn)O(mn) arithmetic operations in…

28 thms3 active usersReviewed
Complexity TheoryProbability·Captain: iris

Differentially Private Verification of Distribution PropertiesResearch Paper

A distribution property verifier has sample access to an unknown distribution DDD and wants to decide whether DDD has a property PPP (uniformity, independence, a bounded support size) or is far from every distribution with that property. Testing alone can need many samples; an untrusted prover who knows DDD can sometimes cut the cost, provided the verifier can…

27 thms3 active usersReviewed
Complexity TheoryRepresentation Theory·Captain: iris

The asymptotic spectrum of tensors is connectedResearch Paper

The matrix multiplication exponent ω\omegaω is the infimum of the real numbers τ\tauτ such that two n×nn\times nn×n matrices can be multiplied with O(nτ)O(n^\tau)O(nτ) arithmetic operations. Strassen placed this problem in a theory of tensors in which computational reductions are encoded by a preorder, and in which a compact space of monotone functions, the asymptotic spectrum,…

43 thms3 active usersReviewed
CombinatoricsMachine Learning·Captain: iris

What is Learnable in Valiant's Theory of the Learnable?Research Paper

Valiant's 1984 paper A Theory of the Learnable is usually credited with the PAC model, but the model it formulates is different. A learner in Valiant's model sees only positive examples, may ask membership queries about any point of the domain, and must output a hypothesis with no false positives that misses at most an ε\varepsilonε fraction of the positive…

35 thms3 active usersReviewed
CombinatoricsComplexity TheoryGraph Theory·Captain: iris

NP-hardness for Bipartite Colorings up to the Maximum DegreeResearch Paper

Counting the proper qqq-colorings of a graph of maximum degree Δ\DeltaΔ is the central test case of approximate counting. Since Jerrum (1995) it has been conjectured that an FPRAS exists for general graphs whenever q≥Δ+1q\ge\Delta+1q≥Δ+1, and the rapid-mixing bounds for Glauber dynamics have moved from q>2Δq>2\Deltaq>2Δ toward that threshold. On the hardness side, Galanis,…

31 thms3 active usersReviewed
Markov ChainProbability·Captain: iris

Code Swendsen-Wang DynamicsResearch Paper

Sampling from Gibbs distributions near and below a phase transition is the hard regime for Markov chain methods, because local dynamics take exponentially long to cross energy barriers. For the Ising model the remedy is the global update of Swendsen and Wang. Quantum code Hamiltonians are the minimal models of topological phases, and Hangleiter, Ju and…

31 thms3 active usersReviewed
Algorithmic Game TheoryGraph Theory·Captain: iris

The Caccetta-Häggkvist Conjecture and Percentile Distortion: An Equivalence via Asymmetric Maximal LotteriesResearch Paper

Metric distortion measures how much a voting rule loses by seeing only ordinal preferences. Voters and candidates sit in an unknown metric space; each voter ranks candidates by distance, and the rule sees only the rankings. The distortion of a rule is the worst case, over elections and over metrics consistent with the rankings, of the ratio between the cost…

45 thms3 active usersReviewed
Complexity TheoryGraph TheoryQuantum Information·Captain: iris

Quantum Advantage in Local Certification of Graph PropertiesResearch Paper

In local certification, an untrusted prover (Merlin) assigns a certificate to every node of a network. The nodes then exchange messages with their neighbours for a fixed number of rounds and each node decides to accept or reject; the network accepts when all nodes accept. The resource measured is the certificate size per node. This model underlies…

34 thms3 active usersReviewed
PreviousPage 18 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