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
🏆Completed
Machine LearningOperations ResearchStatistics+1·Captain: mikedeng1

Foundations of Machine Learning XIV: Finite Markov Decision Processes and Bellman's EquationsTextbook

Reinforcement learning formalizes a scenario supervised learning cannot: an agent that actively interacts with an environment, choosing actions that change both the state it observes next and the reward it receives, rather than passively receiving an i.i.d. labeled sample. Every practical treatment of this scenario — from classical dynamic programming to…

13 thms3 active usersReviewed
🏆Completed
Machine LearningRandom Matrix TheoryStatistics·Captain: mikedeng1

High-Dimensional Probability XI: Dvoretzky-Milman's TheoremTextbook

A striking fact discovered by Dvoretzky in the 1960s (conjectured by Grothendieck, and sharpened into its modern quantitative form by Milman in 1971) is that every high-dimensional convex body, however irregular, contains a round slice: a random low-dimensional section (or projection) of any bounded convex set in Rn\mathbb R^nRn is, with high probability, close…

9 thms3 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

Support Vector Machines V: Bernstein's Inequality for Independent Hilbert-Space-Valued Random VariablesTextbook

Every statistical guarantee for a learning algorithm ultimately rests on a concentration inequality: a bound on how far an empirical average can stray from its expectation. For real-valued averages, Bernstein's inequality (1924, refined through the 20th century) is the classical tool — sharper than Hoeffding's inequality whenever the summands' variance is…

5 thms3 active usersReviewed
🏆Completed
Operations ResearchStatisticsStochastic Systems·Captain: mikedeng1

Stochastic Orders III: The Convex Order and Strassen's Martingale CouplingTextbook

Chapter I's usual stochastic order compares "how large" two random variables tend to be. A different, equally common question in operations research is "how spread out" a random variable is: two portfolios with the same expected loss can differ sharply in how much that loss varies, and a risk-averse decision maker or a convex cost function cares about…

6 thms3 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: mikedeng1

Stochastic Orders II: The Mean Residual Life OrderTextbook

A device's mean residual life at age ttt — its conditional expected remaining lifetime given that it has survived to ttt — is one of the oldest and most interpretable summaries in reliability and survival analysis: it is what an insurer, a maintenance planner, or a hospital outcomes researcher actually wants to know about a unit still in service. Comparing two…

7 thms3 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Introduction to Stochastic Programming VIII: Multistage Jensen Bounds and AggregationTextbook

A multistage stochastic program's exact deterministic equivalent grows exponentially with the number of periods, even when each period's random data takes only a handful of values (Chapter 9's concern was the growth in the number of realizations; Chapter 10 adds growth in the number of periods). One remedy, generalizing Chapter 8's single-period Jensen…

4 thms3 active users
🏆Completed
Convex OptimizationLinear OptimizationOperations Research+1·Captain: mikedeng1

Introduction to Stochastic Programming III: The L-Shaped Method and Its Finite ConvergenceTextbook

Two-stage stochastic programs with recourse — choose a first-stage decision xxx now, observe a random outcome ξ\xiξ, then choose a second-stage recourse decision y(ξ)y(\xi)y(ξ) to repair whatever xxx left infeasible or suboptimal — are the workhorse model of the field, used for capacity planning, inventory and financial portfolio problems since the 1950s (Dantzig 1955;…

6 thms3 active users
🏆Completed
Analysis·Captain: naimengye

Probability Theory and Examples I: Kolmogorov's Three-Series TheoremTextbook

Given independent random variables X1,X2,…X_1,X_2,\dotsX1​,X2​,…, when does ∑nXn\sum_n X_n∑n​Xn​ converge? Not absolutely — that question is settled by ∑nE∣Xn∣<∞\sum_n\mathbb{E}|X_n|<\infty∑n​E∣Xn​∣<∞ and is usually too strong. The interesting question is when the partial sums converge for almost every outcome, and here independence buys something that holds for no general sequence: convergence is not…

6 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: mikedeng1

Introduction to Stochastic Programming II: The Value of Perfect Information and of the Stochastic SolutionTextbook

Every stochastic program is, in practice, compared against a shortcut. A decision maker facing genuine uncertainty is tempted either to replace the random data by its mean and solve one deterministic problem, or to imagine that perfect information about the future were available and solve a separate deterministic problem per scenario. Both temptations have…

8 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: Shuze Chen

Dynamic Programming and Optimal Control VII: Infinite Horizon ProblemsTextbook

Infinite-horizon dynamic programming is the mathematical core of Markov decision processes and reinforcement learning: Bellman equations, value iteration, policy iteration, and their guarantees. Chapter 7 of Bertsekas, Dynamic Programming and Optimal Control, Vol. I (3rd ed., 2005) develops the finite-state theory in its cleanest generality — stochastic…

8 thms3 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: Shuze Chen

The Higher-Order Identifiability Paradox: Learning and Certifying Hypergraph OrderResearch Paper

Predictors built on coarse views of a hypergraph — features that keep only interactions up to some order and discard the rest — are cheaper and more stable than full-order models, but discarding the higher-order part is safe only when that part carries little signal. Zhang, Yan, Qiao and Yu (The Higher-Order Identifiability Paradox: Learning and Certifying…

15 thms2 active usersReviewed
🏆Completed
CombinatoricsInformation TheoryTheoretical Computer Science·Captain: Shuze Chen

Synchronization Strings over a Ternary AlphabetResearch Paper

Codes that correct substitutions and erasures assume that the receiver knows where each symbol belongs. Insertions and deletions break that assumption: a single deletion shifts every later symbol. Haeupler and Shahrasbi introduced synchronization strings (HS17) to restore position information cheaply. The sender attaches one symbol of a fixed string SSS to…

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

Calibrated Multiaccuracy: Deterministic and Randomized Sample ComplexityResearch Paper

Multiaccuracy asks that a predictor's residuals be uncorrelated with every test in a fixed class: subpopulations or features that an auditor can compute should not reveal systematic over- or under-prediction. The condition was introduced by Hébert-Johnson, Kim, Reingold and Rothblum (2018) under the name multi-AE, alongside multicalibration. Calibration asks…

25 thms2 active usersReviewed
🏆Completed
AlgebraNumerical AnalysisTheoretical Computer Science·Captain: Shuze Chen

Approximate Syzygies of Smoothed Polynomials and ApplicationsResearch Paper

Many algorithms for tensor decomposition, polynomial system solving and learning mixtures reduce to linear algebra on Macaulay matrices: given polynomials b1,…,bmb_1,\dots,b_mb1​,…,bm​, the matrix of the map (h1,…,hm)↦∑ibihi(h_1,\dots,h_m)\mapsto\sum_i b_ih_i(h1​,…,hm​)↦∑i​bi​hi​ at a fixed output degree. Whether such an algorithm is robust to noise depends on how far this map is from losing rank, beyond the…

12 thms2 active usersReviewed
🏆Completed
Discrete Geometry·Captain: mikedeng1

Optimal Average Distortion for Non-Expansive Embeddings of Euclidean Metrics into the Line: With applications to cut-matching games and vertex expansionResearch Paper

Non-expansive maps of a metric space into the real line with small average distortion are a standard rounding device for graph partitioning. A relaxation (a linear or semidefinite program) produces a metric on the vertices; a 1-Lipschitz map to the line that preserves the average distance up to a factor DDD is then thresholded into a cut, and DDD becomes the…

9 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Subgaussian Vector Balancing by an Ising ModelResearch Paper

Vector balancing asks how to choose signs for short vectors so that their sum remains controlled in every direction. A distribution over signs offers a probabilistic version: every linear measurement of the resulting signed sum should have a small exponential moment. This is useful when a randomized assignment must balance several numerical covariates…

17 thms2 active usersReviewed
🏆Completed
AnalysisFunctional Analysis·Captain: mikedeng1

A dimension-free bound for the isoperimetric constant of unconditional log-concave measuresResearch Paper

A probability distribution in high dimension can be difficult to control even when every one-dimensional coordinate has variance one. A Poincaré inequality controls the variance of every locally Lipschitz real function by its average squared gradient. For log-concave distributions, this functional inequality also controls isoperimetry. It therefore connects…

24 thms2 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryMathematical Physics·Captain: Shuze Chen

A Complete Hierarchy of Local LemmasResearch Paper

Suppose each vertex vvv of a graph GGG carries a bad event AvA_vAv​ with Pr⁡(Av)≤pv\Pr(A_v)\le p_vPr(Av​)≤pv​, and GGG is a dependency graph: each AvA_vAv​ is independent of the collection of events at its non-neighbors. The Lovász Local Lemma gives a local sufficient condition under which, with positive probability, no bad event occurs. Shearer (Shearer 1985) found the exact condition: writing

20 thms2 active usersReviewed
🏆Completed
cryptographyTheoretical Computer Science·Captain: iris

Correlated Group Actions: Founding Cryptography on S4 and SnResearch Paper

Oblivious transfer (OT) is a two-party primitive in which a sender holds two bits m0,m1m_0, m_1m0​,m1​, a receiver holds a selection bit sss, and the receiver learns msm_sms​ while the sender learns nothing about sss and the receiver learns nothing about the other bit m1−sm_{1-s}m1−s​. Kilian showed in 1988 that OT is complete for secure two-party computation: any function can be…

15 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Tight weighted paging with delay via mirror descentResearch Paper

A cache can avoid repeated downloads by retaining useful pages. When requests may wait, it can also batch several requests for the same page into one download. These two choices interact: waiting may save a fetch, but holding a page while waiting occupies space that another page needs. Weighted paging with delay asks for an online rule that balances these…

19 thms2 active usersReviewed
🏆Completed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

Tight Bounds for Randomized Generalized k-Server on Uniform MetricsResearch Paper

The generalized kkk-server problem was introduced by Koutsoupias and Taylor (KT04) as a model of kkk heterogeneous servers, each moving in its own metric space, that must jointly answer requests naming one location per server. It contains the classical kkk-server problem, weighted kkk-server, and paging with heterogeneous cache slots as special cases, and it is a…

12 thms2 active usersReviewed
🏆Completed
Information Theory·Captain: mikedeng1

On the optimality of truncation among binary linear sketchesResearch Paper

A binary linear sketch compresses a binary vector by reporting parity measurements: each output bit is the sum modulo two of selected input coordinates. Such sketches support distributed computation because parity measurements of a sum can be obtained by adding the separate measurements. When two terminals observe correlated data, however, preserving this…

14 thms2 active usersReviewed
🏆Completed
Combinatorics·Captain: mikedeng1

Tight Bounds for Tusnády's Problem in the PlaneResearch Paper

A coloring assigns each point one of two signs, interpreted as membership in two groups. For a region of the plane, its imbalance is the absolute difference between the numbers of points of the two signs inside it. Small imbalance simultaneously over many regions is a basic objective of geometric discrepancy theory. Axis-parallel rectangles are a natural…

13 thms2 active usersReviewed
🏆Completed
Graph TheoryInformation Theory·Captain: mikedeng1

Entropy Bounds for Local Coordination and Graph AmenabilityResearch Paper

Consider players on a graph who each output a random bit and want neighbours to agree, while each player sees only some of the available random sources. Hutchcroft, Rospuskova and Tamuz studied this problem for communication limited to a graph distance, and showed that low inefficiency forces the graph to be amenable: a small fraction of the edges can be…

14 thms2 active usersReviewed
🏆Completed
Complexity Theory·Captain: mikedeng1

Parallel Repetition for k-Player XOR GamesResearch Paper

Parallel repetition is the standard way to amplify the soundness of multi-prover interactive protocols without adding players or rounds. A verifier plays nnn copies of a one-round game at once and accepts only if every copy is won. The basic question is how fast the optimal winning probability falls with nnn. This matters for probabilistically checkable proofs…

15 thms2 active usersReviewed
PreviousPage 38 of 62Next

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