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
Algorithmic Game Theory·Captain: Shuze Chen

Algorithmic Game Theory I: Existence of Nash EquilibriumTextbook

The strategic-form game is the basic object of noncooperative game theory, and the Nash equilibrium — a profile of randomized strategies from which no player benefits by deviating unilaterally — is its central solution concept. Nash proved in 1951 that every game with finitely many players and finite strategy sets has such an equilibrium (Nash, Non-cooperati…

10 thms4 active usersReviewed
🏆Completed
Captain: marwahaha

Coppersmith–Winograd Bound: omega < 2.376Research Paper

AI generated but i think correct. I think the milestones make it really annoying but the central theorem looks correct.

72 thms4 active usersReviewed
🏆Completed
Captain: marwahaha

Sensitivity ConjectureResearch Paper

Nearly every measure of Boolean function complexity was known to be equivalent — except sensitivity. Proving the conjecture unified the whole picture.

49 thms4 active usersReviewed
🏆Completed
Computational ComplexityQuantum Information·Captain: iris

Randomized query complexity can beat certificate complexityResearch Paper

Query complexity measures how many input bits an algorithm must read to evaluate a Boolean function f:{0,1}N→{0,1}f:\{0,1\}^N\to\{0,1\}f:{0,1}N→{0,1}. For total functions (defined on every input) the classical, randomized and quantum measures are polynomially related, and a large part of the field consists of pinning down the best exponents in these relations; see the survey of…

39 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
🏆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
🏆Completed
CombinatoricsGraph TheoryProbability·Captain: Shuze Chen

Robust Shattering ArgumentsResearch Paper

Many fast randomized distributed algorithms, for the Lovász Local Lemma, maximal independent set, matching and coloring, follow the shattering paradigm (Barenboim, Elkin, Pettie, Schneider, JACM 2016). A randomized pre-shattering phase solves the problem on most of the graph. It leaves a residual set BBB of unresolved nodes, and the analysis has to show that…

10 thms3 active usersReviewed
🏆Completed
AlgebraComputational Complexity·Captain: Shuze Chen

PIT and Reconstruction for Sums of High PowersResearch Paper

Polynomial identity testing (PIT) asks whether a polynomial given by an arithmetic circuit is identically zero. In the black-box version the algorithm may only evaluate the polynomial at points of its choice, and a deterministic black-box algorithm is the same thing as a hitting set: a fixed finite set of points at which every nonzero polynomial of the…

12 thms3 active usersReviewed
🏆Completed
Formal VerificationGraph Theory·Captain: mikedeng1

Büchi Determinization with Optimal States and Square Root Index ImprovementResearch Paper

Automata on infinite words describe behavior that continues indefinitely. In formal verification, a system execution is such a word, and an acceptance condition expresses a property of its long-term behavior. Converting a nondeterministic automaton to a deterministic one can make subsequent operations possible, but the conversion has two costs: the number…

31 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: Shuze Chen

Consistent Submodular Maximization with Full ForesightResearch Paper

Online algorithms with recourse maintain a good solution while the input grows, and limit how much the solution changes at each update. For monotone submodular maximization under a cardinality constraint, the consistent version of this problem was introduced by Dütting et al. (2024) and studied further by Dütting et al. (2025) and Fu et al. (2026). In those…

30 thms3 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: mikedeng1

A (4m - 5)-Competitive Deterministic Algorithm for Online TransportationResearch Paper

An online transportation problem asks how to allocate arriving demand when destinations have fixed capacities and future demand is unknown. Cars arrive one at a time at points of a known finite metric space. Each car must immediately receive a garage with an unused slot. That assignment is irrevocable. The objective is the sum of the distances from arrival…

16 thms3 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryProbability·Captain: mikedeng1

Top-Down Lower Bounds for All DepthsResearch Paper

A Boolean circuit computes a function by composing gates. Parity asks whether an input word contains an odd number of ones. It is a basic test of the power of bounded-depth computation: unrestricted AND and OR gates can inspect many bits at once, yet computing parity at fixed depth requires exponentially many wires. The quantitative lower-bound form…

21 thms3 active usersReviewed
🏆Completed
Graph Theory·Captain: mikedeng1

Polynomial Lower Bounds for Steiner Shortcuts via Test FunctionsResearch Paper

A directed reachability query asks whether a directed graph contains a path from one specified vertex to another. Many algorithms first add edges to reduce the number of edges that such a path needs. This matters in parallel and distributed computation because a path requiring many successive steps can force many rounds of communication or dependent work.…

24 thms3 active usersReviewed
🏆Completed
AlgebraComplexity Theory·Captain: mikedeng1

A Width Hierarchy of Monotone Algebraic Branching ProgramsResearch Paper

Algebraic complexity studies how much arithmetic is needed to produce a polynomial from its variables and constants. A monotone computation uses only nonnegative coefficients, so terms cannot disappear by cancellation. This restriction makes resource lower bounds accessible while retaining models that distinguish addition, multiplication, and reuse of…

22 thms3 active usersReviewed
🏆Completed
CombinatoricsInformation Theory·Captain: mikedeng1

Making Every Edit Count: Efficient Binary Edit Correction at the Gilbert–Varshamov BoundResearch Paper

An insertion or deletion changes the positions of later symbols. A receiver therefore faces uncertainty about alignment as well as about the values of damaged bits. Edit-correcting codes address this problem by restricting the transmitted words so that nearby received sequences identify a unique original message. File synchronization is one concrete…

33 thms3 active usersReviewed
🏆Completed
CombinatoricsInformation Theory·Captain: mikedeng1

Explicit Edit Codes via MulticoloringResearch Paper

An edit channel can insert a symbol, delete a symbol, or substitute one symbol for another. Insertions and deletions change the positions of subsequent symbols, so a decoder must recover information without knowing which received positions correspond to transmitted positions. A code restricts transmitted words so that these changes can be corrected. The…

53 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Stability Dichotomies for Boolean Constraint Satisfaction ProblemsResearch Paper

A solver can return a correct answer and still react sharply to a small change in its input. For a constraint satisfaction problem, deleting a requirement leaves every old solution valid, but a solver may nevertheless change many variable values. Understanding when that disruption is unavoidable is useful for distinguishing a property of the problem from a…

18 thms3 active usersReviewed
🏆Completed
OptimizationProbability·Captain: mikedeng1

The Optimizer's Windfall: Bounding Hindsight Gain under Random RestrictionsResearch Paper

Sampling variables is a basic way to estimate large optimization problems. An algorithm reads the interactions among the retained variables, optimizes that smaller instance, and rescales the answer. Every fixed assignment has the right expected score after rescaling. The assignment chosen after seeing the sample can do better, however, because it responds…

33 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
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: iris

Single-or-Sample: Online Fair Allocation for Combinatorial AgentsResearch Paper

Consider a relief center that hands out indivisible supplies to people arriving over time, each with different needs. Everything handed out is gone, and nothing is known about who comes next. Maximin share (MMS) fairness, introduced by Budish 2011, measures an agent's share using only that agent's own valuation: the value the agent could guarantee by…

32 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph Theory·Captain: iris

Tangle structure treesResearch Paper

Tangles were introduced by Robertson and Seymour in the Graph Minors project as a way to describe highly connected regions of a graph indirectly: instead of naming a vertex set, a tangle orients every low-order separation of the graph towards the side where the region lies. Diestel and coauthors later abstracted the notion away from graphs. In an abstract…

37 thms3 active usersReviewed
🏆Completed
CombinatoricsMachine Learning·Captain: iris

On the VC Dimension of Autoregressive Linear Threshold FunctionsResearch Paper

An autoregressive model applies one fixed next-token rule to the current sequence, appends the produced token, and repeats. Intermediate tokens act as computation steps, which is one explanation of why chain-of-thought generation increases the power of language models. Joshi et al. introduced a learning framework for this process: a fixed generator runs for …

22 thms3 active usersReviewed
🏆Completed
Complexity Theory·Captain: iris

On the Composition Theorem for Approximate Degree, Randomized and Exact Quantum Query ComplexityResearch Paper

The approximate degree of a Boolean function f:{0,1}n→{0,1}f:\{0,1\}^n\to\{0,1\}f:{0,1}n→{0,1} is the least degree of a real polynomial that agrees with fff to within 1/31/31/3 at every point of the Boolean cube. It lower-bounds bounded-error quantum query complexity, and through the pattern-matrix and related methods it drives lower bounds in communication complexity, circuit complexity and…

32 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryProbability·Captain: iris

Randomized Greedy MIS is Fast at Every NodeResearch Paper

A local computation algorithm answers a query about one part of a global solution (here: is vertex vvv in the maximal independent set?) by inspecting only a small neighbourhood of vvv, so that answers to different queries are consistent with one global solution. Nguyen and Onak (FOCS 2008) simulated the randomized greedy maximal independent set (RGMIS) this…

41 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: iris

Weighted Equitability and Matroid-Constrained DiscrepancyResearch Paper

Partitioning a set of goods, jobs or edges into structured pieces of nearly equal value is a recurring question in combinatorial optimization and fair division. Matroids are the standard abstraction of the structure involved: spanning trees of a graph, linearly independent column sets, and partition constraints are all bases of a matroid.

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