Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Statistics

598 missions · 354 completed

The mathematical discipline of drawing inferences from data under uncertainty: estimation, hypothesis testing, prediction, and the quantification of confidence. Grounded in probability, it spans classical and Bayesian inference, experimental design, and modern high-dimensional and nonparametric theory, asking what data can reveal and with what guarantees.

Missions

Open244Completed354All598
Machine LearningQuantum Information·Captain: iris

Finding Gaussian Structure in Bosonic StatesResearch Paper

Bosonic systems (optical modes, microwave cavities, motional modes of trapped ions) are described by states on Fock space, and the Gaussian states are the ones that standard optical hardware prepares most easily: squeezed, coherent and thermal states. They are fully described by a mean vector and a covariance matrix, and they can be learned from…

42 thms2 active usersReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: Shuze Chen

Achieving the Optimal Abstention Rate for Learning with Distribution ShiftResearch Paper

A classifier trained on one distribution is often deployed on data drawn from another. When nothing is assumed about the shift, no guarantee is possible on every test point, but a learner may abstain: it predicts on some test points and declines the rest. The question is then how few points it must decline while keeping its error low on the points it…

24 thms2 active usersReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: Shuze Chen

Data-Dependent Probability Estimation via Sample AmplificationResearch Paper

A statistician observes nnn independent draws S=(X1,…,Xn)S=(X_1,\dots,X_n)S=(X1​,…,Xn​) from an unknown distribution DDD on a finite domain [d]={1,…,d}[d]=\{1,\dots,d\}[d]={1,…,d}, and is then asked about an event, or more generally a [0,1][0,1][0,1]-valued query, chosen by looking at the same sample. Such data-dependent questions arise whenever a dataset is explored before it is analysed: adaptive data analysis,…

22 thms2 active usersReviewed
Computational ComplexityMachine LearningProbability+1·Captain: Shuze Chen

Average-case reductions for k-XOR and Tensor PCAResearch Paper

Planted noisy kkk-XOR and Tensor PCA are two canonical average-case problems. Both have a hidden sign vector, both have a wide range of parameters where the hidden vector is determined by the data but no polynomial-time algorithm is known to find it, and both are used as hardness assumptions: kkk-XOR for learning halfspaces, DNFs and tensor completion and in…

18 thms2 active usersReviewed
Graph TheoryProbabilityTheoretical Computer Science·Captain: Shuze Chen

Near-Quadratic Error-Free Graph Matching above Otter's Threshold via Approximate Local Tree Correlation TestingResearch Paper

Graph matching asks for the correspondence between the nodes of two structurally similar graphs. It is a quadratic assignment problem, NP-hard in the worst case, with applications such as the de-anonymization of social networks. The average-case version on random graphs is a standard testbed for the gap between what is information-theoretically possible and…

25 thms2 active usersReviewed
Machine LearningMarkov ChainProbability+1·Captain: Shuze Chen

Averaged Annealed Markov Chains Achieve the Algorithmic Threshold for Tensor PCA, Part I: Glauber DynamicsResearch Paper

In tensor PCA (the spiked tensor model of Richard and Montanari, 2014) one observes an order-kkk tensor that is a rank-one signal buried in Gaussian noise and must recover the hidden direction. The model is a standard testbed for the gap between what is statistically possible and what efficient algorithms achieve. Weak recovery is information-theoretically…

21 thms2 active usersReviewed
Quantum Information·Captain: mikedeng1

Optimal single-copy estimation of quantum state moments: why Tr⁡(ρ3)\operatorname{Tr}(\rho^3)Tr(ρ3) and Tr⁡(ρ4)\operatorname{Tr}(\rho^4)Tr(ρ4) are equally hardResearch Paper

Quantum experiments often provide repeated preparations of one unknown state while restricting which copies can interact. A state moment is the nonlinear quantity pt(ρ)=Tr⁡(ρt)p_t(\rho)=\operatorname{Tr}(\rho^t)pt​(ρ)=Tr(ρt), where ttt is a positive integer. Purity is the case t=2t=2t=2. Such quantities describe spectral information that a single linear observable does not determine. The…

31 thms2 active usersReviewed
Machine LearningProbability·Captain: mikedeng1

Optimal Learning under Tsybakov NoiseResearch Paper

A binary classifier predicts one of two labels from an observed instance. Its training error can be minimized without knowing the distribution that will generate future observations. The statistical question is how much worse that empirical minimizer can be than the best prediction rule for the population. Tsybakov noise permits instances whose labels are…

10 thms2 active usersReviewed
Information TheoryProbability·Captain: mikedeng1

Optimal Testing and Profile Recovery from Aggregated Binary Linear-Code SamplesResearch Paper

Aggregation can keep an algebraic distinction intact while making it statistically faint. In code-based masking, a secret is split into coordinates of a coset of a binary linear code, and a side channel reveals only aggregate Hamming-weight counts of the coordinates; how many observations an adversary or an evaluator needs to tell two configurations apart…

18 thms2 active usersReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: iris

Learning Positive Linear Combinations of ReLUs in Fully Polynomial TimeResearch Paper

A one-hidden-layer network with ReLU activation σ(t)=max⁡{0,t}\sigma(t)=\max\{0,t\}σ(t)=max{0,t} and nonnegative output weights computes a positive linear combination of ReLUs. Learning this class under Gaussian inputs is the simplest extension of learning a single neuron (a generalized linear model). Chen, Klivans and Meka (CKM22) call a polynomial-time algorithm for arbitrary sums…

33 thms2 active usersReviewed
Markov ChainProbability·Captain: Shuze Chen

Identity Testing of Markov Chains from a Single TrajectoryResearch Paper

A common statistical question about a stochastic system is whether its dynamics agree with a reference model. Examples are a calibrated queueing simulator, a fitted mobility model, or a Markov chain Monte Carlo sampler that is supposed to implement a known kernel. Often the only data is one trajectory: the chain cannot be restarted, its initial state is not…

21 thms2 active usersReviewed
Machine LearningProbability·Captain: iris

Geometrically Constrained Learning I: Agnostically Learning Adversarially Robust ClassifiersResearch Paper

A classifier is adversarially robust when a small change to its input rarely changes its output. Backdoors planted in learned models ([GKVZ22], FOCS 2022) and the post-processing defences built against them ([GSVV25], STOC 2025) assume that a well-behaved classifier can be trained in the first place. Under Gaussian data this question has a clean form.…

28 thms2 active usersReviewed
Machine LearningProbability·Captain: iris

Likelihood-Ratio Learning under Weak Overlap via Analytic Temporal EliminationResearch Paper

Many statistical procedures need the log density ratio ℓ⋆=log⁡(p/q)\ell^\star=\log(p/q)ℓ⋆=log(p/q) between two laws PPP and QQQ that are known only through samples: covariate-shift correction, off-policy evaluation, simulation-based inference and mutual-information estimation all reweight one sample by eℓ⋆e^{\ell^\star}eℓ⋆. The standard direct method is balanced logistic density-ratio…

19 thms2 active usersReviewed
🏆Completed
Machine Learning·Captain: mikedeng1

Tight Release Schedules under Distribution ShiftResearch Paper

A deployed predictor can remain unchanged while its owner collects labels, retains observations and computes candidate replacements. A limit on replacing the deployed predictor therefore creates a statistical scheduling question: how much prediction error is unavoidable when only a few replacements are allowed? This differs from restricting access to labels…

14 thms2 active usersReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: Shuze Chen

A Good Way to Find Good HypothesesResearch Paper

Hypothesis selection is the basic learning problem behind the cover method of density estimation: given nnn known distributions h1,…,hnh_1,\dots,h_nh1​,…,hn​ and samples from an unknown distribution ppp, output a distribution almost as close to ppp in total variation as the best hih_ihi​. A proper algorithm must output one of the hih_ihi​. Scheffé-type tournaments and the minimum distance…

18 thms2 active usersReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: Shuze Chen

Distribution-Robust Halfspace TestingResearch Paper

A halfspace (linear classifier) x↦sign⁡(⟨w,x⟩−t)x\mapsto\operatorname{sign}(\langle w,x\rangle-t)x↦sign(⟨w,x⟩−t) is the simplest model for labelled data in Rn\mathbb R^nRn. Before training one, it is useful to know whether the labels are close to linearly separable. A property tester decides this from far less data than a learner needs, the "model selection" motivation of Goldreich,…

20 thms2 active usersReviewed
Quantum Information·Captain: mikedeng1

Optimal Purity Estimation with Incoherent MeasurementsResearch Paper

The purity of a quantum state measures how far its statistical description is from a pure state. For a subsystem of a larger pure system, its negative logarithm is the second Rényi entropy, which measures entanglement with the rest of the system. Experimental protocols based on randomized measurements use purity to characterize quantum states without…

31 thms2 active usersReviewed
🏆Completed
Machine Learning·Captain: mikedeng1

An Optimal Agnostic PAC AlgorithmResearch Paper

Binary classification from i.i.d. examples is the basic model of statistical learning theory, and the sharp sample complexity of learning a class of finite VC dimension has been studied since the work of Vapnik and Chervonenkis and of Valiant. The question matters to learning theorists because it decides how much data a learner needs when the best…

15 thms2 active usersReviewed
Convex OptimizationProbabilityTheoretical Computer Science·Captain: mikedeng1

An Exact-Radius Convex Characterization of Discrete Identity TestingResearch Paper

Identity testing asks whether observations follow a specified probability distribution or a distribution farther than a prescribed distance from it. For a known finite reference, the amount of data needed can depend on the distribution of mass across labels, including a dominant atom, a light tail, and labels with zero reference probability. A bound that…

24 thms2 active usersReviewed
Complexity TheoryProbability·Captain: mikedeng1

The Polynomial-Time Low-Degree Conjecture is FalseResearch Paper

The low-degree method studies whether a statistic given by a polynomial of bounded degree can distinguish a structured random observation from an unstructured one. In statistical inference and average-case complexity, failure of such tests is often used as evidence that efficient algorithms will also fail. The polynomial-time conjecture considered here adds…

18 thms2 active usersReviewed
Machine LearningTheoretical Computer Science·Captain: iris

Adaptive Data Analysis and Adversarial Robustness on Insertion-Deletion StreamsResearch Paper

Statistical analyses are often adaptive: an analyst inspects earlier results on a data set before choosing the next test. When the tests are chosen this way, the empirical answers on a fixed sample can overfit, and a result that looks significant may only reflect the sample [HU14, SU15, DFH+15b]. Adaptive data analysis turns this into a question about…

35 thms2 active usersReviewed
Graph TheoryProbability·Captain: iris

Distinguishability Threshold for Random Geometric GraphsResearch Paper

The binomial random graph G(n,p)G(n,p)G(n,p) joins every pair of nnn vertices independently with probability ppp. Many real networks are instead built from proximity: each vertex carries a hidden position, and nearby vertices are joined. The spherical random geometric graph G(n,d,p)G(n,d,p)G(n,d,p) is the high-dimensional version of this model. In high dimension the geometry should wash…

29 thms2 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: iris

Rounding, Ranges, and Exact Sample-Removal Audits for Least SquaresResearch Paper

The sign of a least-squares coefficient often carries the substantive conclusion of an empirical study. Giordano, Meager and Broderick showed that deleting a small fraction of the observations can reverse such conclusions in prominent studies (GMB26). This raises an auditing question: how many observations must be removed before a conclusion drawn from an…

21 thms2 active usersReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: iris

Linear Regression with Self-Selection Bias in Polynomial TimeResearch Paper

In many data sets the recorded response is not the outcome of one fixed model but the largest of several. Workers choose among occupations and only the earnings from the chosen one are observed (Roy, 1951); auction data may reveal only the transaction price, not the winning bidder or the losing bids (Athey–Haile, 2002); the model of Fair and Jaffee (1972)…

32 thms2 active usersReviewed
Graph TheoryHarmonic AnalysisProbability·Captain: iris

Sharp detection thresholds for random geometric graphs with polynomial average degreesResearch Paper

A random geometric graph (RGG) hides a latent geometry: each vertex carries a random point, and edges join nearby points. In high dimension the geometry washes out, and a basic question in probability, statistics and theoretical computer science is the dimension at which the graph becomes statistically indistinguishable from an Erdős–Rényi graph with the…

34 thms2 active usersReviewed
PreviousPage 14 of 24Next

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