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
Number TheoryQuantum Information·Captain: mikedeng1

Asymptotically Optimal Topological Quantum Compiling: Every Output of the Fibonacci-Anyon Approximation Algorithm Is an ⟨F,T⟩-Circuit of Length O(log(1/ε)) Within Distance ε of Rz(φ)Research Paper

Topological quantum computing represents a gate operation by moving anyons around one another. A compiler must turn a requested single-qubit unitary into a finite braid or gate word, with enough accuracy and a length that grows slowly as the error tolerance shrinks. For Fibonacci anyons, the matrices generated by the standard elementary braids have…

8 thms3 active usersReviewed
Operations ResearchOptimization·Captain: mikedeng1

Dynamic Resource Allocation in the Cloud with Near-Optimal Efficiency: The Multiplicative Weight Algorithm Nearly Matches the Offline Dynamic Optimum's Work While Approximately Satisfying Every SLAResearch Paper

Cloud platforms divide a shared physical resource, such as a pool of processors, among many users at once. Each user is promised a service level agreement (SLA): a fraction β(i)\beta(i)β(i) of the resource that it should effectively receive whenever it has work to do. The operator wants two things that pull against each other: to keep the resource busy (total work…

29 thms3 active users
Linear algebraOptimizationQuantum Information·Captain: mikedeng1

Optimization by Decoded Quantum Interferometry 1: The Semicircle Law — the Optimal Degree-ℓ DQI State Satisfies ⟨s⟩/m → (√(μ(1−ρ)) + √(ρ(1−μ)))² When 2ℓ + 1 < d⊥Research Paper

Decoded quantum interferometry (DQI) is a quantum algorithm, introduced by Jordan, Shutty, Wootters, Zalcman, Schmidhuber, King, Isakov, Khattar and Babbush (arXiv:2408.08292), that turns an approximate optimization problem over a finite field into a decoding problem for a linear code. It applies to max-LINSAT: given linear constraints over Fp\mathbb F_pFp​,…

14 thms3 active usersReviewed
OptimizationQuantum Information·Captain: mikedeng1

A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem I: Level-One QAOA Satisfies (1/2 + 1/(101 D^(1/2) ln D))m Equations of Max E3LIN2 for Large DResearch Paper

The Quantum Approximate Optimization Algorithm (QAOA) of Farhi, Goldstone and Gutmann (arXiv:1411.4028) is a family of shallow quantum circuits for combinatorial optimization. At its lowest level, p=1p = 1p=1, the circuit has two real parameters, and its output is a random bit string. The question is how many constraints that string satisfies, compared with the…

18 thms3 active usersReviewed
Linear algebraLinear Optimization·Captain: mikedeng1

A Strongly Polynomial Algorithm for Linear Exchange Markets II: A Z₊-Matrix Polyhedron P_M Lies Between an M2VPI Polyhedron and Its Scaling by B²Research Paper

In a linear exchange market every agent owns one divisible good and has linear utilities over all goods; an equilibrium is a price vector at which every agent can spend its budget on goods that maximize utility per unit of money, and all goods are sold. Computing such an equilibrium in strongly polynomial time, with a number of arithmetic operations bounded…

11 thms3 active usersReviewed
Captain: wurtle

Two WordRAM models: equivalence with polylogarithmic overheadTextbook

Prove equivalence between two WordRAM models: one with unsigned pointers, bit operations, and shifts; the other with signed pointers and branching on sign. Both support bounded-word arithmetic and multiplication.

16 thms3 active usersReviewed
Linear algebraNumerical AnalysisProbability·Captain: mikedeng1

Low Rank Approximation and Regression in Input Sparsity Time 1: A Sparse Embedding Matrix with O((r/ε)⁴ log²(r/ε)) Rows Is a (1 ± ε) Subspace Embedding for a Rank-r Matrix with Probability 9/10Research Paper

Many matrix algorithms spend most of their time reading their input. A matrix with few nonzero entries should admit routines whose cost scales with that number, rather than with the product of its dimensions. Clarkson and Woodruff study random maps that compress a matrix before a regression or low rank approximation calculation while retaining the geometric…

9 thms3 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Twin-width I: Tractable FO Model Checking 4: Every K_t-Minor-Free Graph Has Twin-width at Most 4c_g(t)·2^(4c_g(t)+2), a Triple-Exponential Bound in tResearch Paper

Many graph classes are defined by excluding a fixed graph as a minor. A minor can be formed by deleting vertices, deleting edges, and contracting edges. Planar graphs, for example, exclude K5K_5K5​ as a minor. Édouard Bonnet, Eun Jung Kim, Stéphan Thomassé, and Rémi Watrigant proved that every class excluding a fixed clique minor has bounded twin-width, a graph…

17 thms3 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Twin-width I: Tractable FO Model Checking 3: Grid Minor Theorem for Twin-width — t-Twin-Ordered Matrices Are (2t+2)-Mixed Free, and t-Mixed Free Matrices Have Twin-width at Most 4c_t·α^(4c_t+2)Research Paper

Twin-width is a graph and matrix invariant introduced by Bonnet, Kim, Thomassé and Watrigant (J. ACM 69(1), Article 3, 2021). Classes of bounded twin-width include bounded tree-width and clique-width graphs, proper minor-closed classes, posets of bounded width, and permutations avoiding a fixed pattern; on all of them, first-order model checking is…

10 thms3 active usersReviewed
Harmonic AnalysisProbability·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
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
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
CombinatoricsGraph Theory·Captain: mikedeng1

Sorting in c log n Parallel Steps: Sorting Networks of Logarithmic DepthResearch Paper

A sorting network is a sorting procedure whose sequence of comparisons is fixed in advance, independently of the data. Its depth, the number of rounds of simultaneous comparisons on disjoint pairs, is the parallel running time. Sorting networks are used in parallel and hardware sorting, in switching networks, and in cryptography, where a data-independent…

13 thms3 active usersReviewed
CombinatoricsInformation Theory·Captain: iris

Linear codes exceeding the Gilbert–Varshamov boundResearch Paper

A binary linear code of length nnn is a subspace C⊆F2nC\subseteq\mathbb F_2^nC⊆F2n​, and its distance is the least Hamming weight of a nonzero codeword. Codes of large size and large distance are the basic objects of error correction: a code of distance ddd corrects ⌊(d−1)/2⌋\lfloor (d-1)/2\rfloor⌊(d−1)/2⌋ bit errors, and lg⁡∣C∣\lg|C|lg∣C∣ is the number of information bits it carries. The largest…

26 thms2 active usersReviewed
cryptographyProbability·Captain: iris

Signal-Routed Two-Arm Verification: Statistical Soundness and Threshold AggregationResearch Paper

A verifier of an interactive proof or succinct argument ends with one bit, but its view carries graded evidence: how many local consistency tests passed, whether the messages were well formed. A verifier that processes many statements under a budget would like to spend little effort on rounds that look clean and more on rounds that look suspicious. Any such…

16 thms2 active usersReviewed
Convex OptimizationLinear OptimizationOperations Research+1·Captain: mikedeng1

Extending Tardos's Theorem to Separable Convex Quadratic ProgrammingResearch Paper

A strongly polynomial algorithm for a class of optimization problems uses a number of arithmetic operations bounded by a polynomial in the dimensions alone, independently of how large the numbers in the input are. Whether linear programming admits such an algorithm is open (Smale's 9th problem). Tardos (1986) proved the most useful partial answer: for an…

25 thms2 active usersReviewed
Computational GeometryOperations ResearchOptimization·Captain: mikedeng1

Packing Bins in the Euclidean Plane: An Almost-Optimal Approximation for Unsplittable Capacitated Vehicle RoutingResearch Paper

The Capacitated Vehicle Routing Problem (CVRP), introduced by Dantzig and Ramser in 1959, asks for a cheapest set of delivery routes from a depot when each vehicle can carry at most QQQ units. It is a central model of logistics, and most standard benchmark sets use Euclidean distances. In the unsplittable version every client's demand must be delivered by a…

22 thms2 active usersReviewed
Computational GeometryOperations Research·Captain: mikedeng1

A Faster FPTAS for Weighted Completion Time SchedulingResearch Paper

Minimizing the total weighted completion time on parallel identical machines, written Pm∥∑wjCjPm\|\sum w_jC_jPm∥∑wj​Cj​ in three-field notation, is one of the basic objectives of scheduling theory. For a single machine, Smith's rule (1956) solves it exactly by ordering jobs by non-increasing ratio wj/pjw_j/p_jwj​/pj​. Already for m=2m=2m=2 machines the problem is NP-hard (Bruno, Coffman and…

22 thms2 active usersReviewed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

Beyond Gomory-Hu: All-Pairs ×\times× All-Pairs Mincuts in O(n)O(n)O(n) SpaceResearch Paper

Two classical representations of minimum cuts in an undirected weighted graph G=(V,E,w)G=(V,E,w)G=(V,E,w) with nnn vertices answer complementary questions. The Gomory–Hu tree (Gomory–Hu 1961) stores, in O(n)O(n)O(n) space, one minimum (x,y)(x,y)(x,y)-cut for every terminal pair x,yx,yx,y, but only one of the possibly many. The Picard–Queyranne representation (Picard–Queyranne, Math. Programming Study…

41 thms2 active usersReviewed
Complexity TheoryLinear algebra·Captain: mikedeng1

Lattice Reduction at Average PrecisionResearch Paper

Many problems in computational number theory and cryptography are solved by building an integer lattice and extracting one of its short vectors: factoring integer polynomials over the rationals, low-density subset sum, predicting truncated linear congruential generators, Coppersmith's small-root attacks, integer relations and simultaneous Diophantine…

24 thms2 active usersReviewed
Combinatorics·Captain: mikedeng1

Real-Time String Indexing in Optimal TimeResearch Paper

In the string indexing problem a text TTT is stored so that, for any query pattern PPP, all occurrences of PPP in TTT can be reported quickly. In the real-time version the text arrives as a stream, one letter at a time. Each letter must be processed in worst-case O(1)O(1)O(1) time, and at every moment a query can be asked against the portion of the text received so far.…

15 thms2 active usersReviewed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

Minimum-Cost kkk-Arborescence Packing in O~(km+k4n)\tilde O(km+k^4 n)O~(km+k4n) TimeResearch Paper

A packing of kkk arc-disjoint spanning arborescences rooted at a common vertex rrr keeps every vertex reachable from rrr after the deletion of any k−1k-1k−1 arcs. Finding such a packing of minimum total cost is a building block of approximation algorithms for network design, including minimum-cost kkk-edge-connected spanning subgraphs and flexible graph connectivity, and…

37 thms2 active usersReviewed
Complexity TheoryInformation TheoryProbability+1·Captain: mikedeng1

Four Ways to Stream: Exponential Separations from Random Order and Quantum MemoryResearch Paper

Single-pass streaming algorithms read a long input once with little memory. Quantum memory is known to help exponentially on streams whose data all comes before the questions: Boolean Hidden Matching and its relatives give a quantum advantage when the bit items precede the matching items (Gavinsky, Kempe, Kerenidis, Raz and de Wolf, SIAM J. Comput. 2008; Kal…

42 thms2 active usersReviewed
CombinatoricsGraph TheoryHarmonic Analysis·Captain: mikedeng1

Sparsest Cut on Abelian Cayley GraphsResearch Paper

The sparsest cut problem asks for a set of vertices of a graph that is poorly connected to the rest. It is NP-hard to solve exactly, and the best polynomial-time guarantee for general graphs remains the O(log⁡n)O(\sqrt{\log n})O(logn​) approximation of Arora, Rao and Vazirani (ARV09); no subexponential-time constant-factor approximation is known for general graphs. This…

17 thms2 active usersReviewed
Complexity TheorycryptographyLinear algebra·Captain: Shuze Chen

SNARGs and ABE for Uniform Computations via Lattice EncodingsResearch Paper

A succinct non-interactive argument (SNARG) lets a prover convince a verifier that a computation was carried out correctly, with a proof and a verification time much smaller than the computation itself. A line of work on lattice-based functional commitments builds SNARGs whose security rests on the short integer solution (SIS) problem, a standard…

12 thms2 active usersReviewed
PreviousPage 15 of 34Next

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