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

Three Partition Refinement Algorithms 2: Refining by the Smaller HalfResearch Paper

Many equivalence problems on finite structures reduce to computing the coarsest partition of a finite set that is compatible with a relation. Deciding whether two states of a finite labelled transition system are bisimilar, testing congruence of finite-state processes in Milner's calculus of communicating systems (CCS), and minimizing a deterministic finite…

12 thms4 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

Competitive Paging Algorithms I: The Marking Algorithm Is 2H_k-CompetitiveResearch Paper

Paging is the problem of managing a two-level memory: a fast cache holds kkk pages out of an address space of nnn pages, requests to pages arrive one at a time, and a request to a page outside the cache (a page fault) forces the algorithm to bring that page in and, when the cache is full, to evict another. The cost is the number of faults. An on-line algorithm…

10 thms4 active usersReviewed
CombinatoricsComplexity TheoryOperations Research+1·Captain: mikedeng1

A Threshold of ln n for Approximating Set Cover II: The Inapproximability of Max k-CoverResearch Paper

Max kkk-cover is the basic coverage problem of combinatorial optimization. The input is a collection of subsets of a finite ground set and a number kkk; the task is to choose kkk subsets that together cover as many points as possible. It models facility and sensor placement, the selection of a small committee or feature set representing a population, and budgeted…

23 thms4 active usersReviewed
CombinatoricsComplexity TheoryOperations Research·Captain: mikedeng1

A Threshold of ln n for Approximating Set Cover I: The ln n Inapproximability of Set CoverResearch Paper

Set cover is the problem of covering a finite ground set with as few members of a given family of subsets as possible. It models facility location, crew scheduling, test-suite minimization and many other selection problems in operations research, and it is one of the canonical NP-hard problems. The greedy algorithm, which repeatedly picks the subset…

20 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

An Analysis of Several Heuristics for the Traveling Salesman Problem I: Nearest Neighbor Tours Can Be Far from OptimalResearch Paper

The traveling salesman problem with the triangle inequality asks for a shortest closed tour through nnn points whose distances form a metric. It is NP-hard, so in practice tours are built by fast construction heuristics, and the natural question is how far such a tour can be from optimal in the worst case. Rosenkrantz, Stearns and Lewis (SIAM J. Comput. 6(3),…

12 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms 4: First-Fit Decreasing Uses at Most 71/60 L* + 5 Bins When No Item Exceeds 1/2Research Paper

Bin packing asks how to place a list of items with sizes in (0,1](0,1](0,1] into as few unit-capacity bins as possible. It models the cutting of stock material, the packing of files onto tracks of a disc and the assignment of jobs to machines with a common deadline. Deciding the optimum is NP-hard, so in practice simple rules are used, and the question is how far…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms 3: First-Fit Decreasing and Best-Fit Decreasing Use at Most 11/9 L* + 4 BinsResearch Paper

Bin packing asks for the fewest unit-capacity bins that hold a given list of item sizes. It models table formatting, the placement of program segments on pages, and the allocation of files to disc tracks, and it is NP-complete, so exact solutions require search in general. Johnson, Demers, Ullman, Garey and Graham (SIAM J. Comput. 3 (1974)) therefore…

12 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms 2: First-Fit and Best-Fit with Bounded Item SizesResearch Paper

Bin packing asks for the fewest unit-capacity bins that hold a given list of item sizes. It models cutting stock, memory allocation, file placement and the loading of trucks, and it is NP-hard, so in practice lists are packed by simple rules that look at one item at a time. The two most widely used rules are First-Fit and Best-Fit, and the question that…

7 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Worst-Case Performance Bounds for Simple One-Dimensional Packing Algorithms 1: First-Fit and Best-Fit Have Asymptotic Worst-Case Ratio 17/10Research Paper

Bin packing asks for the fewest unit-capacity bins that hold a given list of item sizes. It is one of the first problems studied through the worst-case analysis of approximation algorithms, and it models storage allocation, paging and file placement on tracks, as well as cutting-stock problems in operations research. Deciding the optimum exactly is NP-hard,…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: mikedeng1

Approximation Techniques for Average Completion Time Scheduling I: Best-α on One Machine with Release DatesResearch Paper

Minimizing the average completion time of jobs that arrive over time is one of the basic objectives of machine scheduling: it measures how long, on average, a job waits in the system. On a single machine with release dates and no preemption (written 1∣rj∣∑Cj1|r_j|\sum C_j1∣rj​∣∑Cj​), the problem is strongly NP-hard, so research has focused on approximation algorithms whose…

9 thms4 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization·Captain: mikedeng1

Local Search Heuristics for k-Median and Facility Location Problems III: Add-Drop-Swap Local Search for Uncapacitated Facility Location Has Locality Gap 3Research Paper

The uncapacitated facility location (UFL) problem is one of the basic models of location theory and operations research: a firm chooses which warehouses, plants or servers to open, paying a fixed cost for each open site and a service cost for every client according to its distance to the nearest open site. It is also a standard test case for approximation…

10 thms4 active usersReviewed
Functional AnalysisOptimization·Captain: LG

The Grothendieck Constant: New Upper and Lower BoundsOpen Problem

Given a real matrix A=(aij)∈Rm×nA=(a_{ij})\in\mathbb R^{m\times n}A=(aij​)∈Rm×n, consider maximizing the bilinear form ∑i,jaijxiyj\sum_{i,j}a_{ij}x_iy_j∑i,j​aij​xi​yj​ over sign vectors x∈{±1}mx\in\{\pm1\}^mx∈{±1}m, y∈{±1}ny\in\{\pm1\}^ny∈{±1}n. This discrete optimum, written OPT(A)\mathrm{OPT}(A)OPT(A), is closely tied to the cut norm of a matrix and is NP-hard to compute. Relaxing each sign to a unit vector and each product to an inner product…

13 thms4 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: mikedeng1

The Design of Competitive Online Algorithms via a Primal-Dual Approach VII: Online Group Steiner TreesTextbook

The group Steiner tree problem generalizes the ordinary Steiner tree problem: given a rooted tree and several groups of vertices, find a minimum-cost subtree that connects at least one vertex of each group to the root. It is a canonical instance of the generalized-connectivity family this survey studies in Chapter 11 — a family that also contains the online…

11 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

The Design of Competitive Online Algorithms via a Primal-Dual Approach IV: Generalized CachingTextbook

Caching is a two-level memory-management problem — the fast level (cache) can hold only kkk items, and the algorithm must decide, online, which item to evict whenever the current request misses — that is normally analyzed through the competitive ratio of ad hoc marking or LRU-style rules. Buchbinder and Naor's survey [1] instead recasts weighted caching…

15 thms4 active users
🏆Completed
Linear OptimizationOperations Research·Captain: mikedeng1

The Design of Competitive Online Algorithms via a Primal-Dual Approach II: The Online Set-Cover ProblemTextbook

Section 4 of this survey derives a simple randomized O(log⁡mlog⁡n)O(\log m \log n)O(logmlogn)-competitive algorithm for the online set-cover problem, by rounding the fractional solution the online packing-covering framework produces. An intriguing question the survey poses next: can the same guarantee be achieved deterministically? The standard tool for removing randomness, the…

7 thms4 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Foundations of Machine Learning XI: Maximum Entropy Models and DualityTextbook

Maximum entropy (Maxent) models are a widely used family of density-estimation algorithms: given a sample and a set of features, they select the distribution that matches the empirical feature averages while being otherwise as "agnostic" (close to a prior, usually uniform) as possible — a principle that, notably, never requires specifying a parametric…

15 thms4 active usersReviewed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Foundations of Machine Learning VIII: Multi-Class Classification and the Margin BoundTextbook

Every generalization bound in chapters 2-5 is for binary classification. Most real-world classification problems have more than two classes, and the number of classes can itself be in the hundreds or thousands (topic classification, speech recognition). Chapter 9 extends the margin-based generalization theory of chapter 5 (SVMs) to this multi-class,…

18 thms4 active users
🏆Completed
Machine LearningProbabilityRandom Matrix Theory+1·Captain: mikedeng1

High-Dimensional Probability VIII: Dudley's Integral InequalityTextbook

Many questions in high-dimensional probability reduce to bounding the expected supremum of a random process (Xt)t∈T(X_t)_{t\in T}(Xt​)t∈T​ — the maximum, over an entire indexed family of random variables, of how large any one of them can get. When TTT is finite this is routine (a union bound over ∣T∣|T|∣T∣ terms suffices), but the interesting cases have TTT infinite, even…

8 thms4 active users
Machine LearningProbabilityStatistics·Captain: mikedeng1

Foundations of Machine Learning III: Structural Risk Minimization and Model SelectionTextbook

Chapters 2 and 3 bound the estimation error of a hypothesis chosen from a fixed hypothesis set HHH, but the choice of HHH itself is left open: a richer HHH lowers the approximation error (how close HHH comes to the Bayes classifier) at the price of a looser generalization bound, and a poorer HHH does the reverse. Chapter 4 is the book's answer to this trade-off. It…

16 thms4 active users
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Foundations of Machine Learning I: The PAC Learning FrameworkTextbook

How many labeled examples does a learning algorithm need to see before its output generalizes well to unseen data? Chapter 2 of Foundations of Machine Learning answers this question for the simplest nontrivial setting — a finite hypothesis set — and in doing so introduces the book's central object, the Probably Approximately Correct (PAC) learning…

9 thms4 active users
🏆Completed
Linear OptimizationOptimization·Captain: moutei

Primal-Dual Online Algorithms II: Finite LP Duality and Complementary SlacknessTextbook

Almost every competitive online algorithm built by the primal-dual method rests on the same two facts about a pair of linear programs. The first is weak duality: any feasible solution of the dual is a lower bound on any feasible solution of the primal. The second is complementary slackness: if a feasible primal-dual pair satisfies a local, per-coordinate…

11 thms4 active usersReviewed
Quantum Information·Captain: Goku

Stabilizer Rank of Magic StatesOpen Problem

Quantum circuits built from Clifford gates alone are classically simulable in polynomial time. Universality is recovered by adding copies of a magic state, and the fastest known classical simulators of such circuits work by writing the magic-state input as a short linear combination of stabilizer states. The length of the shortest such combination -- the sta…

5 thms4 active usersReviewed
🏆Completed
Quantum Information·Captain: Goku

The Aaronson-Ambainis ConjectureOpen Problem

Quantum query algorithms are known to beat classical ones on problems with algebraic structure -- period finding, hidden subgroups, forrelation. No such speedup is known for a problem with no structure at all. Aaronson and Ambainis proposed making that observation into a theorem, and reduced it to a question with no quantum content: a statement about…

14 thms4 active usersReviewed
🏆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
PreviousPage 12 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