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
🏆Completed
Machine LearningOperations ResearchProbability+1·Captain: mikedeng1

Foundations of Machine Learning XIV: Finite Markov Decision Processes and Bellman's EquationsTextbook

Reinforcement learning formalizes a scenario supervised learning cannot: an agent that actively interacts with an environment, choosing actions that change both the state it observes next and the reward it receives, rather than passively receiving an i.i.d. labeled sample. Every practical treatment of this scenario — from classical dynamic programming to…

13 thms3 active usersReviewed
🏆Completed
Mathematical PhysicsQuantum Information·Captain: LG

Undecidability of the Spectral GapResearch Paper

The spectral gap of a quantum many-body Hamiltonian is the difference between the energy of its ground state and the energy of its first excited state, in the limit of infinitely many particles. Whether a given microscopic interaction produces a gapped or a gapless system decides much of the macroscopic physics: gapped systems have exponentially decaying…

22 thms3 active usersReviewed
🏆Completed
Mechanism Design·Captain: Shuze Chen

Algorithmic Game Theory IV: VCG and the Limits of TruthfulnessTextbook

Mission III of this series ends at an impossibility: without money, incentive compatibility over three or more alternatives means dictatorship. This mission formalizes the classical escape route — quasilinear utilities and payments — and the exact price of it. Vickrey (1961) discovered that a second-price auction makes truth-telling dominant; Clarke (1971)…

6 thms3 active usersReviewed
🏆Completed
Captain: marwahaha

Asymmetric Hashing Square Bound: omega < 2.3747Research Paper

AI generated, I think it's correct

131 thms3 active usersReviewed
🏆Completed
Captain: marwahaha

Schönhage–Pan–Winograd Bound: omega < 2.522Research Paper

The matrix-multiplication exponent measures the asymptotic arithmetic cost of multiplying square matrices. An upper bound ω<c\omega<cω<c means that, over the field under consideration, N×NN\times NN×N matrices can be multiplied using O(Nc+ε)O(N^{c+\varepsilon})O(Nc+ε) arithmetic operations for every ε>0\varepsilon>0ε>0. Improvements to ω\omegaω are a central benchmark in algebraic…

27 thms3 active usersReviewed
🏆Completed
Computational Geometry·Captain: wurtle

Generalization of Hinging PlanesResearch Paper

A continuous piecewise linear (CPWL) function is one assembled from finitely many flat pieces glued along flat seams. Every ReLU network computes such a function, and every such function is computed by some ReLU network. Questions about how deep a network must be are therefore questions about the internal structure of CPWL functions.

3 thms3 active users
🏆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
🏆Completed
AlgebraNumerical AnalysisProbability·Captain: Shuze Chen

Approximate Syzygies of Smoothed Polynomials and ApplicationsResearch Paper

Many algorithms for tensor decomposition, polynomial system solving and learning mixtures reduce to linear algebra on Macaulay matrices: given polynomials b1,…,bmb_1,\dots,b_mb1​,…,bm​, the matrix of the map (h1,…,hm)↦∑ibihi(h_1,\dots,h_m)\mapsto\sum_i b_ih_i(h1​,…,hm​)↦∑i​bi​hi​ at a fixed output degree. Whether such an algorithm is robust to noise depends on how far this map is from losing rank, beyond the…

12 thms2 active usersReviewed
🏆Completed
Machine Learning·Captain: mikedeng1

Dense Language Generation Made Simple: Deterministic, Randomized, and Multi-Order AlgorithmsResearch Paper

Language generation in the limit asks whether a generator can eventually produce only new members of an unknown language after observing positive examples. This is a mathematical model of generation from examples; it imposes no computational resource bound. Eventual validity alone allows outputs to occupy a sparse part of the target. On the positive…

18 thms2 active usersReviewed
🏆Completed
AlgebraComplexity TheoryLinear algebra·Captain: Shuze Chen

New lower bounds on tensor rank of (n,2,m)(n,2,m)(n,2,m) matrix multiplication with GPT-6 AstraResearch Paper

Every fast matrix multiplication algorithm starts from an identity that computes a fixed-shape product with few multiplications. Strassen's 1969 algorithm (Str69) multiplies two 2×22\times 22×2 matrices with 7 instead of 8 multiplications, and applying such an identity recursively turns RRR multiplications for a k×lk\times lk×l by l×ml\times ml×m product into an …

12 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

A Tight Ω~(m)\widetilde\Omega (\sqrt m)Ω(m​) Information-theoretic Lower Bound for Randomized Online Set CoverResearch Paper

Online set cover asks how many sets must be purchased when the elements requiring coverage arrive one at a time. It is relevant to the analysis of algorithms that make irrevocable covering decisions before learning which demands will occur. Knowing the available sets does not reveal the future demands. The mathematical question is how much this missing…

17 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: iris

Set-defined graph classes: χ\chiχ-boundedness meets tropical algebraResearch Paper

A hereditary class of graphs is χ-bounded if the chromatic number of its members is bounded by a function of their clique number, and polynomially χ-bounded if that function can be a polynomial. Deciding which natural classes are χ-bounded, and whether χ-boundedness forces polynomial χ-boundedness, is a central theme of structural graph theory…

31 thms2 active usersReviewed
🏆Completed
cryptographyProbability·Captain: iris

Correlated Group Actions: Founding Cryptography on S4 and SnResearch Paper

Oblivious transfer (OT) is a two-party primitive in which a sender holds two bits m0,m1m_0, m_1m0​,m1​, a receiver holds a selection bit sss, and the receiver learns msm_sms​ while the sender learns nothing about sss and the receiver learns nothing about the other bit m1−sm_{1-s}m1−s​. Kilian showed in 1988 that OT is complete for secure two-party computation: any function can be…

15 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Exponential Separation of Sign-Rank and Margin ComplexityResearch Paper

A Boolean matrix records the answers to a two-input decision problem: a row is one party's input, a column is the other's, and the entry is their required answer. Its sign-rank measures the smallest real linear representation that preserves every answer by a strict sign test. It connects matrix geometry with communication complexity and with representing…

9 thms2 active usersReviewed
🏆Completed
CombinatoricsMarkov Chain·Captain: mikedeng1

Exact Agreement Expansion up to the Top via Non-polarityResearch Paper

An agreement test checks whether a collection of local functions comes from one global function. Each set KKK of a weighted family carries a local function FK:K→ΣF_K:K\to\SigmaFK​:K→Σ. The test samples a smaller set HHH, then two sets K,K′⊇HK,K'\supseteq HK,K′⊇H, and accepts when FKF_KFK​ and FK′F_{K'}FK′​ agree on HHH. Soundness says that a test that rarely rejects forces most FKF_KFK​ to be…

12 thms2 active usersReviewed
🏆Completed
Convex OptimizationFunctional Analysis·Captain: mikedeng1

A Linear Lower Bound for Convex Body Chasing in Every NormResearch Paper

Convex body chasing is a basic online problem in metric geometry and online algorithms: an algorithm must stay inside a sequence of convex constraints revealed one at a time while moving as little as possible. It was introduced by Friedman and Linial (FL93, Discrete Comput. Geom. 1993) and is the geometric core of online convex optimization with switching…

16 thms2 active usersReviewed
🏆Completed
Algebraic Topology·Captain: mikedeng1

Self-stabilising approximate clock synchronisation requires linear timeResearch Paper

Distributed systems use logical clock ticks to coordinate rounds of communication. A self-stabilising protocol must recover even when transient faults leave every process in an arbitrary local state. A second requirement is tolerance of permanent failures while recovery proceeds. These requirements occur together: an event that corrupts stored state can…

19 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Tight weighted paging with delay via mirror descentResearch Paper

A cache can avoid repeated downloads by retaining useful pages. When requests may wait, it can also batch several requests for the same page into one download. These two choices interact: waiting may save a fetch, but holding a page while waiting occupies space that another page needs. Weighted paging with delay asks for an online rule that balances these…

19 thms2 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Tight Bounds for Randomized Generalized k-Server on Uniform MetricsResearch Paper

The generalized kkk-server problem was introduced by Koutsoupias and Taylor (KT04) as a model of kkk heterogeneous servers, each moving in its own metric space, that must jointly answer requests naming one location per server. It contains the classical kkk-server problem, weighted kkk-server, and paging with heterogeneous cache slots as special cases, and it is a…

12 thms2 active usersReviewed
🏆Completed
Formal VerificationMathematical Logic·Captain: mikedeng1

Tree Equivalence of Higher-Order Recursion Schemes Is UndecidableResearch Paper

A higher-order recursion scheme (HORS) is a finite, simply typed recursive program whose terminal symbols act as tree constructors. Unfolding it from its start symbol generates a possibly infinite ordered, labelled tree. Schemes are a standard model of higher-order functional programs: Ong proved that monadic second-order properties of the generated tree…

30 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Three Standard Deviations Suffice While One Does NotResearch Paper

A collection of measurements can depend on the same binary decisions. Each decision contributes a real coefficient to each measurement, and choosing its sign changes all measurements at once. Discrepancy theory asks how small all resulting totals can be made simultaneously. In the matrix formulation, the columns describe decisions, the rows describe…

15 thms2 active usersReviewed
🏆Completed
Machine Learning·Captain: mikedeng1

Private Uniform Language GenerationResearch Paper

A generator observes examples from an unknown collection of valid objects and must produce new valid objects. Uniform language generation asks for one finite sample bound that works for every target in a specified family. The objects can be finite strings, but their syntax plays no role: the model keeps only a countable universe and the subsets that count…

23 thms2 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: iris

A Hitting Set Lemma for HDX & ApplicationsResearch Paper

The hitting set lemma for expander graphs bounds the probability that a random walk stays inside a fixed set of vertices: for a graph whose normalized second singular value is at most λ\lambdaλ and a set SSS of density μ\muμ, a (d−1)(d-1)(d−1)-step walk from a random vertex stays in SSS with probability at most μ(μ+λ)d−1\mu(\mu+\lambda)^{d-1}μ(μ+λ)d−1. Results of this type underlie…

29 thms2 active usersReviewed
🏆Completed
Complexity TheoryMathematical Logic·Captain: iris

Hard Instances for Strong Semantic Proof Systems: CNFs for Depth-Four PC and Deep Instances for AC0[2]\mathsf{AC}^0[2]AC0[2]-FregeResearch Paper

AC0[2]-Frege is the propositional proof system whose lines are constant-depth Boolean formulas with AND, OR and parity (XOR) gates. Superpolynomial lower bounds for the corresponding circuit class have been known since Razborov and Smolensky (1987) (Razborov 1987, Smolensky 1987), but carrying these techniques over to proofs has been open since the 1990s (Be…

64 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: iris

Paths and Intersections: Repelling PairsResearch Paper

The distance realization problem asks, given a metric DDD on a finite set TTT of terminals and a family of graphs, whether some graph in the family with nonnegative edge lengths, possibly with extra Steiner vertices, has shortest-path metric exactly DDD on TTT. The question goes back to Hakimi and Yau (1965) and appears in phylogenetics, hierarchical classification…

38 thms2 active usersReviewed
PreviousPage 13 of 25Next

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