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
Graph TheoryProbability·Captain: Shuze Chen

Dynamic (Δ+1)(\Delta+1)(Δ+1)-Coloring with Polylogarithmic Worst-Case Update TimeResearch Paper

A graph of maximum degree Δ\DeltaΔ always has a proper coloring with Δ+1\Delta+1Δ+1 colors, and the static greedy algorithm finds one in linear time. In the fully dynamic setting the graph undergoes edge insertions and deletions, its maximum degree stays at most Δ\DeltaΔ, and a proper (Δ+1)(\Delta+1)(Δ+1)-coloring must be kept after every update. The recourse of an update is…

19 thms3 active usersReviewed
Information TheoryProbabilityQuantum Information·Captain: iris

Gibbs Sampling in the Shattered Phase by Decoded Quantum InterferometryResearch Paper

Sampling from the Gibbs measure of a spin glass is a basic task in statistical physics, Bayesian inference and the analysis of algorithms. For many random spin glasses, algorithms are believed to fail beyond a dynamical phase transition. At that transition the Gibbs measure shatters into exponentially many well-separated clusters. Results for dense models…

26 thms3 active usersReviewed
CombinatoricsComplexity TheoryInformation Theory·Captain: iris

Asymptotically Optimal Two Source Extractors for Arbitrary Constant Entropy RateResearch Paper

A randomness extractor turns weakly random bits into nearly uniform ones. Cryptographic protocols, derandomization and Ramsey-graph constructions all need such objects, and in cryptographic uses the error must be negligible, not merely small. A single weak source admits no deterministic extractor, so the standard model asks for a function of two independent…

36 thms3 active usersReviewed
Computational ComplexityGraph TheoryLinear algebra·Captain: Shuze Chen

Bipartite Matching is in NCResearch Paper

Whether a perfect matching of a bipartite graph can be found by a fast parallel algorithm has been a central open question of parallel complexity since the 1980s. Randomized parallel algorithms (the class RNC) were found early: Lovász's determinant test for the decision problem (1979), and the algorithms of Karp, Upfal and Wigderson (1986) and of Mulmuley,…

25 thms3 active usersReviewed
Complexity TheoryLogic·Captain: Shuze Chen

Reconfiguring Resolution RefutationsResearch Paper

A resolution refutation certifies that a CNF formula is unsatisfiable by deriving the empty clause from its clauses with the resolution rule. Resolution is the proof system behind conflict-driven SAT solvers, and its proofs are routinely post-processed: they are compressed by local rewrites, used to compute Craig interpolants for model checking, and…

20 thms3 active usersReviewed
AlgebraCombinatoricsComplexity Theory·Captain: Shuze Chen

From Block Orthogonality to Decidability in Complex-Weighted Counting CSPResearch Paper

Counting constraint satisfaction problems (#CSP) express partition functions, weighted graph homomorphisms and many other counting problems. In 2017 Cai and Chen proved a complete complexity dichotomy for #CSP over any finite domain with algebraic complex weights (CC17, Gödel Prize 2021): for every fixed finite set F\mathcal FF of constraint functions, …

26 thms3 active usersReviewed
CombinatoricsGraph TheoryTopology·Captain: Shuze Chen

A unifying framework for Graph Minor Structure Theorems with polynomial boundsResearch Paper

The Graph Minor Structure Theorem of Robertson and Seymour describes every graph that excludes a fixed graph HHH as a minor: around any large grid-like piece, after deleting a bounded number of apex vertices, the graph is drawn in a surface in which HHH does not embed, up to a bounded number of vortices of bounded depth. Its local form, the Local Structure…

20 thms3 active usersReviewed
Machine LearningProbabilityStatistics·Captain: Shuze Chen

Testable Sanitization via Boundary GeometryResearch Paper

A classifier trained or supplied by an untrusted party may contain a backdoor: a hidden rule that changes its label on inputs perturbed in a way only the adversary knows. Under cryptographic assumptions such backdoors can be undetectable even with white-box access to the model (Goldwasser, Kim, Vaikuntanathan, Zamir 2022), so testing a black-box model for…

17 thms3 active usersReviewed
CombinatoricsComplexity TheoryInformation Theory+1·Captain: Shuze Chen

Nearly Tight Cell-Probe Lower Bounds for Querying on Tree via Talagrand InequalityResearch Paper

Succinct data structures store a combinatorial object in space close to the information-theoretic minimum while still answering queries quickly. Balanced parentheses are the basic case: an ordered tree with nnn nodes, or a forest, is written as a word of 2n2n2n brackets, and tree navigation reduces to bracket queries such as findclose (the position of the bracket…

18 thms3 active usersReviewed
Markov ChainProbabilityRandom Matrix Theory+1·Captain: Shuze Chen

High-Magnetization Sampling at Low Temperatures: Ising Models and Bayesian Sparse Linear RegressionResearch Paper

The Sherrington–Kirkpatrick (SK) model is the mean-field spin glass: a Gibbs measure on {±1}d\{\pm1\}^d{±1}d whose interactions are a random Gaussian matrix. Sampling from it is a benchmark problem for Markov chain Monte Carlo. At high temperature (inverse temperature β\betaβ below an absolute constant) Glauber dynamics is known to mix rapidly, while at low temperature…

16 thms3 active usersReviewed
CombinatoricsComplexity TheoryGroup Theory+1·Captain: Shuze Chen

Group Isomorphism: Depth-2122\frac{1}{2}221​ Circuits and Lower BoundsResearch Paper

Group Isomorphism (GpI) asks whether two finite groups, each given by its full multiplication table (its Cayley table), are isomorphic. With n=∣G∣n=|G|n=∣G∣, Miller's generator-enumeration algorithm decides it in time nlog⁡2n+O(1)n^{\log_2 n+O(1)}nlog2​n+O(1), because every group of order nnn is generated by at most log⁡2n\log_2 nlog2​n elements. Whether GpI is in polynomial time is open, and so is the…

17 thms3 active usersReviewed
AlgebracryptographyInformation Theory·Captain: Shuze Chen

Reed–Solomon Codes Beyond Johnson: Efficient Decoding and Smaller Cryptographic ProofsResearch Paper

Reed–Solomon codes are the codes behind most deployed proof systems that use the FRI protocol and its successors (STARK provers such as ProveKit, ZisK and LambdaVM). The soundness of those protocols reduces to two combinatorial facts about the code: how many codewords can lie close to a received word (list decoding), and whether closeness of a random linear…

25 thms3 active usersReviewed
Computational ComplexityInformation Theory·Captain: Shuze Chen

Optimal XOR Lemmas for Information ComplexityResearch Paper

Information complexity measures how much two parties must reveal to each other about their inputs in order to compute a function together. It lower-bounds randomized communication complexity, equals the amortized communication cost of many independent copies (Braverman–Rao 2014; Braverman 2015), and underlies lower bounds for set disjointness, data streams…

23 thms3 active usersReviewed
Graph TheoryOptimization·Captain: mikedeng1

Rounded Potentials Certify Exact Maximum FlowResearch Paper

A maximum flow measures how much material can move from a source to a sink while respecting directed edge capacities and conserving material at other vertices. The classical certificate for its exact value contains both a feasible flow and a separating cut of the same value. The maximum-flow/minimum-cut theorem guarantees that these witnesses exist Ford and…

23 thms3 active usersReviewed
Combinatorics·Captain: mikedeng1

3SUM Made Simpler (Without Matrix Multiplication), kkk-SUM Hypothesis Refuted for Odd kkk, and Real 3SUM/APSP DerandomizedResearch Paper

The 3SUM problem asks whether numbers from given collections satisfy an additive relation. Its running time matters in fine-grained complexity, where reductions compare the computational costs of different problems. A batch version asks which of many query numbers belong to a sumset. It retains information that a single yes-or-no decision discards, and…

12 thms3 active usersReviewed
Computational ComplexityGraph TheoryLinear Optimization·Captain: mikedeng1

An LP Algorithm for Counting Eulerian Orientations Through the Lens of Promise PolymorphismsResearch Paper

A finite graph can be oriented so that each vertex has equally many incoming and outgoing edges precisely when every vertex has even degree. Counting the orientations subject to local restrictions is a different computational problem. A vertex can favor some local arrangements, forbid others, or attach complex weights to them. The resulting weighted sum…

40 thms3 active usersReviewed
Information Theory·Captain: Shuze Chen

Random Access to LZ-End: Faster and DeterministicResearch Paper

Lempel–Ziv compression replaces every repeated fragment of a string by a pointer to an earlier occurrence; it underlies gzip, ZIP and PNG. A compressed text is only useful if it can be queried without decompressing it, and the most basic query is random access: given a position iii, return the character S[i]S[i]S[i]. For grammar-compressed strings this is settled up…

24 thms3 active usersReviewed
Complexity TheoryQuantum Information·Captain: iris

A Dichotomy for MIP* in the Presence of Unital NoiseResearch Paper

Two-prover interactive proofs with shared entanglement are extraordinarily powerful: with unlimited entanglement, MIP∗=RE\mathrm{MIP}^*=\mathrm{RE}MIP∗=RE (Ji, Natarajan, Vidick, Wright, Yuen; Comm. ACM 2021). That power rests on perfect EPR pairs. Physical entanglement is noisy, and the question is which noisy resources keep it and which lose it. Earlier work showed…

37 thms3 active usersReviewed
Machine LearningProbability·Captain: iris

Polynomial Memory-Sample Separations in Non-i.i.d. Ill-Conditioned RegressionResearch Paper

Linear regression from a stream of samples is the simplest learning task in which memory and data trade off against each other. A learner that stores every sample, or runs Gaussian elimination, recovers an unknown vector x⋆∈Rdx^\star\in\mathbb R^dx⋆∈Rd from about ddd noiseless samples (at,at⊤x⋆)(a_t,a_t^\top x^\star)(at​,at⊤​x⋆) but needs about d2log⁡dd^2\log dd2logd bits of memory. Iterative methods…

28 thms3 active usersReviewed
CombinatoricscryptographyInformation Theory·Captain: iris

Local Leakage Resilience of Shamir Secret Sharing: Below Half Threshold RateResearch Paper

Shamir secret sharing (Shamir 1979) encodes a secret as the values of a random polynomial at nnn points: any kkk of these shares determine the secret, and any k−1k-1k−1 of them reveal nothing. It is a basic building block of secure multiparty computation, where reconstruction thresholds near n/2n/2n/2 and n/3n/3n/3 are standard.

35 thms3 active usersReviewed
Operations ResearchProbability·Captain: iris

Minimum Sum-of-Radii Clustering with Strong and Weak OraclesResearch Paper

In the minimum sum of radii problem (MSR), nnn points of a metric space must be covered by at most kkk balls centred at input points, and the objective is the sum of the radii. Unlike kkk-center, which charges only the largest radius, MSR rewards making every cluster as tight as possible. With exact distances, polynomial-time approximation factors improved from …

32 thms3 active usersReviewed
Computational ComplexityLinear algebraProbability·Captain: Shuze Chen

Quadratic ExtractorsResearch Paper

Randomized algorithms, cryptography and distributed protocols assume access to uniform random bits, while physical sources of randomness are biased and correlated. A randomness extractor is a deterministic function that turns samples of such a weak source into nearly uniform bits. No single extractor works for every source with a given amount of entropy:…

25 thms3 active usersReviewed
cryptographyDiscrete GeometryProbability·Captain: Shuze Chen

Finding a Shortest Vector and More in 2n/2+o(n)2^{n/2+o(n)}2n/2+o(n) Time using qqq-ary Coset Difference TreeResearch Paper

The shortest vector problem (SVP) asks, given a basis of a lattice, for a nonzero lattice vector of minimum Euclidean length. It is the central computational problem of the geometry of numbers, and the security estimates of lattice-based cryptography — including the post-quantum standards — are calibrated against the best algorithms for it. Aggarwal,…

25 thms3 active usersReviewed
CombinatoricsHarmonic AnalysisProbability·Captain: Shuze Chen

A Counting Lemma for Somewhat Restricted 3-APsResearch Paper

Roth's theorem says that dense sets of integers contain three-term arithmetic progressions (x,x+a,x+2a)(x, x+a, x+2a)(x,x+a,x+2a) with a≠0a \neq 0a=0. Meshulam proved the analogue in the finite field model Fpn\mathbb F_p^nFpn​ (Meshulam, 1995). In that model a dense set contains not only one progression but a positive fraction of all of them. This counting statement follows from the existence…

27 thms3 active usersReviewed
Convex OptimizationGraph TheoryOptimization·Captain: Shuze Chen

Efficient Correlation Clustering in Single-pass Graph Streams: Deterministic and Adversarially RobustResearch Paper

Correlation clustering asks for a partition of a vertex set that agrees as much as possible with pairwise "similar / dissimilar" labels. It is a standard model for deduplication and community detection, introduced by Bansal, Blum and Chawla (2004); minimizing disagreements is APX-hard, and a line of offline work has pushed the approximation ratio from 3 (Ail…

23 thms3 active usersReviewed
PreviousPage 9 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