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.

1285 open missions

Missions

401–425 of 1285
Open1285Completed3527All4812
AnalysisLinear algebraProbability+1·Captain: mikedeng1

User-Friendly Tail Bounds for Sums of Random Matrices V: The Matrix Azuma Inequality for Adapted Sequences with Semidefinite Bounds on the Squared DifferencesResearch Paper

Sums of random matrices appear throughout numerical linear algebra, statistics, combinatorics and quantum information: randomized sketching and sparsification, covariance estimation, graph sparsifiers, and the analysis of random features all reduce to controlling the largest eigenvalue of a sum of random self-adjoint matrices. Scalar concentration…

10 thms3 active usersReviewed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Self-Scaled Barriers and Interior-Point Methods for Convex Programming IV: The Predictor-Corrector Path-Following Scheme Keeps π(τ, x) ≤ 1/4 and Multiplies τ by at Least 1 + 3/(8√ν + 2)Research Paper

Interior-point methods solve linear, second-order cone and semidefinite programs by following a smooth curve through the interior of the feasible region. Nesterov and Nemirovskii (1994) showed that the right object to build such methods on is a self-concordant barrier for the cone, and that the number of Newton steps needed by a path-following method is…

16 thms3 active usersReviewed
Control TheoryDynamical SystemsGraph Theory+1·Captain: mikedeng1

Synchronization and Transient Stability in Power Networks and Nonuniform Kuramoto Oscillators 2: λ₂(L(P_ij cos φ_ij)) > λ_critical Gives Phase Cohesiveness and Exponential Frequency SynchronizationResearch Paper

Transient stability of a power grid asks whether the generators of the network return to synchronous operation after a large disturbance such as a fault or a line trip. In the classical network-reduced model the rotor angles obey second-order swing equations, and stability certificates usually come from energy functions evaluated numerically. Dörfler and…

14 thms3 active usersReviewed
Harmonic AnalysisProbabilityTheoretical Computer Science·Captain: mikedeng1

Optimal Inapproximability Results for MAX-CUT and Other 2-Variable CSPs? 3: Low-Influence Functions Have Level-One Fourier Weight at Most 2/π + CδResearch Paper

Fourier analysis of functions on the discrete cube {−1,1}n\{-1,1\}^n{−1,1}n is the main tool behind tight inapproximability results under the Unique Games Conjecture. In the MAX-CUT reduction of Khot, Kindler, Mossel and O'Donnell (SIAM J. Comput. 2007), soundness rests on the Majority Is Stablest theorem: among bounded functions in which no coordinate has large…

7 thms3 active usersReviewed
Dynamic ProgrammingMarkov ChainOperations Research+1·Captain: mikedeng1

Optimality of (s, S) Policies in Inventory Models with Markovian Demand II: In the Nonstationary Discounted Infinite-Horizon Problem, a State-Dependent (s, S) Policy Is OptimalResearch Paper

Periodic-review inventory models with a fixed ordering cost are the setting in which the (s,S)(s,S)(s,S) policy is optimal: when the stock falls below a reorder point sss, order up to a level SSS, otherwise order nothing. Scarf (1960) proved this for independent demands over a finite horizon by introducing KKK-convexity, and Iglehart (1963) extended it to the discounted…

11 thms3 active usersReviewed
Bandit AlgorithmsMachine LearningProbability+1·Captain: mikedeng1

Thompson Sampling: An Asymptotically Optimal Finite-Time Analysis: Bernoulli Thompson Sampling Has Regret (1+ε)Σ Δ_a(ln T + ln ln T)/K(μ_a, μ*) + CResearch Paper

Thompson Sampling is the oldest bandit algorithm: Thompson proposed it in 1933 for allocating patients between two treatments (Thompson 1933). It keeps a posterior distribution over the unknown mean reward of every action, draws one sample from each posterior, and plays the action whose sample is largest. It is simple, widely used, and in experiments…

17 thms3 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Martingale Proofs of Many-Server Heavy-Traffic Limits for Markovian Queues 1: The Centered and √n-Scaled M/M/∞ Queue Converges in D to an Ornstein–Uhlenbeck ProcessResearch Paper

Large service systems (call centers, hospital wards, cloud server pools) run with many servers, and for many of them no exact formula describes how the number of busy servers moves over time. Heavy-traffic limits replace such a system by a diffusion process that is easier to analyze. The many-server regime, in which the number of servers and the arrival…

23 thms3 active usersReviewed
Convex OptimizationLinear algebraMachine Learning+1·Captain: mikedeng1

Nuclear-Norm Penalization and Optimal Rates for Noisy Low-Rank Matrix Completion 2: If λ ≥ 3‖M‖∞ on a Linear Subspace, a Sharp Oracle Inequality with the Restricted Constant μ₅(A)Research Paper

Estimating a large matrix that is approximately low rank from a few noisy linear measurements is a basic problem of high-dimensional statistics. It covers matrix completion (recovering a ratings table from a small sample of entries), multi-task regression and quantum state tomography. The standard estimator penalizes the nuclear norm, the sum of the…

14 thms3 active usersReviewed
Machine LearningProbabilityTheoretical Computer Science·Captain: mikedeng1

What Can We Learn Privately? IV: Any ε-Local Algorithm Is Simulated by a Statistical Query Algorithm with O(t·e^ε) Expected Queries up to Statistical Difference βResearch Paper

In the local model of differential privacy, no trusted curator holds the data: each individual randomizes their own record before handing it to the analyst. This is the model of randomized response in survey statistics and of the privacy-preserving telemetry deployed by large software vendors. Kasiviswanathan, Lee, Nissim, Raskhodnikova and Smith, What Can…

9 thms3 active usersReviewed
Graph TheoryProbabilityStatistics·Captain: mikedeng1

Random Graphs with a Given Degree Sequence 3: With Probability 1 − C(L)n⁻² the β-Model MLE Exists, Is Unique, and Is Within C(L)√(log n/n) of βResearch Paper

Network data often come as a single observed graph, and the simplest summary of a graph is its degree sequence, the list of the numbers of neighbours of its vertices. A statistical model in which the degree sequence is a sufficient statistic is an exponential family on graphs, and the simplest such family is the β-model: each vertex iii carries a parameter …

10 thms3 active usersReviewed
Linear algebraNumerical AnalysisOptimization·Captain: mikedeng1

The Primal-Dual Active Set Strategy as a Semismooth Newton Method IV: Global Convergence for Small Perturbations of M-MatricesResearch Paper

Obstacle problems, contact problems and control-constrained optimal control problems lead, after discretization, to complementarity systems of the form "find y≤ψy \le \psiy≤ψ and λ≥0\lambda \ge 0λ≥0 with Ay+λ=fAy + \lambda = fAy+λ=f and λi(yi−ψi)=0\lambda_i(y_i - \psi_i) = 0λi​(yi​−ψi​)=0". The primal-dual active set strategy solves such systems by guessing which constraints are active, solving one linear…

10 thms3 active usersReviewed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Centralized and Competitive Inventory Models with Demand Substitution 3: Under Multivariate Normal Demand the Centralized Expected Profit Decreases in Every Demand CorrelationResearch Paper

A retailer that carries several substitutable products (brands of the same good, sizes of the same item) faces demands that are linked in two ways: a customer who finds the first-choice product out of stock may buy another one, and the first-choice demands themselves are statistically dependent. Inventory planners routinely assume multivariate normal demand…

9 thms3 active usersReviewed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Quantitative Stability in Stochastic Programming: The Method of Probability Metrics 3: Mixed-Integer Two-Stage Programs Are Hölder Stable in the Polyhedral DiscrepancyResearch Paper

Two-stage stochastic programs are solved with an approximation of the true distribution of the random data: an empirical measure, a scenario tree, or a discretization. Whether the computed decisions mean anything depends on how the optimal value and the solution set react when the underlying probability measure is replaced by a nearby one, and on which…

15 thms3 active usersReviewed
Algorithmic Game TheoryDynamical SystemsLinear algebra·Captain: mikedeng1

Uncoupled Dynamics Do Not Lead to Nash Equilibrium 1: Near the Two-Player Unit-Disk Game Γ₀ of Section II, No Uncoupled Dynamic Is Nash-ConvergentResearch Paper

Learning in games asks whether players who adjust their strategies over time, by simple rules, end up at a Nash equilibrium. Many adaptive dynamics share one informational feature: each player's adjustment depends on the current play and on that player's own payoff function, but not on the payoffs of the others. Hart and Mas-Colell (AER 2003) call such…

14 thms3 active usersReviewed
Numerical AnalysisOptimization·Captain: mikedeng1

The Primal-Dual Active Set Strategy as a Semismooth Newton Method I: Local Superlinear Convergence for P-Matrix Complementarity ProblemsResearch Paper

Many problems in optimization and in the discretization of partial differential equations reduce to a linear complementarity problem with an obstacle: find y,λ∈Rny, \lambda \in \mathbb{R}^ny,λ∈Rn with

8 thms3 active usersReviewed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Designing a Call Center with Impatient Customers II: In the Halfin–Whitt Regime the Scaled Erlang-A Queue Converges to a Diffusion with Piecewise-Linear DriftResearch Paper

Telephone call centers are large service systems: hundreds of agents answer callers who wait in a queue and hang up when their patience runs out. Staffing them is a trade-off between the cost of agents and the quality of service, and in large centers both the efficiency (agents busy almost all the time) and the service level (most callers answered almost…

9 thms3 active usersReviewed
Markov ChainProbabilityStochastic Systems·Captain: mikedeng1

The Two-Parameter Poisson–Dirichlet Distribution Derived from a Stable Subordinator 5: PD(α, θ) Is a Y_1^θ-Tilt of Independent beta(θ + nα, 1) Ratios, and (Y_n) Is a Markov ChainResearch Paper

The two-parameter Poisson–Dirichlet distribution PD(α,θ)\mathrm{PD}(\alpha,\theta)PD(α,θ) is a law on decreasing sequences V1≥V2≥⋯>0V_1 \ge V_2 \ge \cdots > 0V1​≥V2​≥⋯>0 with ∑nVn=1\sum_n V_n = 1∑n​Vn​=1. It describes the ranked frequencies of species in Bayesian nonparametric models (the Pitman–Yor process), the ranked lengths of excursions of Bessel processes and bridges, and the ranked cycle or block…

15 thms3 active usersReviewed
Machine LearningMarkov ChainProbability+1·Captain: mikedeng1

An Analysis of Temporal-Difference Learning with Function Approximation 2: For Every Sampling Distribution q and 5/6 < α < 1, Off-Line q-Sampled TD(0) Can Diverge in ExpectationResearch Paper

Temporal-difference learning estimates the future cost of a system from observed transitions. In a Markov model, a state has a distribution of possible successors and each transition carries a cost. An agent may approximate the future cost with a small number of basis functions rather than store one number per state. This is useful when the state set is…

9 thms3 active usersReviewed
Convex OptimizationOperations ResearchOptimization·Captain: mikedeng1

Primal-Dual Interior-Point Methods for Self-Scaled Cones II: The Functional-Proximity Predictor-Corrector Step Has α²/(1 − α) ≥ ω₁(Δ, κ)/ν and Boundedly Many Newton CorrectionsResearch Paper

Primal-dual interior-point methods are the standard algorithms for linear, second-order-cone and semidefinite programming. Their best-known variants keep the iterates in a narrow neighbourhood of the central path and take short or moderately long steps whose length is fixed in advance. Practical codes instead take long steps and recentre only when needed.…

25 thms3 active usersReviewed
Control TheoryOperations ResearchProbability+1·Captain: mikedeng1

Reflected Solutions of Backward SDE's, and Related Obstacle Problems for PDE's 2: With a Concave Coefficient, the Reflected BSDE Is the Value of a Minimax Optimal Stopping–Control ProblemResearch Paper

A backward stochastic differential equation (BSDE) prescribes the terminal value of an adapted process instead of its initial value. Pardoux and Peng (1990) proved existence and uniqueness for Lipschitz coefficients, and BSDEs have since become a standard tool in stochastic control, mathematical finance and the probabilistic treatment of semilinear PDEs. El…

13 thms3 active usersReviewed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Fast Rates for Support Vector Machines Using Gaussian Kernels 1: Under Tsybakov and Geometric Noise, Gaussian-Kernel SVMs Reach Excess Risk Cx²n^{−β+ε} with Probability 1 − e^{−x}Research Paper

Support vector machines classify observations by choosing a real-valued function from a reproducing kernel Hilbert space and using its sign as the predicted label. The Gaussian kernel is widely used because it gives a flexible class of functions, but that flexibility alone does not explain how quickly classification error approaches the best possible error…

11 thms3 active usersReviewed
Markov ChainOperations ResearchStochastic Systems·Captain: mikedeng1

Stability Properties of Constrained Queueing Systems and Scheduling Policies for Maximum Throughput in Multihop Radio Networks I: Policy π₀ Is Throughput-Optimal, C′ ⊂ C_π₀ ⊂ C ⊂ C̄′Research Paper

In a wireless multihop network, a switch, or a parallel computer, transmissions interfere: two links that share a receiver, or two crossbar paths that share a port, cannot be active in the same time slot. The scheduler must choose, slot by slot, a set of links that may operate together and decide which traffic each one carries. The basic question is which…

9 thms3 active usersReviewed
AnalysisOperations ResearchOptimization+1·Captain: mikedeng1

Dynamic Scheduling with Convex Delay Costs: The Generalized cμ Rule: Policies Equalizing the Indices μ_k c_k(W_k/ρ_k) Attain the Heavy-Traffic Lower Bound on Cumulative Delay CostResearch Paper

A single server shared by several classes of jobs must decide, at every moment, which class to work on. When each class kkk incurs a linear delay cost ckc_kck​ per unit of waiting time and needs mean service time 1/μk1/\mu_k1/μk​, the classical cμc\mucμ rule (serve the waiting class with the largest ckμkc_k\mu_kck​μk​) minimizes expected cost in many settings, from the M/G/1 queue to…

16 thms3 active usersReviewed
Machine LearningOptimizationProbability+1·Captain: mikedeng1

Learning Models with Uniform Performance via Distributionally Robust Optimization 1: The Plug-In Cressie–Read Robust Risk Concentrates at Rate n^(−1/(k*∨2))·√(t + log n) (Theorem 2)Research Paper

A model trained to minimize its average loss EP0[ℓ(θ;X)]\mathbb E_{P_0}[\ell(\theta;X)]EP0​​[ℓ(θ;X)] can perform poorly on subpopulations that are rare under the training distribution P0P_0P0​. Distributionally robust optimization replaces the average loss by its worst case over all distributions QQQ close to P0P_0P0​ in an fff-divergence, which upweights the tail of the loss and controls…

12 thms3 active usersReviewed
Convex OptimizationInformation TheoryOptimization+2·Captain: mikedeng1

I-Divergence Geometry of Probability Distributions and Minimization Problems 2: Under Moment Constraints the I-Projection Exists at Every Interior Point and Has Exponential-Family DensityResearch Paper

Given a reference probability distribution RRR and a set E\mathcal EE of probability distributions, the minimum discrimination information problem asks for the member of E\mathcal EE closest to RRR in Kullback–Leibler divergence. It is the basis of Kullback's information-theoretic approach to statistics (Kullback 1959), of the maximum-entropy principle of…

10 thms3 active usersReviewed
PreviousPage 17 of 52Next

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