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
Graph TheoryLinear algebra·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 Theory·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 Theory·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·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 Research·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 Research·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 Theory·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+1·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 Information·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
Algorithmic Game Theory·Captain: marwahaha

Randomized quasipolynomial-time mean-payoff gamesOpen Problem

Mean-payoff games ask which starting positions allow a player to guarantee a nonnegative long-run average reward. Binary-encoded weights make the bit cost of solving the complete winning set a central part of the question. The source manuscript presents the surrounding research claim.

6 thms3 active usersReviewed
🏆Completed
Analysis·Captain: marwahaha

Tree Constructions for the l1 Distortion of Binary Edit DistanceOpen Problem

Embedding edit distance into ℓ₁ would permit algorithms and geometric tools for that normed space. Distortion lower bounds quantify the loss any such representation must incur. The source manuscript presents the surrounding research claim.

70 thms3 active usersReviewed
🏆Completed
Combinatorics·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 Chain·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·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 LearningProbability·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 Logic·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·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
AnalysisProbability·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 Research·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·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
Combinatorics·Captain: marwahaha

3SUM in O(n^1.999074) Time on a Word RAMOpen Problem

Prove a deterministic O(n1.999074)O(n^{1.999074})O(n1.999074) algorithm for integer 3SUM in the campaign's shared word-RAM model, improving the verified 1.9991121.9991121.999112 bound.

50 thms3 active usersReviewed
🏆Completed
CombinatoricsLinear OptimizationOperations Research·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 Optimization·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 Optimization·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·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 24 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