Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Probability

2,744 missions · 1,570 completed

Missions

Open1174Completed1570All2744
CombinatoricsTheoretical Computer Science·Captain: Shuze Chen

Catalan Hashing: Efficient Linear Probing for Variable-Length ItemsResearch Paper

Linear probing stores each key in the first free cell at or after its hash position, so a query is a single forward scan over a contiguous region of memory. That locality is why linear probing is the default hash table in practice and in external memory, and its analysis goes back to Knuth's 1963 note and its many refinements (Knuth, The Art of Computer…

10 thms1 active userReviewed
Quantum InformationStatistics·Captain: iris

Quantum Multivariate Mean Estimation: O~(n)\tilde O(n)O~(n) Queries Give Error TrΣ/n+∥Σ∥log⁡(1/δ)/n\sqrt{\mathrm{Tr}\Sigma/n}+\sqrt{\|\Sigma\|\log(1/\delta)/n}TrΣ/n​+∥Σ∥log(1/δ)/n​ if n≤dn\le dn≤d, dTrΣlog⁡(d/δ)/n\sqrt{d\mathrm{Tr}\Sigma}\log(d/\delta)/ndTrΣ​log(d/δ)/n if n>dn>dn>dResearch Paper

Estimating the mean of a random vector from samples is a basic task in statistics, learning and simulation. Classically, the optimal answer is known: with nnn samples, the sub-Gaussian estimators of Lugosi and Mendelson achieve error Tr(Σ)/n+∥Σ∥log⁡(1/δ)/n\sqrt{\mathrm{Tr}(\Sigma)/n}+\sqrt{\|\Sigma\|\log(1/\delta)/n}Tr(Σ)/n​+∥Σ∥log(1/δ)/n​ in Euclidean norm with probability 1−δ1-\delta1−δ, for every…

24 thms1 active userReviewed
AnalysisOperations ResearchOptimization+1·Captain: Shuze Chen

Gain-Sharing Optimization in Randomized Primal–Dual Analysis: Structure and CertificationResearch Paper

Randomized primal–dual analysis is the standard way to prove competitive ratios for online matching and allocation: the algorithm's gain is split between dual variables, and a uniform expected dual-feasibility factor γ\gammaγ certifies a γ\gammaγ-competitive guarantee by weak duality (Devanur, Jain, Kleinberg 2013). The split is governed by a gain-sharing…

23 thms1 active userReviewed
Machine LearningStatisticsTheoretical Computer Science·Captain: Shuze Chen

The Sample Complexity of Multi-Class OmnipredictionResearch Paper

A predictor of class probabilities is often used by many downstream decision makers, each with its own loss. Omniprediction (Gopalan, Kalai, Reingold, Sharan, Wieder, 2022, arXiv:2109.05389) asks for one predictor whose best-response post-processing competes, for every loss in a class simultaneously, with every rule in a benchmark class. For binary labels…

20 thms1 active userReviewed
Machine LearningOptimizationStatistics+1·Captain: Shuze Chen

Tensor Decomposition Beyond the Spectral ThresholdResearch Paper

Tensor decomposition asks, given all entries of an order-kkk tensor T=∑i=1mvi⊗kT=\sum_{i=1}^m v_i^{\otimes k}T=∑i=1m​vi⊗k​, to recover the rank-one components viv_ivi​ up to the symmetries of the problem. It underlies algorithms for dictionary learning, topic models and mixtures of spherical Gaussians. For general tensors it is intractable: computing the rank of a third-order tensor is…

18 thms1 active userReviewed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: Shuze Chen

One Trap Is Enough: The Structure and Complexity of Robust Contracts for Sequential SearchResearch Paper

In research and development, procurement and delegated experimentation, an agent tries costly options with random outcomes one at a time, keeps the best outcome found, and decides when to stop; the principal sees only the outcome that is finally submitted and pays a wage that depends on it. Without an incentive problem this is Pandora's box problem (Weitzman…

19 thms1 active userReviewed
Theoretical Computer Science·Captain: Shuze Chen

An Information Hierarchy of Privacy Filters and OdometersResearch Paper

Differential privacy is usually analysed for a fixed sequence of releases, but in practice an analyst queries a database adaptively, choosing each request after seeing earlier answers, and the privacy cost of the next answer may itself depend on what has been released. Two kinds of procedures control the cumulative privacy loss of such an interaction: privac…

11 thms1 active userReviewed
Algorithmic Game TheoryOperations Research·Captain: Shuze Chen

Order-selection Prophet Inequality (Almost) Goes I.I.D.Research Paper

In the prophet inequality a gambler sees independent nonnegative values V1,…,VnV_1,\dots,V_nV1​,…,Vn​ with known distributions one at a time and may accept at most one, irrevocably, when it is revealed; the benchmark is the prophet's E[max⁡iVi]\mathbb E[\max_i V_i]E[maxi​Vi​]. In an adversarial order the best ratio is 1/21/21/2 (Krengel–Sucheston 1977; Samuel-Cahn 1984). In the order-selection varian…

22 thms1 active userReviewed
Random Matrix TheoryTheoretical Computer Science·Captain: Shuze Chen

Improved Bounds for Certifying Injective Norm of Sparse Random TensorsResearch Paper

The injective norm of a symmetric tensor is the largest value of its multilinear form on the unit sphere. For matrices it is the largest absolute eigenvalue and is computable in polynomial time; for tensors of order k≥3k\ge3k≥3 computing it, or even approximating it, is NP-hard in the worst case (Hillar–Lim 2013). For random tensors the injective norm is small…

24 thms1 active userReviewed
cryptographyTheoretical Computer Science·Captain: Shuze Chen

Minimizing Key Schedules for Key-Alternating CiphersResearch Paper

A key-alternating cipher (KAC) encrypts a block mmm of a finite abelian group GGG by alternately adding round keys and applying fixed public permutations: x0=k0−mx_0=k_0-mx0​=k0​−m, xj=kj−πj(xj−1)x_j=k_j-\pi_j(x_{j-1})xj​=kj​−πj​(xj−1​). Its provable security in the random permutation model is well understood when the t+1t+1t+1 round keys are independent and uniform (Hoang–Tessaro 2016), but real ciphers derive…

13 thms1 active userReviewed
cryptographyInformation TheoryTheoretical Computer Science·Captain: Shuze Chen

The Information-Theoretic Limits of Hiding Among Decoys in the Shuffle ModelResearch Paper

Hiding a genuine secret among plausible decoys is a recurring pattern in security and privacy. A honeyword system stores a user's real password together with n−1n-1n−1 fake ones and raises an alarm when a fake one is used (Juels–Rivest 2013). A computationally unbounded adversary who decrypts a ciphertext under every key of a small key space obtains one genuine…

16 thms1 active userReviewed
CombinatoricsMarkov ChainTheoretical Computer Science·Captain: mikedeng1

Tight Variable-Occurrence Bounds and Exponential Separations for Moser–Tardos and WalkSAT on 3-CNFResearch Paper

WalkSAT and the Moser–Tardos algorithm (MT) are the two standard clause-driven local-repair procedures for satisfiability. Both keep a complete assignment and repeatedly pick an unsatisfied clause. WalkSAT flips one variable of it (Papadimitriou 1991, Schöning 1999); MT resamples all of its variables with fresh random bits, which is the algorithmic form of…

28 thms1 active userReviewed
Complexity TheoryGroup Theory·Captain: mikedeng1

On Testing Finite GroupsResearch Paper

A multiplication table describes a binary operation on a finite labelled set. Reading the whole table requires quadratically many entries. Property testing instead asks for a decision from substantially fewer entries: accept a genuine group and reject an operation that requires many changes to become any group. This question concerns algorithms that receive…

36 thms1 active userReviewed
CombinatoricsInformation Theory·Captain: mikedeng1

A Universal Threshold Theory for Local Properties of Random Linear CodesResearch Paper

A linear code stores messages as vectors in a finite-dimensional vector space. Its dimension controls how many messages it can represent, while its other properties determine what kinds of corruption or ambiguity it can tolerate. Researchers studying random codes therefore ask at which dimensions a given property becomes likely. For many properties, a small…

5 thms1 active userReviewed
Graph TheoryOperations ResearchTheoretical Computer Science·Captain: mikedeng1

Competitive Random-Order Correlation k-ClusteringResearch Paper

Correlation clustering groups objects using only pairwise similarity judgements. Each pair is labelled positive or negative, and a clustering pays for positive pairs separated into different groups and negative pairs placed together. This objective is useful when similarities are qualitative and need not come from distances. Limiting the number of groups…

31 thms1 active userReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: mikedeng1

Random Deletion for Circuits in Regular MatroidsResearch Paper

Karger's random contraction algorithm ([Kar93], [Kar95]) showed that a graph with minimum cut weight λ\lambdaλ has at most n2αn^{2\alpha}n2α cuts of weight at most αλ\alpha\lambdaαλ. Through matroid duality, cuts of a graph are the circuits of its cographic matroid and cycles are the circuits of its graphic matroid, and Subramanian ([Sub95]) proved the analogous bound …

25 thms1 active userReviewed
Linear algebraTheoretical Computer Science·Captain: mikedeng1

Matrix sensing meets property testing: Sample-optimal testing for low rankResearch Paper

A low-rank matrix represents a linear transformation whose output lies in a small-dimensional subspace. Matrix sensing uses random linear measurements to recover such a transformation. Recovery assumes that the target has low rank; a property test instead checks that assumption, distinguishing a matrix with rank at most a specified integer from one…

21 thms1 active userReviewed
Mathematical PhysicsQuantum Information·Captain: iris

Rapid mixing of Gibbs samplers via quantum Dobrushin–Shlosman conditionsResearch Paper

Preparing the Gibbs state σβ=e−βH/Tr e−βH\sigma_\beta=e^{-\beta H}/\mathrm{Tr}\,e^{-\beta H}σβ​=e−βH/Tre−βH of a quantum many-body Hamiltonian is a basic task of quantum simulation: it gives access to thermal expectation values, and it is the quantum analogue of Markov chain Monte Carlo. A quantum Gibbs sampler is a continuous-time quantum Markov dynamics etLe^{t\mathcal L}etL whose unique…

31 thms1 active userReviewed
Algorithmic Game TheoryOperations ResearchTheoretical Computer Science·Captain: Shuze Chen

Santa Claus and Weighted Nash Social Welfare with Subadditive ValuationsResearch Paper

In max-min allocation, also called the Santa Claus problem, nnn agents share mmm indivisible items and the aim is to make the worst-off agent as well off as possible. It is the egalitarian counterpart of welfare maximization and a basic model of fair division; with identical valuations its optimum is the maximin share of the agents. The problem is NP-hard even…

22 thms1 active userReviewed
Computational GeometryMarkov ChainTheoretical Computer Science·Captain: Shuze Chen

An FPRAS for Mixed VolumesResearch Paper

For compact convex sets K1,…,Km⊆RnK_1,\dots,K_m\subseteq\mathbb{R}^nK1​,…,Km​⊆Rn, Minkowski showed that the volume of a weighted Minkowski sum is a homogeneous polynomial of degree nnn in the weights,

27 thms1 active userReviewed
Machine LearningStatisticsTheoretical Computer Science·Captain: Shuze Chen

Proper Agnostic Learning of Two Balanced Product Distributions from Prefix-Conditional SamplesResearch Paper

Mixtures of product distributions on the Boolean cube are a basic model of latent structure: each sample comes from one of a few hidden populations, and within a population the coordinates are independent. Learning such mixtures from ordinary samples is hard in general. Learning two-component mixtures, for example, requires assumptions on the component…

19 thms1 active userReviewed
StatisticsTheoretical Computer Science·Captain: Shuze Chen

Memory–Sample Tradeoffs in High–Dimensional StatisticsResearch Paper

Many high-dimensional estimation and testing problems show a gap between the number of samples that suffices information-theoretically and the number that efficient algorithms seem to need. Statistical-query (SQ) lower bounds are one standard way to show such gaps. A central example is Non-Gaussian Component Analysis (NGCA): distinguish a standard Gaussian…

13 thms1 active userReviewed
Mathematical PhysicsTheoretical Computer Science·Captain: Shuze Chen

Hopfield Model with ppp-spin Interactions: Shattering, Disorder Chaos and Sampling HardnessResearch Paper

The Hopfield model is the standard model of an associative memory: MMM random patterns η1,…,ηM∈Rn\eta^1,\dots,\eta^M\in\mathbb R^nη1,…,ηM∈Rn are stored in the couplings of a spin system on {−1,1}n\{-1,1\}^n{−1,1}n by Hebb's rule, and the low-energy configurations are meant to retrieve them. Its ppp-spin (dense) version couples ppp spins at a time; it stores about np−1n^{p-1}np−1 patterns instead of about …

21 thms1 active userReviewed
Graph TheoryTheoretical Computer Science·Captain: Shuze Chen

Near-Optimal Space and Time Cut Sparsification in Turnstile StreamsResearch Paper

A cut sparsifier of a weighted graph G=(V,E,w)G=(V,E,w)G=(V,E,w) on nnn vertices is a reweighted subgraph HHH that approximates the weight of every cut of GGG within a factor 1±ε1\pm\varepsilon1±ε. Benczúr and Karger showed that every graph has one with O(nlog⁡n/ε2)O(n\log n/\varepsilon^2)O(nlogn/ε2) edges, and sparsifiers have since become a basic tool for minimum cut, maximum flow, Laplacian solvers and…

22 thms1 active userReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

Random-Walk Cuckoo Hashing is Efficient up to the Critical Load ThresholdResearch Paper

Cuckoo hashing stores keys in a table so that every key sits in one of a few cells determined by its hashes, which makes lookups take constant worst-case time. With ddd hashes per key, the table can be filled almost completely: Fountoulakis and Panagiotou (FP12) identified the exact load threshold 1−εd∗1-\varepsilon^*_d1−εd∗​ up to which all keys can be placed with high…

20 thms1 active userReviewed
PreviousPage 97 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