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

A Complete Characterization of Eventually Evasive Binary PatternsResearch Paper

Deciding whether a fixed word occurs in a text is the most basic string-matching task. This mission formalizes a result about its query complexity: how many positions of an unknown text must an algorithm read, in the worst case, merely to decide whether a known binary pattern occurs? Computation is free and only reads are counted, so the question isolates…

29 thms2 active usersReviewed
CombinatoricsInformation TheoryRepresentation Theory·Captain: iris

The Honeycomb Framework for Code BoundsResearch Paper

A binary code of length nnn is a set C⊆{±1}nC\subseteq\{\pm1\}^nC⊆{±1}n; it has minimum distance at least ddd if any two distinct codewords differ in at least ddd coordinates. The rate–distance tradeoff asks for the largest size A2(n,d)A_2(n,d)A2​(n,d) of such a code, and asymptotically for

45 thms2 active usersReviewed
Complexity Theory·Captain: Shuze Chen

Beyond Width-3: Better Hitting Set Generators for Width-4 Read-Once Branching ProgramsResearch Paper

A computation with little working memory can still use many random bits. A read-once branching program records how its memory state changes as these bits arrive. Its width measures the number of possible states at each step, and its length counts the bits read. Finding short deterministic descriptions of useful input strings is one way to understand how…

27 thms2 active usersReviewed
Combinatorics·Captain: Shuze Chen

Fully Dynamic Correlation Clustering with Vertex Updates in Polylogarithmic Update TimeResearch Paper

Correlation clustering asks for a partition of the vertices of a complete graph whose edges are labelled (+)(+)(+) (similar) or (−)(-)(−) (dissimilar), minimizing the number of disagreements: (+)(+)(+) edges between clusters plus (−)(-)(−) edges inside clusters. Introduced by Bansal, Blum and Chawla (DOI 10.1023/B:MACH.0000033116.57574.95), it is a standard model for…

22 thms2 active usersReviewed
CombinatoricsGraph TheoryOperations Research·Captain: iris

Breaking the O(mn)O(mn)O(mn) Barrier for Minimum Bipartite Dijoin via Dynamic and Local Graph AlgorithmsResearch Paper

A dijoin of a digraph is a set of arcs whose contraction makes the digraph strongly connected; equivalently, a set of arcs meeting every dicut, the nonempty set of arcs crossing a vertex bipartition when all crossing arcs point the same way. Lucchesi and Younger proved in 1978 that the minimum size of a dijoin equals the maximum number of pairwise…

30 thms2 active usersReviewed
Computational ComplexityProbability·Captain: Shuze Chen

Exact Parallel Sampling without Maximal Independent SetsResearch Paper

A counting oracle for a distribution μ\muμ on [q]n[q]^n[q]n answers a query (S,y)(S,y)(S,y) with the marginal probability Pr⁡X∼μ[XS=y]\Pr_{X\sim\mu}[X_S=y]PrX∼μ​[XS​=y]. Any-order autoregressive and masked diffusion models provide exactly this access. With it, μ\muμ can be sampled coordinate by coordinate, but that takes nnn sequential rounds. The question of parallel sampling is how many adaptive rounds…

23 thms2 active usersReviewed
Dynamic ProgrammingOperations ResearchOptimization·Captain: Shuze Chen

Fine-Grained Complexity of Approximating Vector Knapsack: A Faster Algorithm and Equivalence with kkk-SUM in 2DResearch Paper

In ddd-Knapsack (the vector or multidimensional knapsack problem) every item has a profit and a ddd-dimensional weight vector, and one must choose a set of items of maximum total profit whose total weight stays within a capacity in every coordinate. It models any selection problem with several budgets at once (money, time, space, staff) and is the simplest…

21 thms2 active usersReviewed
Complexity TheoryInformation TheoryProbability·Captain: Shuze Chen

Tight Bounds for Rank Estimation in Turnstile StreamsResearch Paper

A rank query asks how much of a dataset lies below a threshold; together with its inverse, the select (quantile) query, it summarizes the empirical distribution of the data: medians, percentiles, tail behaviour, and selectivity estimates for database queries. When the data change through insertions and deletions (database records removed, network sessions…

24 thms2 active usersReviewed
Graph Theory·Captain: Shuze Chen

Local Distributed Computation under Crash FailuresResearch Paper

In the LOCAL model of distributed computing, every node of a communication graph runs the same deterministic program, rounds are synchronous, messages are unbounded, and a problem's complexity is the number of rounds after which every node can produce its output. Without failures, a node learns its whole radius-RRR neighborhood in RRR rounds, so any TTT-round…

20 thms2 active usersReviewed
Complexity Theory·Captain: mikedeng1

An Explicit and Optimal Separation of BPP from NP in Number-on-Forehead Communication ComplexityResearch Paper

Communication complexity measures how many bits participants must exchange when each sees only part of an input. In the number-on-forehead model, there are kkk participants and kkk input blocks: participant iii sees every block except block iii. Their overlapping knowledge makes lower bounds difficult. A separation between randomness and nondeterminism asks whether…

13 thms2 active usersReviewed
CombinatoricsProbability·Captain: mikedeng1

The Local Probe Complexity of Maximal Independent SetResearch Paper

A maximal independent set in a graph is a collection of vertices with no edge between two chosen vertices, such that every unchosen vertex has a chosen neighbor. A local computation algorithm answers whether a queried vertex belongs to one fixed solution while inspecting only part of the graph. Different queries must agree with that solution even though…

22 thms2 active usersReviewed
Combinatorics·Captain: iris

Near-Optimal Compressed Algorithms and Data Structures by Eliminating Recursive SubstructuresResearch Paper

A rank query on a string TTT asks how many times a symbol ccc occurs among the first iii symbols of TTT. Rank queries are a basic primitive of compressed text indexes (FM-index, wavelet trees), and on an uncompressed text over an integer alphabet they are answered in near-constant time after linear preprocessing. Compressed indexing asks for the same queries when TTT…

24 thms2 active usersReviewed
Graph TheoryLinear algebra·Captain: iris

Revisiting Local Push: Faster Algorithms and Optimal Query Complexity for PageRank and Effective ResistanceResearch Paper

Personalized PageRank from a seed node is the basic primitive of local graph algorithms: it drives local clustering by sweep cuts (Andersen, Chung, Lang 2007; Andersen, Chung 2007) and the bidirectional estimation of single PageRank values (Lofgren, Banerjee, Goel 2015). The standard local method is the push of Andersen, Chung and Lang. It computes an…

29 thms2 active usersReviewed
Graph TheoryProbability·Captain: iris

Trees with Benefits: Stochastic Hop-Constrained Ramsey-Type Embeddings with Logarithmic Expected DistortionResearch Paper

Many network design and routing problems limit the number of edges, or hops, a path may use: hop limits bound delay and the probability that some link on a path fails, and they govern the round complexity of parallel shortest-path computations. The relevant distance is then the hop-constrained distance dG(h)(u,v)d^{(h)}_G(u,v)dG(h)​(u,v), the least weight of a uuu–vvv path with at…

31 thms2 active usersReviewed
CombinatoricsProbability·Captain: mikedeng1

The Query Cost of Certifying a RankingResearch Paper

A comparison system can produce a useful ranking while leaving substantial uncertainty about what its acquired answers justify. This matters when a released estimate must be defensible from a public record: a user who did not observe an estimator's private choices needs a guarantee that survives every plausible explanation of the comparisons. Persistent…

39 thms2 active usersReviewed
Harmonic AnalysisProbability·Captain: mikedeng1

Sharp Limits of Time Invariance in Private Continual CountingResearch Paper

Continual counting releases an estimate of a running sum whenever another stream element arrives. The same person’s contribution must remain protected across the entire sequence of releases. Streams without a known stopping time make this a distinct design problem: a mechanism chosen for one horizon does not automatically define one mechanism that works…

23 thms2 active usersReviewed
Complexity TheoryGraph Theory·Captain: mikedeng1

k-Coloring is Faster than Computing the Chromatic NumberResearch Paper

Graph coloring is one of the basic NP-complete problems, and its exact exponential-time complexity has been studied for decades. Computing the chromatic number χ(G)\chi(G)χ(G) of an nnn-vertex graph takes O∗(2n)O^*(2^n)O∗(2n) time by the inclusion–exclusion algorithm of Björklund, Husfeldt and Koivisto (SIAM J. Comput. 2009), where O∗O^*O∗ hides factors polynomial in the input size.…

17 thms2 active usersReviewed
Convex OptimizationProbabilityStatistics·Captain: mikedeng1

An Exact-Radius Convex Characterization of Discrete Identity TestingResearch Paper

Identity testing asks whether observations follow a specified probability distribution or a distribution farther than a prescribed distance from it. For a known finite reference, the amount of data needed can depend on the distribution of mass across labels, including a dominant atom, a light tail, and labels with zero reference probability. A bound that…

24 thms2 active usersReviewed
Probability·Captain: mikedeng1

The Online k-Taxi Problem Is Competitive on All MetricsResearch Paper

In the online k-taxi problem [FRR90], k taxis sit in a metric space and requests arrive one at a time, each an ordered pair of a pickup point and a drop-off point. An online algorithm must pick the serving taxi without knowing future requests. The classical k-server problem is the special case where every pickup equals its drop-off. The problem models…

22 thms2 active usersReviewed
Machine LearningProbability·Captain: mikedeng1

Lower Bounds for Parallel Diffusion SamplingResearch Paper

A diffusion sampler produces a random vector by repeatedly asking for information about a distribution after Gaussian noise has been added. Such queries are often the expensive part of generation. Parallel implementations can evaluate many proposed locations simultaneously, but the next batch can still depend on earlier answers. The question is how many…

25 thms2 active usersReviewed
CombinatoricsProbability·Captain: mikedeng1

The Strong Secretary Conjecture is True for Linear MatroidsResearch Paper

In the Matroid Secretary Problem, introduced by Babaioff, Immorlica and Kleinberg (SODA 2007; J. ACM version), the elements of a matroid carry nonnegative weights and arrive in uniformly random order. On each arrival the algorithm learns the element's weight and must decide irrevocably whether to keep it, while the kept set stays independent. The model…

18 thms2 active usersReviewed
Combinatorics·Captain: mikedeng1

Recovery Beats Storage: Improved Space for Preprocessed 3SUMResearch Paper

The 3SUM problem asks whether finite integer sets A,B,CA,B,CA,B,C contain values a,b,ca,b,ca,b,c with a+b=ca+b=ca+b=c. When many instances draw from the same large sets, preparing information once can reduce the cost of subsequent instances. Preprocessed 3SUM with unknown CCC permits preparation of AAA and BBB, while every query supplies its own subsets and its own target set. This separates…

20 thms2 active usersReviewed
Complexity Theory·Captain: mikedeng1

Lifting to Unary Sherali–Adams over ParitiesResearch Paper

A propositional proof system certifies that a collection of Boolean constraints has no satisfying assignment. Its resources depend on the language in which certificates are written. For Sherali–Adams, a certificate uses a polynomial identity together with nonnegative combinations of conjunctions of literals. Bounds on polynomial degree alone do not control…

27 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

New bounds for online coloring three-colorable graphsResearch Paper

A proper coloring assigns different colors to adjacent vertices of a graph. In the online vertex-coloring problem, vertices arrive one at a time with their edges to earlier vertices, and each color choice is immediate and irrevocable. The algorithm has to commit before learning which future vertices will connect to its current color classes. This separates…

12 thms2 active usersReviewed
Algorithmic Game TheoryOperations Research·Captain: mikedeng1

Weakly Stable Roommates with Two Master Lists: Tractable Existence and Hard OptimizationResearch Paper

A roommates matching partitions a population into pairs. Each person ranks possible partners, and a proposed arrangement is stable when no two people both strictly prefer one another to their assigned partners. Preferences may contain ties. A person who is indifferent does not participate in a blocking pair on that comparison. This distinction matters when…

28 thms2 active usersReviewed
PreviousPage 21 of 34Next

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