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
Captain: marwahaha

Sensitivity ConjectureResearch Paper

Nearly every measure of Boolean function complexity was known to be equivalent — except sensitivity. Proving the conjecture unified the whole picture.

49 thms4 active usersReviewed
🏆Completed
Computational ComplexityQuantum Information·Captain: iris

Randomized query complexity can beat certificate complexityResearch Paper

Query complexity measures how many input bits an algorithm must read to evaluate a Boolean function f:{0,1}N→{0,1}f:\{0,1\}^N\to\{0,1\}f:{0,1}N→{0,1}. For total functions (defined on every input) the classical, randomized and quantum measures are polynomially related, and a large part of the field consists of pinning down the best exponents in these relations; see the survey of…

39 thms3 active usersReviewed
Computational ComplexityMachine LearningProbability·Captain: iris

Genetic Algorithms with Optimization Guided OperatorsResearch Paper

Systems such as FunSearch and AlphaEvolve search for programs and constructions by repeatedly asking a language model for new candidates, for local revisions of a stored candidate, and for combinations of several stored candidates. A. Brandenberger, I. Doron-Arad and E. Mossel (Genetic Algorithms with Optimization Guided Operators, STOC 2027 submission; an…

26 thms3 active usersReviewed
Dynamic ProgrammingOperations ResearchOptimization·Captain: mikedeng1

Compressing the Lawler-Moore Dynamic Program for Weighted Tardy JobsResearch Paper

A production planner may have many jobs competing for a small number of identical machines. Each job has a processing requirement, a due date and a penalty for missing that date. Minimizing the sum of those penalties is the weighted tardy jobs problem. Its numerical parameters matter for exact optimization: a dynamic program can depend on the largest due…

18 thms3 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Linear-Space Exact Distance Oracle for Minor-Free GraphsResearch Paper

A distance oracle preprocesses a weighted graph so that later queries can ask for the shortest distance between two vertices. Storing every answer takes quadratic space. Storing only the input uses linear space on sparse graphs, but computing a shortest path from scratch can take almost linear time for each query. The question addressed here is whether the…

10 thms3 active usersReviewed
CombinatoricsOperations Research·Captain: mikedeng1

Faster Approximation Schemes for Scheduling on Related MachinesResearch Paper

In makespan minimization on uniformly related machines, Qm∥Cmax⁡Qm\|C_{\max}Qm∥Cmax​, each of nnn jobs is assigned to one of mmm machines that differ only in speed, and the goal is to minimize the time at which the most loaded machine finishes. The problem is strongly NP-hard when mmm is part of the input, already for identical machines (Garey–Johnson 1978), so a fully…

28 thms3 active usersReviewed
Combinatoricscryptography·Captain: mikedeng1

Nearly Optimal Information-Theoretic PIR with Client PreprocessingResearch Paper

Private information retrieval (PIR) lets a client read one bit D[i]D[i]D[i] of a database held by a server without revealing iii. With a single server and no preprocessing, PIR has two costs that cannot be avoided: it requires public-key cryptography, and the server must read the whole database on every query, so its work is Ω(n)\Omega(n)Ω(n) (Beimel–Ishai–Malkin 2000). In…

27 thms3 active usersReviewed
CombinatoricsGraph TheoryProbability·Captain: mikedeng1

Constant-Time Dynamic Edge Coloring via Dynamic Splitting and LLLResearch Paper

Vizing's theorem gives every simple graph of maximum degree Δ\DeltaΔ a proper edge colouring with Δ+1\Delta+1Δ+1 colours. Maintaining such a colouring while edges are inserted and deleted is much harder: no dynamic algorithm for (Δ+1)(\Delta+1)(Δ+1) colours with subpolynomial update time is known, except for low-degree graphs. With slightly more colours, (1+ϵ)Δ(1+\epsilon)\Delta(1+ϵ)Δ,…

26 thms3 active usersReviewed
cryptographyQuantum Information·Captain: iris

Robust and Leakage-Resilient Device-Independent Oblivious Transfer in MiniQCryptResearch Paper

Oblivious transfer (OT) lets a sender holding two bits (S0,S1)(S_0,S_1)(S0​,S1​) deliver SdS_dSd​ to a receiver who picks ddd. The sender learns nothing about ddd, and the receiver learns nothing about S1−dS_{1-d}S1−d​. OT is complete for two-party secure computation. Quantumly, OT can be built from one-way functions alone, the setting called MiniQCrypt, but those constructions trust the…

38 thms3 active usersReviewed
cryptographyQuantum Information·Captain: iris

Quantum Fire with Delegated CloningResearch Paper

The no-cloning theorem forbids copying an unknown quantum state, and quantum money and copy-protection are built on that restriction. Quantum fire (Nehoran–Zhandry, ITCS 2024) inverts it: a family of states that anyone can clone, but that cannot be telegraphed, i.e. sent over a classical channel and rebuilt at the other end. Çakan, Goyal and Shmueli (ÇGS26)…

50 thms3 active usersReviewed
cryptographyQuantum Information·Captain: iris

Breaking the Bounded Entanglement Barrier for Quantum Position VerificationResearch Paper

Quantum position verification (QPV) asks whether a prover can convince distant verifiers that it sits at a claimed location xxx, using only the fact that signals travel no faster than light. Unconditionally secure QPV is impossible: coalitions of adversaries that share enough entanglement can simulate any honest prover (Buhrman et al., SIAM J. Comput. 2014).…

36 thms3 active usersReviewed
Complexity TheorycryptographyQuantum Information·Captain: iris

Four-Message Arguments for NP∘batchQMA\mathsf{NP} \circ \mathsf{batchQMA}NP∘batchQMA and Six-Message Arguments for QMA from LWEResearch Paper

This mission formalizes the theorems of Goyal and Koppula, Four-Message Arguments for NP ∘ batchQMA and Six-Message Arguments for QMA from LWE (STOC 2027 submission), with the operator-requested pinned-down version of Corollary 5.15 as its goal. As printed, the corollary leaves the LWE parameters, the machine model and the honest resource informal. Every…

31 thms3 active usersReviewed
cryptographyQuantum Information·Captain: iris

How To Track Qubits Through Space and Time (Or: Sailing in a Quantum Boat)Research Paper

Quantum position verification (QPV) lets two verifiers at the ends of a line segment check that somebody answers challenges from a claimed point, using the fact that information travels no faster than light. It does not say what is at that point. Bartusek, Huang, Orshansky and Yuen ask for more: localization, a guarantee that a specified quantum object can…

27 thms3 active usersReviewed
Computational ComplexityMathematical PhysicsQuantum Information·Captain: iris

Polynomial-Time Classical and Quantum Simulation of Quantum Impurity ModelsResearch Paper

Quantum impurity models describe a small, strongly interacting system (an atom, a quantum dot, a defect) coupled to a large non-interacting fermionic reservoir. They are the original setting of the Kondo problem and of Wilson's numerical renormalization group (Wilson 1975), and they are the subproblem that embedding methods such as dynamical mean-field…

32 thms3 active usersReviewed
Machine LearningProbabilityStatistics·Captain: Shuze Chen

Posterior Sampling in Gaussian Mixture Models Beyond the Clusterability ThresholdResearch Paper

Bayesian mixture models are the standard probabilistic description of clustering: each data point carries a hidden label saying which component generated it, and the scientific object is the posterior over labels given the data. In practice the posterior is explored with Gibbs samplers and related Markov chains, which are known to get trapped between label…

21 thms3 active usersReviewed
Graph TheoryOperations ResearchProbability·Captain: Shuze Chen

First Near-Additive All-Pairs Approximate Shortest Paths in Decremental Weighted GraphsResearch Paper

All-pairs approximate shortest paths (APASP) asks for a matrix ddd with δ(u,v)≤d[u,v]≤α δ(u,v)+β\delta(u,v)\le d[u,v]\le\alpha\,\delta(u,v)+\betaδ(u,v)≤d[u,v]≤αδ(u,v)+β for every pair of vertices. Static algorithms trade the stretch (α,β)(\alpha,\beta)(α,β) against running time; the classical additive tradeoffs are due to Dor, Halperin and Zwick for unweighted graphs and to Cohen and Zwick for weighted graphs,…

17 thms3 active usersReviewed
Discrete GeometryProbability·Captain: mikedeng1

Strongly Log-Concave Measures and LatticesResearch Paper

A lattice is a discrete additive subgroup of Rn\mathbb R^nRn. Lattices are the basic objects of the geometry of numbers and of lattice-based cryptography, and many questions about them ask how "evenly spread" a lattice is: whether some sublattice is much denser than the lattice itself. Stable lattices, those of determinant one with no denser sublattice, appear…

20 thms3 active usersReviewed
Graph Theory·Captain: mikedeng1

Constructive Arboricity in Almost-Linear Time for Dense GraphsResearch Paper

Graph algorithms often need a representation of sparsity that can be used directly. A forest has no cycle, so its edges admit tree operations and simple traversal rules. A graph whose edges split into a small number of forests can be processed one forest at a time. The minimum possible number, called arboricity, measures this form of sparsity. An algorithm…

18 thms3 active usersReviewed
Computational Complexitycryptography·Captain: mikedeng1

Hardness of Unique Shortest Vectors and Bounded Distance DecodingResearch Paper

Short lattice vectors and nearby lattice points are the basic computational objects of lattice algorithms and lattice-based cryptography [MG02]. Two promises are expected to make them easier to find. In the unique shortest vector problem (uSVP), every lattice vector off the line of a shortest vector is longer by a fixed factor Γ\GammaΓ. In bounded distance…

32 thms3 active usersReviewed
Combinatorics·Captain: Shuze Chen

A Unified and Robust Theory of Lower and Upper Bounds for the √log n BarrierResearch Paper

Many basic problems on packed strings and on planar point sets have the same best known running time on the word RAM: O(mlog⁡m)O(m\sqrt{\log m})O(mlogm​), where mmm is the input size in machine words. Examples are dictionary matching on a packed text, building the Burrows–Wheeler transform (BWT) of a packed binary string, the LZ77 factorization, counting inversions in an array…

68 thms3 active usersReviewed
Computational ComplexityComputational GeometryOperations Research·Captain: Shuze Chen

Near-Optimal Makespan and Parameterized Hardness for Multi-Robot Motion PlanningResearch Paper

Moving several robots through a shared workspace without collisions is a basic problem of robotics and computational geometry. Deciding whether one arrangement of robots can be transformed into another is PSPACE-hard when the number of robots is part of the input, so attention turns to a small number kkk of robots. Known algorithms for kkk square robots in a…

25 thms3 active usersReviewed
Complexity TheorycryptographyQuantum Information·Captain: Shuze Chen

Post-Quantum Perfect Zero-Knowledge Arguments for NP From Any One-Way PermutationResearch Paper

A zero-knowledge argument lets a prover convince a verifier that a statement xxx belongs to an NP language without revealing anything beyond that fact. In the perfect variant, everything the verifier sees can be reproduced exactly by an efficient simulator that never sees the witness; soundness holds only against efficient provers, which is what "argument"…

26 thms3 active usersReviewed
Combinatorics·Captain: Shuze Chen

Dynamic Approximate Text IndexingResearch Paper

A text index preprocesses a text TTT so that, given a pattern PPP of length mmm, the occurrences of PPP in TTT can be found in time close to mmm rather than to ∣T∣|T|∣T∣. Suffix trees and suffix arrays do this for exact matching. Many applications, most prominently read alignment in bioinformatics, need approximate occurrences, where a small number kkk of differences is…

19 thms3 active usersReviewed
CombinatoricsGraph Theory·Captain: Shuze Chen

Incremental Approximate Vertex Connectivity via Almost-Linear Time Local Cut AlgorithmsResearch Paper

The vertex connectivity κ(G)\kappa(G)κ(G) of a graph is the least number of vertices whose removal disconnects it. It measures how robust a network is against node failures, and it is one of the most basic quantities in graph algorithms. For directed graphs the notion is strong connectivity: κ(G)\kappa(G)κ(G) is the least size of a set whose deletion leaves a graph that is…

23 thms3 active usersReviewed
Algorithmic Game TheoryCombinatoricsOperations Research·Captain: Shuze Chen

Structural Complexity of Matching with IndifferencesResearch Paper

Centralized school choice and other two-sided assignment systems are run by clearinghouses that announce a single outcome. When preferences contain ties (a student may be indifferent between several schools), the classical notion of stability splits into weak, strong and super stability (Irving 1994), and a deterministic rule must also say which stable…

19 thms3 active usersReviewed
PreviousPage 13 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