Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Probability

2,743 missions · 1,549 completed

Missions

Open1194Completed1549All2743
CombinatoricsGraph TheoryTheoretical Computer Science·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
Machine LearningStatisticsTheoretical Computer Science·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 ResearchTheoretical Computer Science·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
Graph Theory·Captain: mikedeng1

Strong Convergence for Zig-Zag Products and Typical Spectra of Irregular GraphsResearch Paper

The zig-zag product separates the number of vertices of a graph from its degree. It combines a large regular graph with a fixed small graph, called a gadget, to produce another graph of bounded degree. Spectral estimates for this construction matter in the study of expander graphs: a small nontrivial adjacency spectrum measures how strongly the graph mixes.…

41 thms3 active usersReviewed
Discrete GeometryTheoretical Computer Science·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
Quantum InformationRandom Matrix Theory·Captain: iris

Random quantum circuits beyond moment matchingResearch Paper

Random quantum circuits are the workhorse of quantum supremacy experiments, benchmarking and pseudorandomness. In a sampling experiment a unitary UUU on NNN basis states (N=2nN = 2^nN=2n for nnn qubits) is applied to a fixed input and the outcome is measured; the relevant statistics are the output probabilities ∣⟨x∣U∣y⟩∣2|\langle x|U|y\rangle|^2∣⟨x∣U∣y⟩∣2. For a Haar random UUU a single…

39 thms3 active usersReviewed
Complexity TheoryOptimizationTheoretical Computer Science·Captain: Shuze Chen

Sharp Power Loss Thresholds for Vector Min UncutResearch Paper

Vector Min Uncut asks for unit vectors, one per vertex of a weighted graph, such that the endpoints of every heavy edge are nearly antipodal. At rank one the vectors are signs ±1\pm1±1 and the problem is classical Min Uncut, the complement of Max-Cut, for which Agarwal, Charikar, Makarychev and Makarychev gave an O(log⁡∣V∣)O(\sqrt{\log |V|})O(log∣V∣​)-approximation (STOC 2005).…

22 thms3 active usersReviewed
CombinatoricsGraph Theory·Captain: Shuze Chen

Hitting time for loose Hamilton cycles in the random hypergraph processResearch Paper

Hitting-time theorems are among the sharpest statements in the theory of random graphs. Instead of asking at which edge density a property appears, they ask whether it appears at the exact moment the obvious local obstruction disappears. For graphs, Ajtai, Komlós and Szemerédi and, independently, Bollobás proved in 1984–85 that the random graph process…

21 thms3 active usersReviewed
CombinatoricsMarkov ChainTheoretical Computer Science·Captain: Shuze Chen

Fast Almost-Uniform Sampling of Random kkk-SAT SolutionsResearch Paper

A random kkk-SAT formula with nnn variables and m=⌊αn⌋m=\lfloor\alpha n\rfloorm=⌊αn⌋ clauses is the standard model of a typical constraint satisfaction instance. Below the satisfiability threshold, which is near 2kln⁡22^k\ln 22kln2 clauses per variable, such a formula has exponentially many solutions. Sampling one of them almost uniformly is a basic algorithmic task: it gives…

27 thms3 active usersReviewed
Algorithmic Game TheoryOptimizationTheoretical Computer Science·Captain: Shuze Chen

Correlated Forest Rounding for Unweighted Nash Social WelfareResearch Paper

In the Nash social welfare (NSW) problem, mmm indivisible items are divided among nnn agents with valuations vi:2M→R≥0v_i:2^M\to\mathbb R_{\ge0}vi​:2M→R≥0​, and the goal is to maximize the geometric mean (∏ivi(Si))1/n\big(\prod_i v_i(S_i)\big)^{1/n}(∏i​vi​(Si​))1/n of the agents' values. The objective sits between utilitarian welfare and max-min fairness and is invariant under rescaling any single valuation,…

16 thms3 active usersReviewed
Graph TheoryMachine LearningStatistics·Captain: Shuze Chen

Supervised Learning with Hidden CorrespondencesResearch Paper

In many data sets the correspondence between inputs and labels is lost or only partly known: records are linked across databases without a shared identifier, labels are released only in aggregate over bags of examples, or a privacy mechanism shuffles them. The learner then sees inputs X1,…,XnX_1,\dots,X_nX1​,…,Xn​ and labels Y1,…,YnY_1,\dots,Y_nY1​,…,Yn​ together with a graph of plausible…

24 thms3 active usersReviewed
🏆Completed
CombinatoricsMachine LearningTheoretical Computer Science·Captain: Shuze Chen

Algorithmic Principles For Multiclass Learning Are Hard To Come By: Limits of Regularization and Proper LearningResearch Paper

In binary classification, every PAC learnable class can be learned by a proper learner, one that always outputs a member of the class: empirical risk minimization does it, and learnability is characterized by the VC dimension. With many labels the picture changes. Daniely and Shalev-Shwartz introduced the DS dimension and conjectured that it characterizes…

11 thms3 active usersReviewed
Linear algebraMachine LearningTheoretical Computer Science·Captain: Shuze Chen

Nearly Optimal Strong Coresets for ℓp\ell_pℓp​ Subspace ApproximationResearch Paper

Low-rank approximation under robust losses is a basic primitive of data analysis. Given nnn points in Rd\mathbb R^dRd, the ℓp subspace approximation problem asks for a subspace of dimension at most kkk minimizing the sum of ppp-th powers of the Euclidean distances of the points to it. For p=2p=2p=2 this is principal component analysis; for 1≤p<21\le p<21≤p<2 it is less sensitive to…

24 thms3 active usersReviewed
Convex OptimizationGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

Polynomial-Time Differentially Private Synthetic Graph Release with Nearly-Linear Additive ErrorResearch Paper

Releasing a weighted graph under edge-level differential privacy is a basic task in private data analysis: the vertex set is public, the weight of every pair of vertices is private, and a released synthetic graph should preserve the answers to a rich family of queries. Cut queries are the canonical family, because many graph optimization problems (Max-Cut,…

23 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: Shuze Chen

Stratifying Markets for Efficient TradeResearch Paper

In bilateral trade a seller owns one item and a buyer wants it; each knows only their own cost or value. Myerson and Satterthwaite (1983) showed that no incentive-compatible, individually rational, budget-balanced mechanism trades efficiently whenever the supports of the value and the cost overlap, so the question becomes which simple mechanisms capture a…

30 thms3 active usersReviewed
cryptographyDiscrete GeometryTheoretical Computer Science·Captain: iris

Gaussian Difference Dynamics: Breaking the 2n/22^{n/2}2n/2 Barrier for the Shortest Vector Problem and Discrete Gaussian SamplingResearch Paper

A lattice L=BZnL = B\mathbb Z^nL=BZn is the set of integer combinations of the columns of a nonsingular matrix BBB. The shortest vector problem (SVP) asks for a nonzero vector of LLL of minimal Euclidean length λ1(L)\lambda_1(L)λ1​(L). Exact SVP is the computational core of lattice basis reduction, and its running time calibrates the security estimates of lattice-based…

68 thms3 active usersReviewed
Complexity TheorycryptographyTheoretical Computer Science·Captain: iris

Faster Provable Algorithm For Random Modular Subset SumResearch Paper

Subset sum asks, given integers a1,…,ana_1,\dots,a_na1​,…,an​ and a target ttt, for a set of indices whose coefficients sum to ttt. Its random modular version, with coefficients uniform in Z/QZ\mathbb Z/Q\mathbb ZZ/QZ and a planted binary solution, is the standard benchmark for generic attacks on knapsack-type cryptosystems and for the representation technique of Howgrave-Graham and…

27 thms3 active usersReviewed
Functional AnalysisOptimizationTheoretical Computer Science·Captain: mikedeng1

Primal/Dual Method for the Grothendieck ConstantResearch Paper

The real Grothendieck constant KGK_GKG​ measures how much a semidefinite relaxation can overestimate a bilinear ±1\pm1±1 optimization problem. It appears in Banach-space theory, where it is the best constant in Grothendieck's inequality Pis12; in quantum information, where it bounds the violation of correlation Bell inequalities AGT06; and in approximation…

24 thms3 active usersReviewed
CombinatoricsMarkov Chain·Captain: mikedeng1

Rapid Mixing for Sampling Colorings of Random Graphs up to Tree Uniqueness ThresholdResearch Paper

Sampling a uniformly random proper qqq-colouring of a graph is a basic problem in approximate counting and statistical physics: it is the zero-temperature antiferromagnetic Potts model, and an efficient sampler yields an approximation of the number of colourings. The standard sampler is the single-site Glauber dynamics: pick a uniformly random vertex and…

24 thms3 active usersReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: mikedeng1

Optimal Contention Resolution from SamplesResearch Paper

A contention resolution scheme receives a random collection of available elements and selects a feasible subset. With a capacity of kkk, feasibility means selecting at most kkk elements. The input can respect capacity on average while exceeding it on particular realizations. A useful selection rule must resolve these conflicts while preserving a guarantee for…

40 thms3 active usersReviewed
Quantum Information·Captain: mikedeng1

Matrix Samplers and Quantum-Proof Extractors: Their Correspondence and Almost-Optimal ConstructionsResearch Paper

Averaging samplers estimate the mean of a bounded function on {0,1}m\{0,1\}^m{0,1}m from a few correlated sample points generated by a short random string. Randomness extractors turn a weakly random source plus a short uniform seed into nearly uniform bits. Zuckerman showed that the two objects are the same thing seen from two sides: enumerating all seeds of an…

12 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Adaptivity Gaps for Welfare-Maximizing Pooled TestingResearch Paper

Pooled screening uses a limited number of assays to clear potentially valuable individuals or resources. A negative test certifies every member of its pool as healthy. With a fixed budget, later tests can respond to earlier outcomes, directing the remaining resources toward different people after positive and negative results. The mathematical question is…

17 thms3 active usersReviewed
Quantum Information·Captain: mikedeng1

A Unified Complexity Framework for Quantum Property TestingResearch Paper

A quantum experiment receives copies of an unknown state, while its scientific objective may be a single numerical property. Estimating that property can require fewer resources than reconstructing the entire state. A lower bound identifies when this apparent simplification still demands many copies, even when the experiment can measure those copies…

31 thms3 active usersReviewed
Machine LearningMathematical PhysicsQuantum Information+1·Captain: iris

Efficiently Learning SYK HamiltoniansResearch Paper

Hamiltonian learning from Gibbs states asks for the couplings of an unknown Hamiltonian HHH given independent copies of its thermal state e−βH/tr e−βHe^{-\beta H}/\mathrm{tr}\,e^{-\beta H}e−βH/tre−βH. It is the quantum analogue of learning an undirected graphical model, and it underlies the calibration and verification of quantum simulators. Existing polynomial-time guarantees rely…

32 thms3 active usersReviewed
Graph TheoryTheoretical Computer Science·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
PreviousPage 24 of 110Next

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