Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in
← Collections

The OR Formalization Drive

A coordinated effort to formalize the mathematics of operations research in Lean 4.

Scope: missions in linear and integer programming, convex and nonlinear optimization, combinatorial optimization, dynamic programming, scheduling, stochastic models such as queueing and inventory, simulation, revenue management, and game theory and mechanism design.

3527 completed missions

Missions

201–225 of 3527
Open1285Completed3527All4812
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Robust Sample Average Approximation 3: The Kolmogorov–Smirnov, Kuiper, Cramér–von Mises, Watson and Anderson–Darling Tests with O(N^(−1/2)) Thresholds Are Uniformly ConsistentResearch Paper

Robust Sample Average Approximation (Robust SAA) is a data-driven approach to stochastic optimization proposed by Bertsimas, Gupta and Kallus (arXiv:1408.4445; Mathematical Programming (2018), doi:10.1007/s10107-017-1174-z). Instead of minimizing the empirical average of a cost, a decision maker minimizes the worst-case expected cost over a distributional…

11 thms5 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization·Captain: mikedeng1

A game-theoretic approach to computation offloading in mobile cloud computing I: The Offloading GNEP Has a SolutionResearch Paper

Mobile devices run applications whose computational load can exceed what the device itself can serve in reasonable time and with reasonable battery drain. Computation offloading sends part of that load elsewhere: to a cloudlet, a small cluster of servers one wireless hop away, or to a distant cloud reached through the wide-area network. The cloudlet is…

9 thms5 active usersReviewed
🏆Completed
Complexity TheoryOperations ResearchOptimization+1·Captain: mikedeng1

Scheduling Problems with Two Competing Agents 7: PARTITION Reduces to Two Agents Each Bounding Their Own Makespan in the Two-Machine Flow Shop and Open ShopResearch Paper

In multi-agent scheduling, several decision makers share one processing resource, and each one cares only about the completion of its own jobs. Agnetis, Mirchandani, Pacciarelli and Pacifici (Oper. Res. 52(2), 2004) set up the two-agent version of this problem and classified its complexity for most combinations of classical objectives. Typical settings are…

14 thms5 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Distribution-Free, Risk-Controlling Prediction Sets II: The Waudby-Smith–Ramdas Betting Bound Is a (1 − δ) Upper Confidence Bound for the Mean Loss (Proposition 5)Research Paper

A risk-controlling prediction set is a set-valued predictor T\mathcal TT that, with probability at least 1−δ1-\delta1−δ over a calibration sample, has expected loss at most a target level α\alphaα. Bates, Angelopoulos, Lei, Malik and Jordan (arXiv:2101.02703, J. ACM 2021) build such sets for any black-box predictor and any bounded loss by a procedure called upper…

7 thms5 active usersReviewed
🏆Completed
AlgebraCombinatoricsDiscrete Geometry+1·Captain: mikedeng1

Generalising the Scattered Property of Subspaces 4: For n ≥ h + 3, the Delsarte Dual of a Maximum h-Scattered Subspace of Dimension rn/(h + 1) Is Maximum (n − h − 2)-ScatteredResearch Paper

Scattered subspaces are a central object of finite geometry. An Fq\mathbb F_qFq​-subspace UUU of an Fqn\mathbb F_{q^n}Fqn​-vector space is scattered when every one-dimensional Fqn\mathbb F_{q^n}Fqn​-subspace meets it in Fq\mathbb F_qFq​-dimension at most one. They give the largest scattered linear sets of projective spaces, and through them constructions of two-intersection sets,…

9 thms5 active usersReviewed
🏆Completed
AnalysisOptimal TransportOptimization·Captain: mikedeng1

Computational Optimal Transport X: For the Cost c = d a Function Is a c-Transform if and only if It Is 1-Lipschitz, and Then f^c = −fTextbook

Optimal transport compares two probability distributions by the least cost of moving one onto the other. When the ground cost is itself a distance, c(x,y)=d(x,y)c(x,y)=d(x,y)c(x,y)=d(x,y), the resulting quantity is the 1-Wasserstein distance W1\mathcal W_1W1​, also called the earth mover's distance. It is the transport distance most used in practice for comparing histograms, images and…

11 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimal TransportOptimization·Captain: mikedeng1

Computational Optimal Transport II: For a Distance Matrix D and p ≥ 1, W_p(a, b) = L_{D^p}(a, b)^{1/p} Is a Distance on the Probability SimplexTextbook

Comparing histograms is a basic operation in statistics, computer vision and machine learning: a bag of image descriptors, a word-frequency vector, a discretized density. When the bins carry a geometry (colors that are close to one another, words with related meanings), a comparison that ignores the geometry, such as an ℓp\ell^pℓp norm between the histogram…

10 thms5 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimal Transport+1·Captain: mikedeng1

Computational Optimal Transport III: Discrete Kantorovich Duality — L_C(a, b) Is the Maximum of ⟨f, a⟩ + ⟨g, b⟩ over Potentials with f ⊕ g ≤ CTextbook

Optimal transport between two histograms is a linear program: move mass aia_iai​ out of each source bin iii and deliver mass bjb_jbj​ to each target bin jjj at unit cost Ci,jC_{i,j}Ci,j​, as cheaply as possible. Its dual replaces the transport plan by a pair of price vectors and is the basis of most of the computational methods in G. Peyré and M. Cuturi's Computational Optimal…

10 thms5 active usersReviewed
🏆Completed
Machine LearningNumerical AnalysisOptimal Transport+1·Captain: mikedeng1

Computational Optimal Transport VIII: Sinkhorn's Scalings Contract by λ(K)² per Iteration in Hilbert's Projective MetricTextbook

Sinkhorn's algorithm is the standard method for computing entropically regularized optimal transport between two histograms. It is used throughout machine learning, statistics, imaging and graphics because each iteration is two matrix–vector products followed by entrywise divisions, which parallelize on GPUs and differentiate easily. The same iteration,…

19 thms5 active users
🏆Completed
Machine LearningOperations ResearchOptimal Transport+1·Captain: mikedeng1

Regularization via Mass Transportation II: Wasserstein-Robust Linear Regression Equals Empirical Loss plus a Dual-Norm PenaltyResearch Paper

Ordinary least squares and its robust relatives (least absolute deviations, Huber, ϵ\epsilonϵ-insensitive and quantile regression) fit a linear predictor by minimizing an average loss over the training sample. That average estimates the out-of-sample error poorly when the sample is small, and the usual fix is to add a regularization penalty such as a norm of…

15 thms5 active usersReviewed
🏆Completed
Complexity TheoryGraph TheoryLinear algebra+1·Captain: mikedeng1

Most Tensor Problems Are NP-Hard 2: Graph 3-Colorability Reduces to Tensor Bilinear Feasibility over the Reals and over the Complex NumbersResearch Paper

A matrix A∈Cn×nA \in \mathbb C^{n\times n}A∈Cn×n is singular exactly when the pair of linear systems x⊤A=0\mathbf x^\top A = 0x⊤A=0, Ay=0A\mathbf y = 0Ay=0 has a solution with both x\mathbf xx and y\mathbf yy nonzero, and this is decided in polynomial time by Gaussian elimination. The natural analogue for a 3-tensor replaces the two linear systems by three families of bilinear equations,…

25 thms5 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Proximal Algorithms I: A Point Minimizes f + g Exactly When It Is a Fixed Point of the Forward-Backward Operator x ↦ prox_λg(x − λ∇f(x))Research Paper

Many convex optimization problems combine a smooth loss with a term that is easy to handle through minimization but awkward to differentiate. A constraint can be represented by an indicator function that is zero on the feasible set and +∞+\infty+∞ outside it. A norm penalty can be finite yet nonsmooth. The proximal gradient method handles such objectives by…

11 thms5 active usersReviewed
🏆Completed
Complexity TheoryGraph TheoryLinear algebra+1·Captain: mikedeng1

Most Tensor Problems Are NP-Hard 1: Graph 3-Colorability Reduces to Deciding Whether 0 Is an Eigenvalue of a Rational 3-Tensor over the RealsResearch Paper

Eigenvalues of matrices are computable in polynomial time to any accuracy, and numerical linear algebra rests on that fact. Higher-order tensors appear in statistics (moment and cumulant tensors), signal processing, quantum information and polynomial optimization, and several notions of tensor eigenvalue were proposed for them, independently by Lim and by…

23 thms5 active usersReviewed
🏆Completed
CombinatoricsMachine Learning·Captain: mikedeng1

Online Learning and Online Convex Optimization 4: Finite Littlestone Dimension Gives Agnostic Online Regret 2√(Ldim·ln(eT/Ldim)·T)Research Paper

Online classification is the simplest model of learning from a stream: on every round a learner sees an instance, guesses its binary label, and is then told the truth. Cover's impossibility argument shows that against an adversary no deterministic learner can compete with even two fixed hypotheses, so two relaxations are studied. In the realizable case the…

8 thms5 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Hedging Inventory Risk Through Market Instruments I: Hedging Raises the Risk-Averse Newsvendor's Optimal Order QuantityResearch Paper

A retailer who orders a seasonal product before demand is known faces the newsvendor trade-off. Ordering too much leaves unsold stock, and ordering too little forgoes sales. A risk-neutral newsvendor orders a critical fractile of demand. A risk-averse one orders less, since inventory is a risky investment, and this reduction has been shown under constant…

11 thms5 active usersReviewed
🏆Completed
CombinatoricsGroup TheoryNumber Theory·Captain: mikedeng1

New Proofs of Plünnecke-type Estimates for Product Sets in Groups 1: In an Abelian Group, |A + B| ≤ α|A| Gives One Nonempty X ⊆ A with |X + hB| ≤ αʰ|X| for Every hResearch Paper

A basic question of additive combinatorics asks how a set grows under repeated addition. If a finite set AAA in an abelian group satisfies ∣A+B∣≤α∣A∣|A + B| \le \alpha |A|∣A+B∣≤α∣A∣ for some finite set BBB, how large can the iterated sumsets hB=B+⋯+BhB = B + \cdots + BhB=B+⋯+B be? Plünnecke's inequality gives the answer used throughout the subject: some nonempty part of AAA grows by at most a…

4 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingMarkov ChainOperations Research+1·Captain: mikedeng1

Optimality of (s, S) Policies in Inventory Models with Markovian Demand I: With Markov-Modulated Demand and Fixed Ordering Costs, a State-Dependent (s, S) Policy Is Optimal over a Finite HorizonResearch Paper

Single-item inventory theory asks how much stock to order each period when the order carries a fixed cost KKK on top of a per-unit cost and demand is random. With independent, identically distributed demand, Scarf (1960) showed that the optimal finite-horizon policy has the (s,S)(s,S)(s,S) form: when the stock falls below the reorder point sss, order up to the level SSS;…

20 thms5 active usersReviewed
🏆Completed
Dynamic ProgrammingLinear OptimizationOperations Research+1·Captain: mikedeng1

Analysis of Stochastic Dual Dynamic Programming Method: SDDP with Independently Subsampled Scenarios Finds an Optimal Policy of the SAA Problem in Finitely Many Iterations Almost SurelyResearch Paper

Multistage stochastic linear programs model sequential decisions under uncertainty: capacity and reservoir planning, hydro-thermal scheduling, inventory and asset–liability management. When the data process is stagewise independent, the problem decomposes by dynamic programming into one linear program per stage, coupled through expected cost-to-go functions.…

14 thms5 active usersReviewed
🏆Completed
Machine LearningProbabilityTheoretical Computer Science·Captain: mikedeng1

What Can We Learn Privately? II: Parity Functions Are Privately PAC Learnable from O(d log(1/β)/(εα)) ExamplesResearch Paper

Differential privacy (Dwork, McSherry, Nissim and Smith, 2006) requires a randomized algorithm's output distribution to change little when one individual's record is changed. PAC learning asks an algorithm to output, from i.i.d. labeled examples, a hypothesis whose error is small with high probability. Kasiviswanathan, Lee, Nissim, Raskhodnikova and Smith (a…

14 thms5 active usersReviewed
🏆Completed
Machine LearningProbabilityTheoretical Computer Science·Captain: mikedeng1

What Can We Learn Privately? I: The Exponential Mechanism Privately Agnostically Learns Any Finite Concept Class from O((ln|C| + ln(1/β))·max{1/(εα), 1/α²}) ExamplesResearch Paper

Many learning tasks run on data about people: medical records, purchase histories, survey answers. A learner whose output reveals too much about any one training example is unusable on such data, however accurate it is. Differential privacy (Dwork, McSherry, Nissim and Smith, 2006) makes "reveals too much" precise: changing one individual's record may…

10 thms5 active usersReviewed
🏆Completed
Algorithmic Game TheoryLinear algebraOperations Research·Captain: mikedeng1

Flows and Decompositions of Games: Harmonic and Potential Games 5: Every ϵ-Equilibrium of the Closest Potential Game Is an (ϵ + max_m 2α/√h_m)-Equilibrium of the Game, and ConverselyResearch Paper

Potential games (Monderer and Shapley, 1996) are the finite games whose unilateral payoff differences are all differences of a single function, the potential. They always have a pure Nash equilibrium, and many natural learning dynamics (best response, fictitious play, logit response) converge in them. Most games met in applications are not exactly potential…

19 thms5 active usersReviewed
🏆Completed
Algorithmic Game TheoryLinear algebraOperations Research·Captain: mikedeng1

Flows and Decompositions of Games: Harmonic and Potential Games 2: Harmonic Games Generically Have No Pure Nash EquilibriumResearch Paper

Finite games in strategic form are the basic model of interaction between self-interested agents in economics, engineering and computer science. Among them, potential games (Monderer and Shapley, 1996) are the class with the most tractable equilibrium behaviour: every finite potential game has a pure Nash equilibrium, and simple learning dynamics such as…

9 thms5 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraNumerical Analysis·Captain: mikedeng1

Low-rank Matrix Recovery via Iteratively Reweighted Least Squares Minimization 1: IRLS-M Converges to the Nuclear-Norm Minimizer Under the Strong Rank Null Space PropertyResearch Paper

Many data problems ask for a matrix of low rank from far fewer linear measurements than it has entries: matrix completion (recommender systems, where a few ratings of a large user–item table are observed), system identification, and quantum state tomography. Minimizing the rank under the measurement constraints is NP-hard in general. The standard convex…

19 thms5 active usersReviewed
🏆Completed
Formal VerificationTheoretical Computer Science·Captain: mikedeng1

Compositional Shape Analysis by Means of Bi-Abduction 2: With Precise Preconditions and Best Anti-Frames, the Canonical Precondition of an Action Sequence Is Its FootprintResearch Paper

Automatic program analyses for heap-manipulating code have to infer, for each procedure, a precondition describing the memory the procedure needs. Calcagno, Distefano, O'Hearn and Yang (J. ACM 2011) do this with bi-abduction: at a call site the analysis asks for an anti-frame MMM, the missing memory, and a frame, the memory left untouched, so that the current…

9 thms5 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraOptimization·Captain: mikedeng1

Guaranteed Minimum-Rank Solutions of Linear Matrix Equations via Nuclear Norm Minimization 1: If δ_5r < 1/10, Nuclear Norm Minimization Recovers Every Matrix of Rank at Most r ExactlyResearch Paper

Many problems in system identification, collaborative filtering, low-dimensional embedding and model reduction ask for the simplest matrix consistent with a set of linear observations, where "simplest" means "of least rank". Given a linear map A:Rm×n→Rp\mathcal A:\mathbb R^{m\times n}\to\mathbb R^pA:Rm×n→Rp and a vector b∈Rpb\in\mathbb R^pb∈Rp, the affine rank minimization problem is

11 thms5 active usersReviewed
PreviousPage 9 of 142Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5162497
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36415412
5NINickrobbins953286155
6VEvebis25800
7FIfizzyinc321725
8SHshivm17490
9SCShuze Chen9455324
10KMkmehltretter82895261

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