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

601–625 of 3527
Open1285Completed3527All4812
🏆Completed
Machine LearningProbabilityTheoretical Computer Science·Captain: mikedeng1

What Can We Learn Privately? III: An ε-Local Algorithm Simulates Any t-Query Statistical Query Algorithm from O(t log(t/β) b²/(ε²τ²)) SamplesResearch Paper

In the local model of differential privacy, no trusted curator ever sees the raw data: each individual randomizes their own record before handing it to the analyst. This is how private telemetry is collected in practice (randomized response and its descendants), and it raises a basic question: which learning tasks remain possible when the learner only sees…

9 thms4 active usersReviewed
🏆Completed
OptimizationTheoretical Computer Science·Captain: marwahaha

Additive hardness and unbounded configuration gaps in bin packingOpen Problem

Configuration linear programs relax bin packing by allowing fractional combinations of feasible bins. The mission asks whether the integral optimum can stay within any universal additive constant of this relaxation. The source manuscript presents the surrounding research claim.

12 thms4 active usersReviewed
🏆Completed
AnalysisProbabilityRandom Matrix Theory·Captain: mikedeng1

Phase Transition of the Largest Eigenvalue for Nonnull Complex Sample Covariance Matrices 1: Spikes at or below 1+γ⁻¹ Give M^{2/3} Fluctuations of the Largest Eigenvalue with Limit F_kResearch Paper

Sample covariance matrices are the basic object of multivariate statistics: principal component analysis, factor models and signal detection all start from the eigenvalues of S=1M∑k=1My⃗ky⃗k ∗S=\frac1M\sum_{k=1}^M\vec y_k\vec y_k^{\,*}S=M1​∑k=1M​y​k​y​k∗​ built from MMM observations of NNN variables. When NNN is comparable to MMM, the largest eigenvalue λ1\lambda_1λ1​ of SSS is no longer a consistent…

27 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryLinear algebraOperations Research·Captain: mikedeng1

Flows and Decompositions of Games: Harmonic and Potential Games 1: Every Finite Game Decomposes Uniquely into Potential, Harmonic and Nonstrategic ComponentsResearch Paper

Potential games (Monderer and Shapley, 1996) are the finite games whose incentives are captured by a single function on strategy profiles: every unilateral change of strategy changes the deviator's payoff by exactly the change of a common potential. They have pure Nash equilibria, and natural learning dynamics such as better-reply and fictitious play…

13 thms4 active usersReviewed
🏆Completed
Convex OptimizationOptimization·Captain: mikedeng1

Rank-Sparsity Incoherence for Matrix Decomposition: If μ(A⋆)ξ(B⋆) < 1/6, ℓ1 + Nuclear-Norm Minimization Uniquely Recovers the Sparse and Low-Rank ComponentsResearch Paper

Many data matrices are, to a good approximation, the sum of a sparse matrix (few nonzero entries) and a low-rank matrix. In system identification the low-rank part models a system of small order and the sparse part a system with sparse impulse response; in statistics the same structure appears in latent-variable graphical models, where a sparse inverse…

16 thms4 active usersReviewed
🏆Completed
Convex OptimizationLinear OptimizationOperations Research·Captain: mikedeng1

Retailer-Supplier Flexible Commitments Contracts: A Robust Optimization Approach: With Box Demand Uncertainty the Min-Max RSFC Problem Has the Same Optimal Value on the Extreme DemandsResearch Paper

In a flexible commitments contract a retailer announces, before a selling horizon starts, a vector of planned orders (commitments) to its supplier, who uses them to plan capacity. During the horizon the retailer may deviate from the commitments, but pays penalties for each deviation and for changes between successive commitments. Such contracts were studied…

13 thms4 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Overbooking with Substitutable Inventory Classes: With Semigroup Survivals the Expected Net Revenue Is Componentwise Concave and Submodular in the Overbooking LevelsResearch Paper

Airlines, hotels and car-rental firms sell reservations ahead of service, and a fraction of those reservations cancel or do not show up. Overbooking — accepting more reservations than there is capacity — recovers revenue that cancellations would otherwise destroy, at the risk of denying service to some customers. In practice inventory is often substitutable:…

12 thms4 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

On Implementing a Primal-Dual Interior-Point Method for Conic Quadratic Optimization IV: The Nesterov–Todd Scaling of a Quadratic or Rotated Quadratic Cone Is W = −Q + (e₁ + w)(e₁ + w)ᵀ/(1 + w₁)Research Paper

Conic quadratic (second-order cone) programs are solved in practice by primal-dual interior-point methods. Each iteration solves a Newton system for the central-path equations, and for non-polyhedral cones that system is only guaranteed to be well posed after the problem is scaled: the primal point xxx and the dual slack sss are transformed by a matrix ΘW\Theta WΘW…

15 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryConvex OptimizationOperations Research+1·Captain: mikedeng1

How Bad is Selfish Routing? 2: With Linear Latency Functions the Cost of a Nash Flow Is at Most 4/3 Times the Optimal CostResearch Paper

In a road or communication network, each user picks a route to minimize its own delay, without regard to the delay it imposes on others. The outcome is an equilibrium that is in general not socially optimal: Braess's paradox shows that adding a road can make every user worse off, and Pigou's two-link example shows that selfish users can incur a third more…

15 thms4 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

Pegasos: Primal Estimated Sub-Gradient Solver for SVM: Mini-Batch Pegasos Has Average Instantaneous Objective Within c(1+ln T)/(2λT) of the SVM Optimum'sResearch Paper

The support vector machine (SVM) is a linear classifier trained by minimising a regularised hinge loss. For training sets with millions of examples, solving the SVM problem to high accuracy by interior-point or dual decomposition methods is too slow, and what is needed is an algorithm whose cost per iteration does not grow with the number of examples. Pegaso…

15 thms4 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion 2: With Random Objective, Z(x) = Z_D(x) = Z_DD(x) and Moment-Matching Distributions Attain Z(x) AsymptoticallyResearch Paper

Two-stage stochastic linear programming chooses a first-stage decision xxx before a random parameter is revealed and pays an optimal second-stage (recourse) cost afterwards. The classical model fixes the distribution of the random parameter. In practice it is rarely known beyond a few moments, and a decision maker who is averse to risk does not evaluate the…

14 thms4 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion 3: With Random Right-Hand Side and Known Dual Extreme Points, the Problem Equals the Semidefinite Program (14)Research Paper

Two-stage stochastic linear programs model a decision xxx taken before uncertainty is revealed, followed by a corrective recourse action once it is. The classical model needs the full probability distribution of the uncertain data, which in practice is rarely known; often only estimates of the mean and the second moments are available, and the computed plan…

11 thms4 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research+1·Captain: mikedeng1

Convex Quadratic and Semidefinite Programming Relaxations in Scheduling IV: A ρ-Approximate Max-m-Cut Gives a (ρ + m(1 − ρ))-Approximate Schedule for Pm | | Σ wⱼCⱼResearch Paper

Scheduling jobs on identical parallel machines to minimize the total weighted completion time ∑jwjCj\sum_j w_jC_j∑j​wj​Cj​, the problem P ∣ ∣∑wjCjP\,|\,|\sum w_jC_jP∣∣∑wj​Cj​, is one of the basic NP-hard problems of machine scheduling. On a single machine it is solved by Smith's ratio rule (Smith 1956); with several machines the only hard decision is which jobs share a machine. Section 6 of…

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

On the Rate of Convergence of Optimal Solutions of Monte Carlo Approximations of Stochastic Programs 2: At a Sharp Minimum the SAA Problem Fails to Be Exact with Exponentially Small ProbabilityResearch Paper

The sample average approximation (SAA) method replaces an expectation in a stochastic program by the average over a random sample and solves the resulting deterministic problem. It is the standard way to solve two-stage stochastic linear programs with large or continuous scenario sets, and it underlies the stochastic counterpart and sample-path optimization…

11 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

The Sample Average Approximation Method for Stochastic Discrete Optimization 2: √N(v̂_N − v*) Converges in Distribution to the Minimum over S* of a Centered Gaussian VectorResearch Paper

Many decision problems in operations research have a finite set of alternatives and an objective that is an expectation: choose a configuration, a route or a stocking level xxx from a finite set S\mathcal SS to minimize the expected cost E G(x,W)\mathbb E\,G(x, W)EG(x,W), where WWW is random. When the expectation cannot be computed in closed form, the sample average…

7 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchOptimization+1·Captain: mikedeng1

Consumer Returns Policies and Supply Chain Performance 2: Under Consumer Returns, the Differentiated Buy-Back with b − l = s Coordinates the Supply Chain and Gives the Retailer a Share φResearch Paper

Retailers in many categories accept returns of products that are not defective: a consumer buys, learns whether the product suits them, and may send it back for a refund. Returns of this kind are a large cost item in retailing, and the refund a retailer offers is an operational decision on a par with its price and its stocking quantity. Xuanming Su, Consumer…

12 thms4 active usersReviewed
🏆Completed
Discrete GeometryHarmonic AnalysisProbability·Captain: mikedeng1

On Lattices, Learning with Errors, Random Linear Codes, and Cryptography 2: For r ≥ √2·η_ε(L), ε ≤ 1/10, a Discrete Gaussian Sample Lies Outside Any Proper Subspace with Probability ≥ 1/10Research Paper

Regev's paper (J. ACM 56(6), Article 34, 2009) introduces the learning with errors (LWE) problem and shows that solving it is at least as hard, for quantum algorithms, as approximating standard worst-case lattice problems such as the shortest independent vectors problem (SIVP) and GapSVP. LWE is the basis of most lattice-based public-key cryptography,…

12 thms4 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Models for Minimax Stochastic Linear Optimization Problems with Risk Aversion 1: With Random Objective, the Risk-Averse Minimax Problem Equals the Semidefinite Program (7)Research Paper

Two-stage stochastic linear programs choose a first-stage decision xxx before a random parameter is revealed and a recourse decision www afterwards. The classical model assumes the distribution of the random data is known. In practice it is estimated, and often only its first two moments are trusted. The minimax (distributionally robust) approach hedges against…

13 thms4 active usersReviewed
🏆Completed
Convex OptimizationOperations ResearchOptimization+1·Captain: mikedeng1

Convex Quadratic and Semidefinite Programming Relaxations in Scheduling I: Randomized Rounding of the Convex Quadratic Relaxation (CQP′) Is Within 3/2 for R | | Σ wⱼCⱼResearch Paper

Scheduling jobs on unrelated parallel machines to minimize the total weighted completion time, the problem written R ∣ ∣∑wjCjR\,|\,|\sum w_jC_jR∣∣∑wj​Cj​ in the three-field notation, is one of the basic NP-hard models of machine scheduling. Each job may take a different time on each machine, as when heterogeneous processors, plants or crews serve the same pool of tasks, and…

12 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Conditional Value-at-Risk for General Loss Distributions: β-CVaR Is min_α F_β(x, α), Attained on the Interval from β-VaR to Upper β-VaRResearch Paper

Financial institutions, insurers and engineers who manage the risk of a decision describe it by a statistic of the loss distribution that the decision induces. The value-at-risk (VaR) at confidence level β\betaβ, the β\betaβ-quantile of the loss, became an industry and regulatory standard in the 1990s, but it is not subadditive and behaves erratically as a…

9 thms4 active usersReviewed
🏆Completed
Dynamical SystemsOperations ResearchStochastic Systems+1·Captain: mikedeng1

The Power of Two Choices in Randomized Load Balancing I: In the Limiting Supermarket System the Expected Time Converges to T_d(λ) = Σ λ^((d^i−d)/(d−1))Research Paper

Randomized load balancing asks how much a dispatcher gains from a little information. In the supermarket model, jobs arrive at nnn servers and each job inspects a few servers chosen at random before joining one. With one random choice every server is an independent M/M/1 queue, and the expected time a job spends in the system is 1/(1−λ)1/(1-\lambda)1/(1−λ) at load λ\lambdaλ.…

8 thms4 active usersReviewed
🏆Completed
Algorithmic Game TheoryMachine LearningProbability·Captain: mikedeng1

A Simple Adaptive Procedure Leading to Correlated Equilibrium 2: Playing an Invariant Vector of the Regret Matrix (3.1) Drives Every Regret R_t(j,k) to Zero Almost SurelyResearch Paper

A correlated equilibrium (Aumann, 1974) is a probability distribution over the strategy profiles of a game such that no player gains by deviating from the strategy it recommends. It is the natural solution concept for repeated play by adaptive agents, because the set of correlated equilibria is a polytope described by linear inequalities and, as Hart and…

9 thms4 active usersReviewed
🏆Completed
Harmonic AnalysisProbabilityTheoretical Computer Science·Captain: mikedeng1

On Lattices, Learning with Errors, Random Linear Codes, and Cryptography 1: A Discrete Gaussian on L + u Plus Continuous Gaussian Noise ν_s Is Within Statistical Distance 4ε of ν_t, t = √(r² + s²)Research Paper

The learning with errors (LWE) problem underlies most of post-quantum public-key cryptography. Its hardness rests on Regev's reduction from worst-case lattice problems to LWE (Regev, J. ACM 2009). The reduction is iterative: it repeatedly turns samples of a discrete Gaussian on a lattice into samples of a narrower one. Its classical step, Lemma 3.11, needs…

11 thms4 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Revenue Management Without Forecasting or Optimization: An Adaptive Algorithm for Determining Airline Seat Protection Levels: Fill-Event Updates Converge to the Optimal Protection LevelsResearch Paper

Airlines sell seats on a single flight in several fare classes. Discount classes book first, so the carrier must decide how many seats to protect for later, higher-paying passengers. The classical answer, from Littlewood's rule for two classes to the nested optimality conditions of Brumelle and McGill (1993), computes optimal protection levels from a…

12 thms4 active usersReviewed
🏆Completed
Number TheoryProbabilityTheoretical Computer Science·Captain: mikedeng1

On Lattices, Learning with Errors, Random Linear Codes, and Cryptography 5: If Every χ^⋆k Is Below ⌊p/2⌋/2 with Probability > 1 − δ, the Cryptosystem Decrypts Correctly with Probability ≥ 1 − δResearch Paper

Learning with errors (LWE) asks to recover a secret vector s∈Zpns \in \mathbb Z_p^ns∈Zpn​ from noisy inner products (ai,⟨ai,s⟩+ei)(a_i, \langle a_i, s\rangle + e_i)(ai​,⟨ai​,s⟩+ei​), where the aia_iai​ are uniform and the errors eie_iei​ are drawn from a narrow distribution χ\chiχ on Zp\mathbb Z_pZp​. Regev introduced the problem and showed that solving it is at least as hard as solving worst-case lattice problems…

5 thms4 active usersReviewed
PreviousPage 25 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