Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Collections

The TCS Formalization Drive

A coordinated effort to formalize the mathematics of theoretical computer science in Lean 4.

Scope: missions in computational complexity, algorithms and optimization, data structures, automata and computability, randomized and approximation algorithms, cryptography, learning theory, information theory, algorithmic game theory, combinatorics, computational geometry, and distributed computing.

582 missions

Missions

226–250 of 582
Open91Completed491All582
🏆Completed
CombinatoricsOperations ResearchProbability+1·Captain: mikedeng1

Matroid Prophet Inequalities 2: On an Intersection of p Matroids, the Summed-Threshold Algorithm Earns at Least 1/(4p−2) of the Expected OptimumResearch Paper

A prophet inequality compares a gambler who sees independent random rewards one at a time, and must accept or reject each on arrival, with a prophet who sees all rewards in advance. The classical inequality of Krengel, Sucheston and Garling (1977–78, as cited in the paper) says that when only one reward may be kept, a single threshold rule earns at least…

12 thms3 active usersReviewed
🏆Completed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: mikedeng1

Distributed Verification and Hardness of Distributed Approximation: Simulation Theorem — Time R < (dᵖ−1)/2 on G(Γ,d,p) with B-Bit Messages Gives an ε-Error Two-Party Protocol with 2dpB·R BitsResearch Paper

In distributed computing, many graph problems (minimum spanning tree, shortest paths, connectivity checks) are solved by processors that sit at the vertices of the input network and communicate only along its edges. When every edge can carry only a few bits per round, the number of rounds an algorithm needs can be far larger than the network's diameter.…

8 thms3 active usersReviewed
Harmonic AnalysisProbabilityTheoretical Computer Science·Captain: mikedeng1

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? 3: Low-Influence Functions Have Level-One Fourier Weight at Most 2/π + CδResearch Paper

Fourier analysis of functions on the discrete cube {−1,1}n\{-1,1\}^n{−1,1}n is the main tool behind tight inapproximability results under the Unique Games Conjecture. In the MAX-CUT reduction of Khot, Kindler, Mossel and O'Donnell (SIAM J. Comput. 2007), soundness rests on the Majority Is Stablest theorem: among bounded functions in which no coordinate has large…

7 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear algebraTheoretical Computer Science·Captain: mikedeng1

Spectral Sparsification of Graphs 3: Sparsifying the Contraction and Pulling It Back Approximates a Graph with Heavy Intra-Part Edges to Within (1+ε)(1+1/c)²Research Paper

A spectral sparsifier of a weighted graph GGG is a graph G~\widetilde GG on the same vertices, with few edges, whose Laplacian quadratic form is within a factor σ\sigmaσ of that of GGG on every vector. Spielman and Teng introduced the notion in their work on nearly-linear-time solvers for symmetric diagonally dominant linear systems (Spielman–Teng 2004; arXiv:0808.41…

12 thms3 active usersReviewed
🏆Completed
AlgebraGroup TheoryTheoretical Computer Science·Captain: mikedeng1

New Techniques for Noninteractive Zero-Knowledge 4: The Decisional-Linear Commitment Is Perfectly Binding and Extractable, with a Perfectly Sound, Witness-Indistinguishable 0/1 ProofResearch Paper

A non-interactive zero-knowledge (NIZK) proof lets a prover convince a verifier that a statement is true by sending a single message, without revealing why it is true. Groth, Ostrovsky and Sahai (J. ACM 59(3), 2012) gave NIZK proofs for Circuit SAT of size O(∣C∣k)O(|C|k)O(∣C∣k) for a circuit CCC and security parameter kkk, the first perfect NIZK arguments for all of NP, and…

13 thms3 active usersReviewed
🏆Completed
Group TheoryNumber TheoryTheoretical Computer Science·Captain: mikedeng1

New Techniques for Noninteractive Zero-Knowledge 3: The Subgroup-Decision (BGN) Commitment Is Perfectly Binding and Extractable, with a Perfectly Sound, Witness-Indistinguishable 0/1 ProofResearch Paper

A non-interactive zero-knowledge (NIZK) proof lets a prover convince a verifier that a statement is true by sending a single message, without revealing why it is true. NIZK proofs are a basic building block of public-key cryptography: chosen-ciphertext secure encryption, signature schemes and secure multi-party computation all use them. Groth, Ostrovsky and…

13 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear algebraProbability+1·Captain: mikedeng1

Spectral Sparsification of Graphs 1: Sampling Each Edge of a High-Conductance Graph with Probability min(1, Υ/min(dᵢ, dⱼ)) Gives a (1+ε)-Spectral Approximation with Few EdgesResearch Paper

A spectral sparsifier of a graph is a much sparser weighted graph whose Laplacian quadratic form is within a factor σ\sigmaσ of the original on every vector. Spielman and Teng introduced the notion in Spectral Sparsification of Graphs as a strengthening of the cut sparsifiers of Benczúr and Karger: a spectral sparsifier preserves every cut, and in addition…

13 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchTheoretical Computer Science·Captain: mikedeng1

AdWords and Generalized On-line Matching I: The Tradeoff Algorithm with ψ_k(i) = Σ_{j≥i} y*_j Is (1 − 1/e)-Competitive as k → ∞ When Bids Are SmallResearch Paper

Search engines sell advertising space query by query. Each advertiser states a bid for each keyword and a daily budget; queries arrive one at a time, and each must be assigned to an advertiser immediately, without knowledge of the queries still to come. The revenue-maximizing assignment of the day can only be computed offline. The adwords problem asks how…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Hardness of Approximating Flow and Job Shop Scheduling Problems 1: Every Schedule of the Flow Shop Instance F(r,d) Has Makespan at Least min(r, d/4)·lbResearch Paper

In shop scheduling, jobs consist of chains of operations, each to be processed on a prescribed machine, and the goal is to minimize the makespan, the time at which the last operation finishes. Almost every approximation algorithm for job shops, acyclic job shops and flow shops is analysed against one quantity: the trivial lower bound lb=max⁡(C,D)\mathrm{lb}=\max(C,D)lb=max(C,D),…

8 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: mikedeng1

Spectral Sparsification of Graphs 2: Every Graph with m Edges Has a (6 log_{4/3} 2m)⁻¹-Conductance Decomposition Cutting at Most Half of Its EdgesResearch Paper

A sparse graph that approximates a dense one, in the sense that both have nearly the same Laplacian quadratic form, can stand in for it in every algorithm that only reads cuts or solves Laplacian linear systems. Spielman and Teng introduced such spectral sparsifiers and built them in nearly linear time; the construction is the sparsification step of their…

10 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear algebraProbability+2·Captain: mikedeng1

Graph Sparsification by Effective Resistances 1: Sampling O(n log n/ε²) Edges by Effective Resistance Yields a (1±ε) Spectral Sparsifier with Probability 1/2Research Paper

Many graph algorithms run in time proportional to the number of edges. A sparsifier of a weighted graph GGG is a graph HHH on the same vertices with far fewer edges that approximates GGG for the purpose at hand, so that the algorithm can be run on HHH instead. Benczúr and Karger (1996) showed that every graph has a sparsifier with O(nlog⁡n/ε2)O(n\log n/\varepsilon^2)O(nlogn/ε2) edges…

9 thms3 active usersReviewed
Quantum InformationTheoretical Computer Science·Captain: mikedeng1

Search via Quantum Walk 1: Recursive Amplitude Amplification with Approximate Reflections R(βᵢ), βᵢ = 18γ/(4π³i²), Finds a Marked Element with Probability at Least 1/12 − 3γResearch Paper

Grover's algorithm finds a marked element among NNN with O(N)O(\sqrt N)O(N​) queries by alternating two reflections: one about the initial state and one that flips the sign of marked states. In quantum-walk search, the initial state ∣π⟩|\pi\rangle∣π⟩ encodes the stationary distribution of a Markov chain, and the reflection about ∣π⟩|\pi\rangle∣π⟩ is too expensive to implement…

14 thms3 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: wurtle

Snaky in 21 Maker movesResearch Paper

In a Maker–Breaker achievement game, two players alternately claim cells of a board; Maker wins by owning every cell of some copy of a fixed shape, and Breaker only tries to prevent this. Polyomino achievement games on the infinite square grid, introduced by Frank Harary, ask which small polyominoes are winners (Maker can force a copy) and which are losers (…

33 thms3 active usersReviewed
🏆Completed
CombinatoricsMarkov ChainTheoretical Computer Science·Captain: wurtle

Approximate counting of common bases of two matroidsResearch Paper

A matroid abstracts linear independence: a finite ground set with a family of "independent" subsets that is closed under subsets and satisfies the augmentation axiom. Its maximal independent sets, the bases, all have the same size, the rank. Matroid intersection, finding a common basis of two matroids, is one of the central polynomially solvable problems of…

70 thms3 active usersReviewed
🏆Completed
Complexity TheoryMachine LearningProbability+1·Captain: mikedeng1

What Can We Learn Privately? V: Masked Parity Is Learnable by Adaptive but Not by Nonadaptive Statistical Queries Under the Uniform DistributionResearch Paper

In the local model of differential privacy, each individual randomizes their own data before handing it to an untrusted learner. Local protocols are the deployed form of private data collection, and in practice every round of interaction with the population is expensive: the learner must broadcast new instructions and wait for new reports. Kasiviswanathan,…

11 thms3 active usersReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: mikedeng1

What Can We Learn Privately? IV: Any ε-Local Algorithm Is Simulated by a Statistical Query Algorithm with O(t·e^ε) Expected Queries up to Statistical Difference βResearch Paper

In the local model of differential privacy, no trusted curator holds the data: each individual randomizes their own record before handing it to the analyst. This is the model of randomized response in survey statistics and of the privacy-preserving telemetry deployed by large software vendors. Kasiviswanathan, Lee, Nissim, Raskhodnikova and Smith, What Can…

9 thms3 active usersReviewed
🏆Completed
Formal VerificationMathematical LogicTheoretical Computer Science·Captain: mikedeng1

Compositional Shape Analysis by Means of Bi-Abduction 1: The Best Abductive Solution for Points-To Symbolic Heaps Is a Computable Disjunction of Symbolic HeapsResearch Paper

Automatic verification of programs that manipulate pointers needs procedure specifications: preconditions saying which part of the heap a procedure touches and postconditions saying what it leaves behind. Writing them by hand does not scale to millions of lines of code. Calcagno, Distefano, O'Hearn and Yang (J. ACM 58(6), 2011) infer them compositionally…

13 thms3 active usersReviewed
🏆Completed
Complexity TheoryOperations ResearchOptimization+1·Captain: mikedeng1

Convex Quadratic and Semidefinite Programming Relaxations in Scheduling V: 3-Occurrence Max3Sat L-Reduces to R | rⱼ | Σ Cⱼ with Constants 32 and 1Research Paper

The scheduling problem R ∣ rj ∣∑CjR\,|\,r_j\,|\sum C_jR∣rj​∣∑Cj​ asks for a nonpreemptive schedule of jobs on unrelated parallel machines, each job with a machine-dependent processing time and a release date, so that the total completion time is minimal. It is NP-hard, and the question that remains is how well it can be approximated in polynomial time. Positive results include…

7 thms3 active usersReviewed
🏆Completed
AnalysisProbabilityTheoretical Computer Science·Captain: mikedeng1

On Lattices, Learning with Errors, Random Linear Codes, and Cryptography 3: The Periodic Gaussians Ψ_α and Ψ_β Are Within Statistical Distance 9(β/α − 1) When 0 < α < β ≤ 2αResearch Paper

The Learning with Errors (LWE) problem, introduced by Regev in On Lattices, Learning with Errors, Random Linear Codes, and Cryptography (J. ACM 56(6), 2009, Article 34; doi:10.1145/1568318.1568324), asks to recover a secret vector s∈Zpns \in \mathbb{Z}_p^ns∈Zpn​ from noisy inner products ⟨a,s⟩/p+e mod 1\langle a, s\rangle/p + e \bmod 1⟨a,s⟩/p+emod1. The noise eee is drawn from a periodic normal…

7 thms3 active usersReviewed
🏆Completed
Machine LearningOperations ResearchTheoretical Computer Science·Captain: mikedeng1

The Weighted Majority Algorithm 4: The Continuous Master WMC Has Total Absolute Loss at Most ln(w_init/w_fin)/(1−β)Research Paper

In sequential prediction, several forecasters can issue different answers for the same instance. A master algorithm must combine their advice before the true label is known. Littlestone and Warmuth's Weighted Majority framework gives worst-case guarantees for this setting: the instances and labels need not come from a probability distribution. The paper…

6 thms3 active usersReviewed
🏆Completed
Complexity TheoryProbabilityQuantum Information+1·Captain: mikedeng1

Strengths and Weaknesses of Quantum Computing II: Relative to a Random Permutation, a Quantum Algorithm Needs Ω(2^{n/3}) Queries to Decide the First Bit of A⁻¹(1ⁿ)Research Paper

An oracle lets an algorithm ask for the value of a function without giving it a description of that function. An oracle lower bound isolates how many questions are needed, even when computation between questions is unrestricted. Bennett, Bernstein, Brassard and Vazirani used this viewpoint to compare classical and quantum access to randomly chosen functions…

10 thms3 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research+1·Captain: mikedeng1

Approximation Algorithms for Scheduling Unrelated Parallel Machines 2: Enumerating Long Assignments and Rounding the LP Gives a (1 + ε)-Approximation for MakespanResearch Paper

Scheduling independent jobs on unrelated parallel machines to minimize the makespan is one of the basic NP-hard problems of scheduling theory: each job has its own processing time on each machine, with no relation between machines, and the goal is to finish all jobs as early as possible. When the number of machines is part of the input, Lenstra, Shmoys and…

10 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationTheoretical Computer Science·Captain: mikedeng1

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

Many graph problems in routing, VLSI layout and scheduling ask for a cut that separates a lot of demand while cutting little capacity. For a single commodity, the max-flow min-cut theorem of Ford and Fulkerson says that the largest flow equals the smallest cut. For several commodities sharing one network this equality fails, and the question becomes how far…

8 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear OptimizationTheoretical Computer Science·Captain: mikedeng1

Multicommodity Max-Flow Min-Cut Theorems and Their Use in Designing Approximation Algorithms II: Every Product Multicommodity Flow Problem with k Commodities Has Ω(𝒮/log k) ≤ f ≤ 𝒮Research Paper

For a single commodity, the Ford–Fulkerson theorem says that the maximum flow between two nodes equals the minimum capacity of a cut separating them. Many routing and partitioning problems involve many source–sink pairs at once, and for those the equality fails: the largest fraction of every demand that can be routed simultaneously can be strictly smaller…

8 thms3 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryProbability+1·Captain: mikedeng1

Software Protection and Simulation on Oblivious RAMs: Every Oblivious Simulation of t Steps Makes max{|y|, Ω(t log t)} AccessesResearch Paper

Programs often reveal information through the memory locations they touch, even when the contents of those locations are hidden. An oblivious RAM simulation aims to conceal this access pattern. Goldreich and Ostrovsky studied the cost of doing so for arbitrary RAM programs and showed that the access sequence itself imposes a lower bound on simulation…

7 thms3 active usersReviewed
PreviousPage 10 of 24Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1EYEyal199050737706
2FIfizzyinc313047
3MAmarwahaha643870
4MRmrfancypants6290
5DBdbenbenn546543
6KMkmehltretter82385111
7NINihal2960
8NINickrobbins952698
9SCShuze Chen224794
10SHshivm2080

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