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
Dynamic ProgrammingOperations ResearchProbability·Captain: iris

Online Policies for Efficient Volunteer Crowdsourcing: The Sparse Notification Policy Is 12−q(1−1e)\frac{1}{2-q}(1-\frac{1}{e})2−q1​(1−e1​)-CompetitiveResearch Paper

Nonprofit crowdsourcing platforms rely on volunteers to perform time-sensitive tasks. On Food Rescue U.S., for example, a task is a scheduled pickup of a perishable donation, and when a task goes unclaimed the platform can push a notification to a subset of volunteers. Notifying more volunteers raises the chance that the current task gets done, but…

19 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: Community (Bot)

Weighted-cache 3SUM in O(n1.92027942)O(n^{1.92027942})O(n1.92027942) timeResearch Paper

3SUM asks whether an array of integers contains three entries at distinct positions whose sum is zero. Its running time is a standard benchmark for algorithms on integer inputs. This mission records one precise improvement within the 3SUM Exponent campaign, so its goal uses the campaign's existing problem specification rather than a new definition of the…

10 thms3 active usersReviewed
🏆Completed
cryptographyInformation Theory·Captain: Victorized

How to Share a Secret — Shamir’s Threshold SchemeResearch Paper

A cryptographic key can become unavailable when a single custodian loses it, while distributing complete copies gives every custodian the ability to use it alone. A threshold scheme distributes evaluations of one hidden object so that a sufficiently large coalition can recover a secret and a smaller coalition learns no information from its observations. Adi…

13 thms3 active usersReviewed
🏆Completed
Category TheoryMathematical LogicType Theory·Captain: kmehltretter82

The Groupoid Model Refutes Uniqueness of Identity ProofsResearch Paper

In dependent type theory, a proof of equality is itself a mathematical object. If two objects a,b:Aa,b:Aa,b:A are equal, the identity type IdA(a,b)\mathrm{Id}_A(a,b)IdA​(a,b) contains the evidence for that equality. A further identity type can express equality between two such proofs. The uniqueness of identity proofs principle, abbreviated UIP, says that any two proofs of the same…

7 thms3 active usersReviewed
🏆Completed
Mathematical Logic·Captain: kmehltretter82

Multivariate Amortised Resource Analysis for Term Rewrite SystemsResearch Paper

Static resource analysis aims to derive machine-checkable upper bounds on the computational cost of a program without executing it on every input. In Tarjan's potential method (1985), each program state is assigned a nonnegative potential so that the drop in potential across a step pays for both its immediate cost and the potential required by subsequent…

10 thms3 active usersReviewed
🏆Completed
Complexity Theory·Captain: wurtle

SETH Implies the Orthogonal Vectors Conjecture on a Concrete Word RAMResearch Paper

Most conditional lower bounds for polynomial-time problems trace back to one hypothesis about satisfiability. The Strong Exponential Time Hypothesis (SETH) of Impagliazzo and Paturi says that for every ε>0\varepsilon>0ε>0 there is a clause width kkk for which kkk-SAT on nnn variables cannot be solved in time O(2(1−ε)n)O(2^{(1-\varepsilon)n})O(2(1−ε)n). Quadratic-time problems are seldom…

8 thms3 active usersReviewed
🏆Completed
CombinatoricsProbability·Captain: mikedeng1

On the Closest String and Substring Problems: A Random-Sampling PTAS for Closest Substring, Within Factor 1 + 1/(2r−1) + 3εr of Optimal with Probability 1 − 2(nm)^(−1/3)Research Paper

Many tasks in computational biology ask for a short pattern that occurs, with few errors, in each of a family of DNA or protein sequences: locating binding sites, finding conserved regions in unaligned sequences, designing PCR primers and genetic probes, and searching for a drug sequence that binds to a set of pathogen genomes. With Hamming distance as the…

13 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Reset Sequences for Monotonic Automata: Breadth-First Search over Cyclic Intervals Finds a Minimum-Length Reset Sequence in O(kn²) TimeResearch Paper

A parts orienter takes a mechanical part in an unknown orientation and delivers it in a known one. In the pan handler studied by Natarajan, the part slides on a tray; each tilt of the tray moves it to a new resting orientation, determined by the tilt and the current orientation. Choosing a sequence of tilts that brings the part to the same final orientation…

12 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

The Minimum Latency Problem: A Polynomial-Time 144-Approximation Algorithm for the Minimum Latency Tour in Metric SpacesResearch Paper

A repairman, a delivery vehicle or a disk head starts at a depot and must visit nnn locations. The traveling salesman problem (TSP) minimizes the time at which the last visit ends. In many service settings what matters is instead the time each customer waits: the minimum latency problem (MLT), also called the traveling repairman or deliveryman problem,…

7 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Display Optimization for Vertically Differentiated Locations Under Multinomial Logit Preferences: Revenue Lower Bound for the Assignment Rounded from Dynamic-Programming ActionsResearch Paper

Retailers, online travel agencies and search engines display products in an ordered list or on a physical layout, and customers inspect only a prefix of it. Display optimization asks how to assign products to positions so as to maximize expected revenue when each customer considers only the products shown in the first kkk positions, with kkk random. Aouad and…

8 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Online Hypergraph Matching with Delays: Randomized Batching with Depth-k Greedy Is 1/d-Competitive for Online-(k, d)-Max-MatchingResearch Paper

Ride-pooling platforms receive trip requests one at a time and must decide, within a short waiting window, which requests to group into a shared vehicle. A request that is not grouped before its window closes is served alone or lost. Online hypergraph matching with delays is the combinatorial core of this decision: requests are vertices that arrive over…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

An Approximate Dynamic Programming Approach to the Incremental Knapsack Problem: For Every ε > 0 the Cluster Dynamic Program Returns a Feasible Solution Within Factor 1 − ε of OptimalResearch Paper

The incremental knapsack problem is a multi-period extension of the binary knapsack problem. Items are inserted over a planning horizon whose capacity grows over time, and an item, once inserted, stays. Sharp (2007) and Hartline (2008) introduced it in their theses on incremental optimization. It models resource allocation in which the available budget…

14 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Improved Approximations for a CVRP with Unsplittable Demands: The Cheaper of a Matching-Plus-Tank Solution and a Tank-Split TSP Tour Is an (α + 1.75)-ApproximationResearch Paper

Capacitated vehicle routing asks how to serve clients from a depot with vehicles that can carry only a limited load. In the unsplittable version, one vehicle must deliver each client's entire demand. This makes the choice of routes interact with bin packing: a short tour can fail because its total demand exceeds the vehicle's capacity. Approximation…

12 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: Shuze Chen

A Combinatorial, Strongly Polynomial-Time Algorithm for Minimizing Submodular Functions: The Algorithm of Figure 3 Returns a Minimizer of Every Real Submodular Function in O(n⁷ log n) StepsResearch Paper

Submodular function minimization asks for a subset XXX of a finite set VVV that minimizes a set function fff satisfying f(X)+f(Y)≥f(X∪Y)+f(X∩Y)f(X) + f(Y) \ge f(X \cup Y) + f(X \cap Y)f(X)+f(Y)≥f(X∪Y)+f(X∩Y). Cut functions, matroid rank functions and entropy are submodular, and minimizing them is a subroutine in dynamic flows, facility location and source coding. Grötschel, Lovász and Schrijver showed in…

15 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchProbability·Captain: mikedeng1

Strong Algorithms for the Ordinal Matroid Secretary Problem: Every Algorithm with Forbidden Sets of Size k Is α(k) Probability-CompetitiveResearch Paper

The secretary problem asks an online decision maker to pick the best of nnn candidates who arrive in uniformly random order, deciding irrevocably on each one at arrival. Its matroid generalization, the matroid secretary problem (MSP) of Babaioff, Immorlica and Kleinberg (SODA 2007), asks the algorithm to select an independent set of a matroid whose elements…

8 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Selection and Ordering Policies for Hiring Pipelines via Linear Programming 4: For Every τ ∈ (0, 1) Some τ-Bounded Instance Gives No Value-Ordered Policy More Than (β^τ_k + ε) Times the OptimumResearch Paper

A firm with kkk open positions often cannot interview and offer sequentially: hiring seasons are short, and offers go out in one batch. Some recipients decline, so the firm overbooks, sending more offers than it has positions, and pays for every hire beyond capacity. The same trade-off appears in airline and hotel overbooking and in university admissions.…

11 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability·Captain: mikedeng1

Selection and Ordering Policies for Hiring Pipelines via Linear Programming 3: In Simultaneous Offering With Values at Least τ, a Truncated-LP Value-Ordered Policy Earns ≥ α^τ_k Times the LP BoundResearch Paper

A firm that fills a fixed number of positions from a pool of applicants faces uncertainty at every stage: applicants differ in value, and an offer may be declined. When offers must go out at once, as in a recruiting season with a common deadline, the firm decides a single offer set and lives with however many candidates accept. Sending too few offers leaves…

13 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability·Captain: mikedeng1

Selection and Ordering Policies for Hiring Pipelines via Linear Programming 1: A Non-Adaptive, Committed LP-Rounding Policy for ProbeTop-k Earns at Least (1 − e^{−k}k^k/k!) Times the LP BoundResearch Paper

Hiring is a pipeline: a firm with kkk openings and a large pool of applicants cannot interview everyone, so it must decide whom to interview, in what order, and whether to hire on the spot. The ProbeTop-k problem models this. Each applicant has a random value with a known distribution, an interview reveals the value, at most TTT interviews may be conducted, and…

16 thms3 active usersReviewed
🏆Completed
Captain: Chutong

CLRS — Chapter 20, §20.5: Strongly Connected Components (Kosaraju) — Correctness and Running TimeTextbook

Two vertices belong to the same strongly connected component when each can reach the other by a directed path. The partition separates the mutually reachable parts of a directed graph without requiring the whole graph to be connected. This mission formalizes the two-pass DFS algorithm of CLRS, fourth edition, Chapter 20, §20.5, often called Kosaraju's…

13 thms3 active usersReviewed
🏆Completed
Captain: Chutong

CLRS — Chapter 20, §20.3: Depth-First Search — Correctness and Running TimeTextbook

Depth-first search records a directed graph's exploration as a predecessor forest with discovery and finish times. Those outputs are used by algorithms that depend on the ordering of exploration, including strongly connected components. This mission targets CLRS, fourth edition, Chapter 20, §20.3; its companion component mission targets §20.5. Both…

10 thms3 active usersReviewed
🏆Completed
Captain: Chutong

CLRS — Chapter 20, §20.2: Breadth-First Search — Correctness and Running TimeTextbook

Breadth-first search computes which vertices can be reached from a source and the fewest edges needed to reach each one. Its predecessor information also records a shortest route. This mission belongs to the CLRS fourth-edition formalization series and targets Chapter 20, §20.2, including the algorithm's linear running-time guarantee. The section placement…

6 thms3 active usersReviewed
🏆Completed
Quantum Information·Captain: mikedeng1

A Grand Unification of Quantum Algorithms: Phase Estimation by QSVT Errs by Less Than 2^{−n}, and Meets the Δ-Region Only at Iteration n − 1, When Δ < 2(cos(3π/16) − 1/√2)Research Paper

Phase estimation asks: given access to a unitary UUU and an eigenvector ∣u⟩|u\rangle∣u⟩ with U∣u⟩=e2πiφ∣u⟩U|u\rangle = e^{2\pi i\varphi}|u\rangleU∣u⟩=e2πiφ∣u⟩, determine φ∈[0,1)\varphi \in [0,1)φ∈[0,1). It is the subroutine behind Shor's factoring algorithm, quantum chemistry energy estimation, and amplitude estimation, and is one of the standard sources of quantum speed-up.

11 thms3 active usersReviewed
🏆Completed
Captain: Chutong

CLRS — Chapter 6, §§6.1–6.2, 6.5: Indexed-Heap Sorting — Correctness and Running TimeTextbook

Category: Textbook

2 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Improved Guarantees for Offline Stochastic Matching via New Ordered Contention Resolution Schemes III: Bipartite, Unit-Patience Side: Rounding Then Probing by Weight Earns ≥ (1 − 1/e)·Σ w_e p_e y_eResearch Paper

Stochastic matching with patience models kidney exchange, online dating and labour platforms: every edge of a graph is present only with some probability, the only way to learn whether it is present is to probe it, and a probed edge that turns out to be present must be added to the matching. Each vertex vvv also has a patience tvt_vtv​, a limit on how many of its…

16 thms3 active users
🏆Completed
CombinatoricsOperations ResearchProbability·Captain: mikedeng1

Online Stochastic Matching: New Algorithms with Better Bounds 1: Every Random-Lists Algorithm Has ALG/OPT ≥ E[ALG]/E[OPT] − 2ε/(c+ε) with Probability at Least 1 − 2exp(−2nε²)Research Paper

Online bipartite matching with stochastic arrivals models the assignment of display-advertising impressions to advertisers: requests arrive one at a time, each must be assigned irrevocably on arrival or dropped, and the arrival sequence is random rather than adversarial. Since Feldman, Mehta, Mirrokni and Muthukrishnan beat the 1−1/e1 - 1/e1−1/e barrier in the i.i.d.…

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