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
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
🏆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
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
🏆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
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
🏆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
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
🏆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
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
🏆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
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
🏆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
Probability·Captain: mikedeng1

Optimal Sparsification of Gaussian ProcessesResearch Paper

A Gaussian process is a family of random variables whose finite subfamilies are jointly Gaussian. Its supremum describes the largest fluctuation across a collection of correlated measurements. In finite-dimensional geometry, the same construction gives support functions of convex sets and many norm representations. Knowing the expectation of such a supremum…

22 thms2 active usersReviewed
CombinatoricsOperations Research·Captain: mikedeng1

Coordinating Boundaries: Improved Approximation Algorithms for Unweighted Non-Preemptive Throughput MaximizationResearch Paper

Nonpreemptive throughput maximization is a basic real-time scheduling problem: a set of jobs, each available only during a time window, must be placed on identical machines so that as many jobs as possible finish by their deadlines. It models admission control in real-time systems and allocation of communication resources (Bar-Noy, Guha, Naor and Schieber,…

20 thms2 active usersReviewed
Graph TheoryLinear algebra·Captain: mikedeng1

A Tight Superlinear Lower Bound on the Sketching Dimension of Weighted Spectral SparsificationResearch Paper

A spectral sparsifier of a weighted graph is a matrix that approximately preserves every quadratic form of its Laplacian. Sparsifiers are used to compute cuts and flows, solve Laplacian systems and cluster graphs. In the linear sketching model the graph is accessible only through a small number of fixed linear measurements of its edge weights. This model…

28 thms2 active usersReviewed
PreviousPage 34 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