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
CombinatoricsDiscrete Geometry·Captain: wurtle

The Euclidean Steinitz–Bergström theoremResearch Paper

Given vectors v1,…,vNv_1,\dots,v_Nv1​,…,vN​ in the Euclidean unit ball of Rd\mathbb R^dRd that sum to zero, can they always be reordered so that every partial sum stays in a ball whose radius depends only on ddd? Steinitz's lemma, from his work on rearrangements of conditionally convergent vector series, says yes: in any norm, radius ddd suffices (Grinberg–Sevast'yanov 1980). For…

9 thms4 active usersReviewed
🏆Completed
Dynamical SystemsOperations ResearchStochastic Systems·Captain: mikedeng1

The Power of Two Choices in Randomized Load Balancing I: In the Limiting Supermarket System the Expected Time Converges to T_d(λ) = Σ λ^((d^i−d)/(d−1))Research Paper

Randomized load balancing asks how much a dispatcher gains from a little information. In the supermarket model, jobs arrive at nnn servers and each job inspects a few servers chosen at random before joining one. With one random choice every server is an independent M/M/1 queue, and the expected time a job spends in the system is 1/(1−λ)1/(1-\lambda)1/(1−λ) at load λ\lambdaλ.…

8 thms4 active usersReviewed
🏆Completed
Harmonic AnalysisProbability·Captain: mikedeng1

On Lattices, Learning with Errors, Random Linear Codes, and Cryptography 1: A Discrete Gaussian on L + u Plus Continuous Gaussian Noise ν_s Is Within Statistical Distance 4ε of ν_t, t = √(r² + s²)Research Paper

The learning with errors (LWE) problem underlies most of post-quantum public-key cryptography. Its hardness rests on Regev's reduction from worst-case lattice problems to LWE (Regev, J. ACM 2009). The reduction is iterative: it repeatedly turns samples of a discrete Gaussian on a lattice into samples of a narrower one. Its classical step, Lemma 3.11, needs…

11 thms4 active usersReviewed
🏆Completed
Number TheoryProbability·Captain: mikedeng1

On Lattices, Learning with Errors, Random Linear Codes, and Cryptography 5: If Every χ^⋆k Is Below ⌊p/2⌋/2 with Probability > 1 − δ, the Cryptosystem Decrypts Correctly with Probability ≥ 1 − δResearch Paper

Learning with errors (LWE) asks to recover a secret vector s∈Zpns \in \mathbb Z_p^ns∈Zpn​ from noisy inner products (ai,⟨ai,s⟩+ei)(a_i, \langle a_i, s\rangle + e_i)(ai​,⟨ai​,s⟩+ei​), where the aia_iai​ are uniform and the errors eie_iei​ are drawn from a narrow distribution χ\chiχ on Zp\mathbb Z_pZp​. Regev introduced the problem and showed that solving it is at least as hard as solving worst-case lattice problems…

5 thms4 active usersReviewed
🏆Completed
Machine LearningOperations Research·Captain: mikedeng1

The Weighted Majority Algorithm 9: With η Anomalies Every Randomized Learner Can Be Forced to ½ opt(F, 0) + η Expected MistakesResearch Paper

Prediction with expert advice asks a learner to predict a binary label on each of a sequence of trials, after seeing the predictions of a pool of candidate functions, and to make few more mistakes than the best member of the pool. Littlestone and Warmuth's The Weighted Majority Algorithm (Inform. and Comput. 108, 1994) gave the deterministic algorithm WM…

7 thms4 active usersReviewed
🏆Completed
AlgebraInformation Theory·Captain: mikedeng1

Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data 3: Shingling plus PinSketch Gives an Average-Case Secure Sketch for Edit DistanceResearch Paper

Biometric readings, physical unclonable functions and typed passphrases share two defects as cryptographic keys: they are not uniformly distributed, and they are never reproduced exactly. Dodis, Ostrovsky, Reyzin and Smith (SIAM J. Comput. 38(1), 2008; preprint arXiv:cs/0602007v4) introduced the secure sketch to handle the second defect without destroying…

13 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Fast Approximation Algorithms for Fractional Packing and Covering Problems 2: An ε-Relaxed Decision Procedure for Fractional Covering Using O(m + ρ log² m + ε⁻²ρ log(m/ε)) Oracle CallsResearch Paper

Many linear programs that arise in combinatorial optimization ask only whether a convex set contains a point satisfying a family of nonnegative linear constraints. In the fractional covering problem the constraints have the form Ax≥bAx\ge bAx≥b with A≥0A\ge 0A≥0: the fractional relaxation of set cover, the Held–Karp lower bound for the travelling salesman problem, and…

10 thms4 active usersReviewed
🏆Completed
CombinatoricsNumber TheoryProbability·Captain: mikedeng1

A New Class of Random Number Generators 2: For Prime m = bʳ − bˢ + 1, Every Nontrivial Subtract-with-Borrow Sequence Is Periodic After r Steps, with Period the Order of b mod mResearch Paper

A pseudorandom number generator replaces repeated random sampling with a deterministic update of a small state. Its useful lifetime depends on the length and structure of the resulting orbit. In Marsaglia and Zaman’s 1991 paper, the subtract-with-borrow generators use only digit subtraction and a one-bit borrow while attaining cycles that can be almost as…

17 thms4 active usersReviewed
🏆Completed
Linear algebraNumber Theory·Captain: mikedeng1

Factoring Polynomials with Rational Coefficients II: The Basis Reduction Algorithm Terminates and Returns a Reduced Basis of the LatticeResearch Paper

A lattice is the set of integer combinations of nnn linearly independent vectors in Rn\mathbb R^nRn. Many computational problems — factoring polynomials over Q\mathbb QQ, simultaneous diophantine approximation, integer programming in fixed dimension, breaking knapsack cryptosystems, and the analysis of lattice-based cryptography — reduce to finding a good basis of…

10 thms4 active usersReviewed
🏆Completed
Graph TheoryLinear Optimization·Captain: mikedeng1

Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms I: Every Uniform Multicommodity Flow Problem Has Ω(𝒮/log n) ≤ f ≤ 𝒮Research Paper

A multicommodity flow problem asks to route several commodities simultaneously through a capacitated network, each from its own source to its own sink. For a single commodity, the max-flow min-cut theorem of Ford and Fulkerson says that the largest routable flow equals the capacity of the smallest separating cut. For many commodities the natural analogue…

10 thms4 active usersReviewed
🏆Completed
Graph TheoryLinear Optimization·Captain: mikedeng1

Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms IV: A Uniform Flow of Size Ω(𝒮/log n) on Paths of Length O(C_max log n/(n𝒮))Research Paper

Communication networks must route many source–destination demands through shared edges. A multicommodity flow describes how much of each demand can be carried simultaneously without exceeding an edge's capacity. In an undirected network, a cut bounds the traffic that can pass between two groups of vertices, but many commodities can interfere even when no…

8 thms4 active usersReviewed
🏆Completed
CombinatoricsLinear algebra·Captain: mikedeng1

Quick Approximation to Matrices and Applications I: Every Real Matrix Is a Sum of at Most 1/ε² Cut Matrices plus an Error W with |W(S,T)| ≤ ε√(|S||T|)‖A‖_FResearch Paper

Many dense combinatorial optimization problems (Max-Cut, graph bisection, quadratic assignment on dense instances) have objective functions that are sums of matrix entries over rectangles S×TS\times TS×T. If a matrix can be replaced by a simple surrogate that agrees with it on every rectangle up to a small error, such problems can be solved approximately on the…

5 thms4 active usersReviewed
🏆Completed
Computational GeometryDiscrete Geometry·Captain: mikedeng1

An Optimal Algorithm for Approximate Nearest Neighbor Searching in Fixed Dimensions: Priority Search in a BBD-Tree Visits at Most ⌈1 + 6d/ε⌉^d Leaf CellsResearch Paper

Nearest neighbor searching asks for a data structure that stores nnn points S⊂RdS\subset\mathbb R^dS⊂Rd and, given a query point qqq, returns a point of SSS closest to qqq. It underlies classification, vector quantization, data compression, pattern recognition and similarity search in databases. In dimension d≥3d\ge 3d≥3, exact methods either use space growing like …

8 thms4 active usersReviewed
🏆Completed
CombinatoricsMachine LearningOperations Research·Captain: mikedeng1

The Weighted Majority Algorithm 7: On a Class Shattered by Its Domain, Every Deterministic Learner's Mistake Bounds Satisfy Σ 2^(−M_i) < 2Research Paper

An online learner predicts a binary label for each instance before seeing that instance's correct label. Its guarantee is usually measured by its worst possible number of mistakes against a target function. Such guarantees can differ greatly across target functions: an algorithm might learn one target quickly while taking much longer on another. Littlestone…

5 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear Optimization+1·Captain: mikedeng1

The Geometry of Graphs and Some of Its Algorithmic Applications 1: Every Multicommodity Flow Network with k Source-Sink Pairs Has a Cut S with Cap(S)/Dem(S) ≤ O(log k) · maxflowResearch Paper

Routing several commodities through one capacitated network at the same time is a basic problem of network optimization, with applications to communication networks, VLSI layout and divide-and-conquer graph algorithms. Its optimum is the value of a linear program, but the natural certificates of an upper bound are combinatorial: every cut of the network…

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

An Optimal Algorithm for On-line Bipartite Matching 1: RANKING Finds a Matching of Expected Size at Least n(1 − 1/e) − o(n) on Every Graph with a Perfect MatchingResearch Paper

Online matching describes allocation when requests must be answered as they arrive. A matching decision uses only the edges revealed so far and cannot be revised when later requests appear. In the bipartite setting studied by Karp, U. Vazirani, and V. Vazirani, the arriving vertices are girls and the possible partners are boys. Even when the full graph has…

10 thms4 active usersReviewed
🏆Completed
Captain: wurtle

Subset Sum is NP-completeResearch Paper

Prove that subset sum is NP-complete by reducing the existing 3-SAT language, to it. Given a list of positive integers and a nonnegative target, decide whether some selection of entries sums exactly to the target. Integers are encoded in binary.

26 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryLinear algebra·Captain: mikedeng1

Explicit Expanders of Every Degree and Size 2: Attaching New Vertices to a (p+1)-Regular Ramanujan Graph and Adding Loops Keeps Every Nontrivial Eigenvalue at Most √(2(p+1)) + √p + o(1)Research Paper

Sparse graphs whose adjacency spectrum is concentrated near zero, expanders, are used throughout theoretical computer science: in error-correcting codes, derandomization, sorting and routing networks, and the construction of pseudorandom objects (Hoory, Linial and Wigderson, survey). The best possible spectral expansion for a ddd-regular graph is governed by…

9 thms4 active usersReviewed
🏆Completed
Captain: wurtle

k-SAT is NP-HardResearch Paper

Prove that kkk-SAT is NP-complete for every fixed k≥3k\ge3k≥3, with at most kkk literal occurrences per clause.

16 thms4 active usersReviewed
🏆Completed
Machine LearningQuantum Information·Captain: mikedeng1

Shadow Tomography of Quantum States 1: Polylogarithmically Many Copies Suffice to Estimate Every Acceptance Probability to Within εResearch Paper

Learning an unknown quantum state is expensive. Full quantum state tomography of a DDD-dimensional mixed state ρ\rhoρ to accuracy ε\varepsilonε in trace distance needs on the order of D2/ε2D^2/\varepsilon^2D2/ε2 copies of ρ\rhoρ (O'Donnell–Wright 2016; Haah et al. 2017), and this is optimal. For a system of nnn qubits, D=2nD = 2^nD=2n, so full tomography is out of reach beyond a few…

17 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: mikedeng1

Real-Time Optimization of Personalized Assortments: Inventory Balancing Is α_cmin(Ψ)-CompetitiveResearch Paper

Online retailers choose, customer by customer, which products to display. The customer's type (location, history, device) is revealed on arrival. Inventories are finite and are not replenished during the selling season. A seller who shows every customer the currently most profitable products can sell out a product early and leave nothing for later customers…

14 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

A Dynamic Near-Optimal Algorithm for Online Linear Programming II: A Lower Bound for Every Online AlgorithmResearch Paper

Online linear programming models resource allocation under uncertainty about future demand: requests arrive one at a time, each asking for some amounts of mmm resources and offering a payment, and each must be accepted or rejected, irrevocably, on arrival. Airline seat and hotel room revenue management, online routing with bandwidth limits and the allocation…

7 thms4 active usersReviewed
🏆Completed
Machine LearningOperations ResearchProbability·Captain: mikedeng1

Competitive Caching with Machine Learned Advice: The Competitive Ratio of Predictive MarkerResearch Paper

Caching (online paging) is one of the oldest problems in online algorithms: a fast memory of kkk slots serves a sequence of requests, and every request for an element not in the fast memory is a cache miss that forces the element to be loaded, possibly evicting another one. With the whole request sequence known in advance, evicting the element whose next…

10 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability·Captain: mikedeng1

Competitive Randomized Algorithms for Nonuniform Problems IV: The Optimal Randomized Two-Server Ratio 1652/1069 on the 3-4-5 TriangleResearch Paper

The kkk-server problem is a basic model of on-line decision making. kkk mobile servers move in a metric space, requests for points arrive one at a time, and each request has to be covered by a server before the next one arrives. The cost is the total distance the servers move. The problem includes paging, caching and disk-head scheduling as special cases (Manass…

7 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchProbability·Captain: mikedeng1

Competitive Randomized Algorithms for Nonuniform Problems I: Optimal Competitiveness of Randomized Block Snoopy CachingResearch Paper

In a shared-memory multiprocessor, each processor keeps copies of memory blocks in its own cache, and all caches listen ("snoop") on a common bus. Every bus cycle spent keeping these copies consistent is a cycle not available for useful work, so the protocol that decides when a block is shared by several caches and when it is private to one cache directly…

8 thms4 active usersReviewed
PreviousPage 11 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