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

1576–1600 of 3527
Open1285Completed3527All4812
🏆Completed
Algorithmic Game Theory·Captain: carlok

WorstCaseEq I: Theorem 3Research Paper

Load balancing on identical parallel links is the example Koutsoupias and Papadimitriou used to define the price of anarchy: the ratio of the social cost of a Nash equilibrium to the social optimum (Koutsoupias–Papadimitriou 2009). Theorem 3 of the journal version is the two-link case. It is the first sharp bound in that paper, and the later two-speed bound…

5 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchProbability+1·Captain: mikedeng1

Matroid Prophet Inequalities 2: On an Intersection of p Matroids, the Summed-Threshold Algorithm Earns at Least 1/(4p−2) of the Expected OptimumResearch Paper

A prophet inequality compares a gambler who sees independent random rewards one at a time, and must accept or reject each on arrival, with a prophet who sees all rewards in advance. The classical inequality of Krengel, Sucheston and Garling (1977–78, as cited in the paper) says that when only one reward may be kept, a single threshold rule earns at least…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationNumerical AnalysisOperations Research+1·Captain: mikedeng1

Efficiency of Coordinate Descent Methods on Huge-Scale Optimization Problems 1: Random Block Coordinate Descent RCDM(α, x₀) Has Expected Error at Most 2·S_α·R²_{1−α}(x₀)/(k + 4)Research Paper

Many large optimization problems arising in machine learning, statistics and network analysis have so many variables that computing a single full gradient is already expensive, while a single partial derivative, or a gradient with respect to a small block of variables, is cheap. Coordinate descent methods exploit this: at each iteration they update one…

11 thms3 active usersReviewed
🏆Completed
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: mikedeng1

Distributed Verification and Hardness of Distributed Approximation: Simulation Theorem — Time R < (dᵖ−1)/2 on G(Γ,d,p) with B-Bit Messages Gives an ε-Error Two-Party Protocol with 2dpB·R BitsResearch Paper

In distributed computing, many graph problems (minimum spanning tree, shortest paths, connectivity checks) are solved by processors that sit at the vertices of the input network and communicate only along its edges. When every edge can carry only a few bits per round, the number of rounds an algorithm needs can be far larger than the network's diameter.…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

A Stochastic Gradient Method with an Exponential Convergence Rate for Finite Training Sets 2: For n ≥ 8L/μ, SAG with Step 1/(2nμ) after an SG Warm Start Converges at Rate (1 − 1/(8n))ᵏResearch Paper

Many problems in machine learning are finite-sum problems: minimize the average of nnn loss functions, one per training example,

18 thms3 active usersReviewed
🏆Completed
CombinatoricsGroup Theory·Captain: mikedeng1

New Proofs of Plünnecke-type Estimates for Product Sets in Groups 2: If |BB| ≤ α|B| and |BbB| ≤ β|B| for All b ∈ B, Then |Bʰ| ≤ α^(8h−17) β^(h−2) |B| for Every h > 2Research Paper

Plünnecke-type inequalities turn information about a set and one product (or sum) of it into bounds on all of its iterated products. In an abelian group, Plünnecke's theorem (Plünnecke 1970) and its extension by Ruzsa say that ∣A+A∣≤α∣A∣|A + A| \le \alpha|A|∣A+A∣≤α∣A∣ implies ∣hA∣≤αh∣A∣|hA| \le \alpha^h |A|∣hA∣≤αh∣A∣ for every hhh. Such bounds are a basic tool in additive combinatorics, and their…

9 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization+1·Captain: mikedeng1

Making Gradient Descent Optimal for Strongly Convex Stochastic Optimization 3: SGD with Full Averaging Suffers an Ω(log(T)/T) Rate on a Non-Smooth Strongly Convex ProblemResearch Paper

Stochastic gradient descent (SGD) is the standard first-order method for stochastic convex optimization and for training linear predictors on large data sets: at each step it queries a noisy subgradient of the objective, takes a step against it and projects back onto the feasible set. When the objective is strongly convex, the classical online-learning…

7 thms3 active usersReviewed
🏆Completed
Number TheoryNumerical AnalysisOptimization·Captain: mikedeng1

Nonsmooth Optimization via Quasi-Newton Methods III: The Secant Method on |x| Generates the Alternating Binary Expansion of x₀Research Paper

Quasi-Newton methods such as BFGS were designed for smooth objectives, yet in practice they are routinely run on nonsmooth functions and they often work well there: on many nonsmooth problems the iterates converge to a minimizer at a linear rate, measured against the total number of function evaluations. Lewis and Overton (Math. Program. 141 (2013) 135–163)…

7 thms3 active usersReviewed
🏆Completed
CombinatoricsGroup Theory·Captain: mikedeng1

New Proofs of Plünnecke-type Estimates for Product Sets in Groups 3: If |AB| ≤ α|A|, |AbB| ≤ β|A| for b ∈ B and |A| ≤ γ|B|, Some S ⊆ A Has |SBʰ| ≤ α^(8h−9) β^(h−1) γ^(4h−5) |S| for h > 1Research Paper

Plünnecke–Ruzsa inequalities bound the size of iterated sumsets: if AAA and BBB are finite subsets of an abelian group with ∣A+B∣≤α∣A∣|A+B| \le \alpha|A|∣A+B∣≤α∣A∣, then ∣hB∣≤αh∣A∣|hB| \le \alpha^h|A|∣hB∣≤αh∣A∣ for every hhh, where hB=B+⋯+BhB = B + \dots + BhB=B+⋯+B. They are a basic tool of additive combinatorics, used in Freiman-type structure theorems, sum–product estimates and the study of approximate groups.…

6 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

Nonsmooth Optimization via Quasi-Newton Methods I: With an Exact Line Search on the Euclidean Norm in ℝ², Quasi-Newton Iterates Converge Q-Linearly at Rate 1/2, Turning by π/3Research Paper

Quasi-Newton methods, BFGS above all, are the standard tool for smooth unconstrained minimization. They are also used directly on nonsmooth functions, where in practice they often converge to stationary points with linearly converging function values; the paper documents applications such as the design of low-order controllers (Lewis–Overton 2013, abstract…

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

Quantity Flexibility Contracts and Supply Chain Performance 1: Under the Minimum Commitment Policy a Flex Node With At Least Its Customer's Flexibility Keeps Zero InventoryResearch Paper

Manufacturers and their suppliers rarely trade on fixed orders. A buyer sends a rolling schedule of intended purchases for the coming periods and revises it every period as its own forecasts change. Left unconstrained, such revisions pass demand volatility up the supply chain and amplify it, the phenomenon studied as the bullwhip effect (Lee, Padmanabhan &…

6 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear algebraTheoretical Computer Science·Captain: mikedeng1

Spectral Sparsification of Graphs 3: Sparsifying the Contraction and Pulling It Back Approximates a Graph with Heavy Intra-Part Edges to Within (1+ε)(1+1/c)²Research Paper

A spectral sparsifier of a weighted graph GGG is a graph G~\widetilde GG on the same vertices, with few edges, whose Laplacian quadratic form is within a factor σ\sigmaσ of that of GGG on every vector. Spielman and Teng introduced the notion in their work on nearly-linear-time solvers for symmetric diagonally dominant linear systems (Spielman–Teng 2004; arXiv:0808.41…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationLinear algebraOperations Research+1·Captain: mikedeng1

On the Rank of Extreme Matrices in Semidefinite Programs and the Multiplicity of Optimal Eigenvalues: If m > k(n − k), Extreme Optima of Affine EV_k Have λ_k = λ_{k+1} with Multiplicity ≥ n − τResearch Paper

Minimizing the sum of the kkk largest eigenvalues of a symmetric matrix that depends affinely on parameters is a basic problem of eigenvalue optimization (survey: A. S. Lewis and M. L. Overton, Eigenvalue optimization, Acta Numerica 5, 1996, doi:10.1017/S0962492900002646). Its objective is convex, and fkf_kfk​ is differentiable at BBB exactly when …

14 thms3 active usersReviewed
🏆Completed
AlgebraGroup TheoryTheoretical Computer Science·Captain: mikedeng1

New Techniques for Noninteractive Zero-Knowledge 4: The Decisional-Linear Commitment Is Perfectly Binding and Extractable, with a Perfectly Sound, Witness-Indistinguishable 0/1 ProofResearch Paper

A non-interactive zero-knowledge (NIZK) proof lets a prover convince a verifier that a statement is true by sending a single message, without revealing why it is true. Groth, Ostrovsky and Sahai (J. ACM 59(3), 2012) gave NIZK proofs for Circuit SAT of size O(∣C∣k)O(|C|k)O(∣C∣k) for a circuit CCC and security parameter kkk, the first perfect NIZK arguments for all of NP, and…

13 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

A Single-Item Inventory Model for a Nonstationary Demand Process: With Adaptive Base-Stock Control at Two Stages, Upstream Inventory Is N(y₀, σ²∑_{i<K}(1+(L+i)α)²)Research Paper

Classical safety-stock formulas assume that demand is stationary: independent and identically distributed around a fixed mean. Many products do not behave that way. Their demand level drifts, and the forecast has to follow it. Graves (A single-item inventory model for a nonstationary demand process, Manuf. Serv. Oper. Manag. 1(1):50–61, 1999) works out what…

12 thms3 active usersReviewed
🏆Completed
Group TheoryNumber TheoryTheoretical Computer Science·Captain: mikedeng1

New Techniques for Noninteractive Zero-Knowledge 3: The Subgroup-Decision (BGN) Commitment Is Perfectly Binding and Extractable, with a Perfectly Sound, Witness-Indistinguishable 0/1 ProofResearch Paper

A non-interactive zero-knowledge (NIZK) proof lets a prover convince a verifier that a statement is true by sending a single message, without revealing why it is true. NIZK proofs are a basic building block of public-key cryptography: chosen-ciphertext secure encryption, signature schemes and secure multi-party computation all use them. Groth, Ostrovsky and…

13 thms3 active usersReviewed
🏆Completed
Graph TheoryLinear algebraProbability+1·Captain: mikedeng1

Spectral Sparsification of Graphs 1: Sampling Each Edge of a High-Conductance Graph with Probability min(1, Υ/min(dᵢ, dⱼ)) Gives a (1+ε)-Spectral Approximation with Few EdgesResearch Paper

A spectral sparsifier of a graph is a much sparser weighted graph whose Laplacian quadratic form is within a factor σ\sigmaσ of the original on every vector. Spielman and Teng introduced the notion in Spectral Sparsification of Graphs as a strengthening of the cut sparsifiers of Benczúr and Karger: a spectral sparsifier preserves every cut, and in addition…

13 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·Captain: mikedeng1

A Note on Probability Distributions with Increasing Generalized Failure Rates II: For IGFR X with Support (α, ∞) and g(ξ) → κ, E[Xⁿ] Is Finite iff κ > nResearch Paper

Many models in operations management and economics need the demand or valuation distribution to be regular in some way, so that an optimal price, order quantity or contract is unique. Pricing a service to one customer whose valuation XXX has survival function Φˉ\bar\PhiΦˉ is a typical example. The seller maximizes p Φˉ(p)p\,\bar\Phi(p)pΦˉ(p). The first-order condition is …

14 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchTheoretical Computer Science·Captain: mikedeng1

AdWords and Generalized On-line Matching I: The Tradeoff Algorithm with ψ_k(i) = Σ_{j≥i} y*_j Is (1 − 1/e)-Competitive as k → ∞ When Bids Are SmallResearch Paper

Search engines sell advertising space query by query. Each advertiser states a bid for each keyword and a daily budget; queries arrive one at a time, and each must be assigned to an advertiser immediately, without knowledge of the queries still to come. The revenue-maximizing assignment of the day can only be computed offline. The adwords problem asks how…

9 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryOperations Research·Captain: mikedeng1

Basic Packing of Arborescences: A Digraph with Roots Has an M-Basic Packing of Arborescences iff π Is M-Independent and D Is M-ConnectedResearch Paper

Packing arc-disjoint arborescences is one of the basic tractable problems of combinatorial optimization. Edmonds' branching theorem (1973) says that a digraph D=(V,A)D=(V,A)D=(V,A) contains kkk arc-disjoint spanning arborescences rooted at a vertex rrr if and only if every non-empty vertex set X⊆V∖rX\subseteq V\setminus rX⊆V∖r is entered by at least kkk arcs. Its undirected counterpart…

12 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization+1·Captain: mikedeng1

Sample Size Selection in Optimization Methods for Machine Learning 1: With Batch Sizes n_k ≥ a^k, Dynamic Batch Steepest Descent Converges Linearly in Expectation, E[J(w_k) − J(w*)] ≤ Cρ^kResearch Paper

Training a model in machine learning means minimizing an expected loss over a data distribution, using a finite sample from it. Two families of methods dominate. Stochastic gradient methods step along the gradient of the loss at one data point: each step is cheap, but the noise forces small steps and many sequential iterations. Batch methods average the…

10 thms3 active usersReviewed
🏆Completed
Mathematical LogicTheory of Computation·Captain: mikedeng1

On the (Im)possibility of Obfuscating Programs 1: A Decidable Promise Problem Closed under Functional Equivalence Is Decided by a Simulator Given Only Oracle Access to ⟨M⟩ and the Size 1^|M|Research Paper

Program obfuscation asks for a compiler that turns a program into one computing the same function while revealing nothing beyond what black-box access to the function reveals. Barak, Goldreich, Impagliazzo, Rudich, Sahai, Vadhan and Yang (J. ACM 59(2), 2012; conference version CRYPTO 2001) showed that this "virtual black box" notion cannot be achieved in…

8 thms3 active usersReviewed
🏆Completed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

Sample Size Selection in Optimization Methods for Machine Learning 2: Steepest Descent with Gradient Error ‖g_k − ∇J(w_k)‖ ≤ θ‖g_k‖ Contracts J by 1 − βλ/L per StepResearch Paper

Training a machine-learning model usually means minimizing an expected or empirical loss J(w)J(w)J(w) over parameters w∈Rmw \in \mathbb{R}^mw∈Rm. Exact gradients of such objectives are expensive, because each one requires a pass over the whole data set; practical methods replace ∇J(wk)\nabla J(w_k)∇J(wk​) by a cheaper approximation gkg_kgk​, for instance a gradient computed on a subsample.…

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

On Augmented Lagrangian Methods with General Lower-Level Constraints II: Feasible Limit Points Satisfying CPLD Are KKT PointsResearch Paper

Augmented Lagrangian methods are among the standard ways to solve smooth nonlinear programs. They replace a constrained problem by a sequence of subproblems in which some constraints are moved into the objective through a penalty term and multiplier estimates. The method of Andreani, Birgin, Martínez and Schuverdt (SIAM J. Optim. 18(4), 2007) is the theory…

7 thms3 active usersReviewed
🏆Completed
Numerical AnalysisOptimization·Captain: mikedeng1

On the Convergence of the Proximal Algorithm for Nonsmooth Functions Involving Analytic Features: Bounded Proximal Sequences of Łojasiewicz Functions Have Finite Length and a Critical LimitResearch Paper

The proximal algorithm is the basic implicit scheme for minimizing a function fff: from the current point xkx^kxk it moves to a minimizer of fff plus a quadratic penalty on the distance travelled. For convex fff its convergence theory is classical (Martinet 1970, Rockafellar 1976). For nonconvex, nonsmooth fff the situation is different: descent and boundedness give…

12 thms3 active usersReviewed
PreviousPage 64 of 142Next

Top contributors

RankContributorAccepted solutionsSubmitted problems
1TItianyipeng5162497
2EYEyal199050327667
3MRmrfancypants41060
4WIWillR36535436
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