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

801–825 of 1285
Open1285Completed3527All4812
CombinatoricsGraph TheoryLinear Optimization+1·Captain: mikedeng1

Shorter Tours by Nicer Ears 3: Every 2-Edge-Connected Graph Has a 2-Edge-Connected Spanning Subgraph with at Most 4/3 LP(G) EdgesResearch Paper

Designing a network that survives the failure of any single link is a basic problem of network design: given a graph GGG whose links can be bought, choose as few links as possible so that the chosen subgraph still connects all vertices after any one of its links is removed. This is the minimum 2-edge-connected spanning subgraph problem (2ECSS). It is NP-hard,…

17 thms2 active usersReviewed
CombinatoricsGraph TheoryLinear Optimization+1·Captain: mikedeng1

Shorter Tours by Nicer Ears 2: Every Connected Graph Has a Graphic TSP Tour with at Most 7/5 LP(G) EdgesResearch Paper

The graphic TSP is the travelling salesman problem in the shortest-path metric of an unweighted connected graph: visit every vertex of a graph GGG by a closed walk using as few edge traversals as possible. It is the unweighted special case of the metric TSP, and it is the setting in which the 3/2 barrier of Christofides' algorithm (1976) was first broken for…

14 thms2 active usersReviewed
CombinatoricsGraph TheoryLinear Optimization+1·Captain: mikedeng1

Shorter Tours by Nicer Ears 1: Every Connected Graph Has a Connected T-Join with at Most 3/2 LP(G,T) EdgesResearch Paper

In graphic TSP the cities are the vertices of a connected graph GGG and the distance between two of them is the number of edges on a shortest path. A closed walk visiting every vertex is the same thing as a connected multi-subgraph of GGG in which every degree is even. Dropping "closed" and asking for a walk from sss to ttt gives graphic sss-ttt-path TSP, where exactly …

18 thms2 active usersReviewed
Algebraic GeometryAnalysisOptimization·Captain: mikedeng1

Exploiting Symmetries in SDP-Relaxations for Polynomial Optimization 1: A G-Linear Functional Is Integration Against a G-Invariant Measure on K iff Its Symmetrized Localizing Forms Are PSDResearch Paper

Polynomial optimization asks for the minimum f∗f^*f∗ of a polynomial fff over a set K⊆RnK\subseteq\mathbb R^nK⊆Rn cut out by polynomial inequalities. Lasserre's moment relaxation (Lasserre 2001) replaces the minimization over points by a minimization over probability measures on KKK, and then over linear functionals on polynomials that satisfy semidefinite constraints. The…

7 thms2 active usersReviewed
Machine LearningOptimizationProbability·Captain: mikedeng1

On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points 2: Perturbed GD (Variant) Makes Half Its Iterates ε-Second-Order Stationary within Õ(ℓΔ_f/ε²) IterationsResearch Paper

Training a model in machine learning usually means minimizing a nonconvex function f:Rd→Rf:\mathbb R^d\to\mathbb Rf:Rd→R with first-order methods. Finding a global minimum of a general nonconvex function is NP-hard, so the classical guarantee for gradient descent (GD), xt+1=xt−η∇f(xt)x_{t+1}=x_t-\eta\nabla f(x_t)xt+1​=xt​−η∇f(xt​), is weaker: with step size η=1/ℓ\eta=1/\ellη=1/ℓ it reaches a point with …

9 thms2 active usersReviewed
Algorithmic Game TheoryOptimizationProbability·Captain: mikedeng1

Distributed Algorithms for Aggregative Games on Graphs III: Equal-Stepsize Gossip under Strong Monotonicity, limsup E‖x^k − x*‖² ≤ (α/μ)(2C²N + BC√(2nN)/(1 − √λ))Research Paper

In an aggregative game, each player's decision affects a common quantity, such as total production or total demand. An agent may be able to calculate its own preferred response while lacking direct access to that aggregate. Koshal, Nedić, and Shanbhag study how agents can estimate it by exchanging information only with neighbours on a communication graph.…

13 thms2 active usersReviewed
Algebraic GeometryOperations ResearchOptimization·Captain: mikedeng1

Optimality Conditions and Finite Convergence of Lasserre's Hierarchy II: Off a Proper Zariski-Closed Set of Input Data, the Classical Optimality Conditions Hold at Every Local MinimizerResearch Paper

Lasserre's hierarchy is a sequence of semidefinite relaxations for minimizing a polynomial over a set defined by polynomial equations and inequalities (Lasserre 2001). Under the archimedean condition its optimal values converge to the true minimum, but only asymptotically in general; in practice the hierarchy is often exact at a small relaxation order. J.…

15 thms2 active usersReviewed
CombinatoricsGraph TheoryProbability·Captain: mikedeng1

Algorithms for #BIS-Hard Problems on Expander Graphs 4: On Almost Every Δ-Regular Bipartite Graph with Δ ≥ Cq² log² q, Proper q-Colorings Reduce to Kotecký–Preiss Polymer ModelsResearch Paper

Counting the proper qqq-colorings of a graph, and sampling one uniformly at random, are basic problems of approximate counting with a long history in statistical physics, where proper colorings are the zero-temperature antiferromagnetic Potts model. On bipartite graphs these problems are tied to #BIS, the problem of approximately counting independent sets in…

13 thms2 active usersReviewed
Machine LearningOptimizationProbability·Captain: mikedeng1

On Nonconvex Optimization for Machine Learning: Gradients, Stochasticity, and Saddle Points 1: Perturbed SGD Makes Half Its Iterates ε-Second-Order Stationary within Õ(ℓΔ_f·𝔑/ε²) IterationsResearch Paper

Most training objectives in machine learning are smooth and nonconvex, and they are minimized by stochastic gradient descent (SGD) and its variants. For nonconvex fff the classical guarantee is convergence to an ϵ\epsilonϵ-first-order stationary point, ∥∇f(x)∥≤ϵ\|\nabla f(x)\|\le\epsilon∥∇f(x)∥≤ϵ: Ghadimi and Lan (arXiv:1309.5549) showed that SGD reaches one in …

17 thms2 active usersReviewed
Machine LearningOptimizationProbability+1·Captain: mikedeng1

Robustness May Be at Odds with Accuracy 2: The Unit-Norm Soft-Margin SVM Is >99% Accurate but <1% Robust at ε ≥ 2η, While Adversarial Training Gives Accuracy pResearch Paper

Adversarial training asks a classifier to work even after an input has been changed within a prescribed perturbation budget. Tsipras, Santurkar, Engstrom, Turner, and Mądry studied why the classifier that performs best on ordinary inputs can behave very differently under these changes. Their explicit model separates one reliably predictive feature from many…

10 thms2 active usersReviewed
Graph TheoryMathematical PhysicsProbability·Captain: mikedeng1

Algorithms for #BIS-Hard Problems on Expander Graphs 3: On Almost Every Δ-Regular Bipartite Graph, the Hard-Core Model at λ > 50 log²Δ/Δ Reduces to Two Kotecký–Preiss Polymer ModelsResearch Paper

The hard-core model assigns weight to independent vertex sets of a graph. Its partition function counts those sets when the activity is one and weights larger sets more heavily when the activity increases. Counting independent sets on bipartite graphs is a standard benchmark for approximate counting: the general problem is difficult, while random regular…

8 thms2 active usersReviewed
Algorithmic Game TheoryOptimizationProbability·Captain: mikedeng1

Distributed Algorithms for Aggregative Games on Graphs II: The Gossip Algorithm with Stepsizes 1/Γ_k(i) Converges Almost Surely to the Unique EquilibriumResearch Paper

In an aggregative game, each player's cost depends on its own decision and on the sum of all players' decisions. That form appears in resource sharing, production, and network games: a player may know its own choice while lacking a central feed of the aggregate. A distributed algorithm therefore has to estimate the aggregate through local communication as…

9 thms2 active usersReviewed
Operations ResearchOptimal TransportProbability+1·Captain: mikedeng1

A Stochastic Control Approach to No-Arbitrage Bounds Given Marginals, with an Application to Lookback Options: The Robust Superhedging Bound of g(X*_T) Given the Law of X_T Equals μ^HL(g)Research Paper

A lookback option pays a function of the running maximum of the underlying asset over the life of the contract. When the prices of European call options of all strikes at the maturity are quoted, the risk-neutral law μ\muμ of the terminal price is known, but the law of the whole path is not. The robust (model-free) superhedging cost of the lookback payoff is…

13 thms2 active usersReviewed
Machine LearningOptimizationProbability·Captain: mikedeng1

Stochastic Model-Based Minimization of Weakly Convex Functions 2: The Proximal Stochastic Subgradient Method Drives E‖∇φ_{1/ρ̄}(x_{t*})‖² to Zero at Rate O(1/√T)Research Paper

The proximal stochastic subgradient method is the workhorse of large-scale learning: to minimize a regularized population risk φ(x)=f(x)+r(x)\varphi(x) = f(x) + r(x)φ(x)=f(x)+r(x) with f(x)=Eξ∼P[f(x,ξ)]f(x) = \mathbb E_{\xi \sim P}[f(x,\xi)]f(x)=Eξ∼P​[f(x,ξ)], it samples a data point, takes a step against a sampled subgradient of fff, and applies the proximal map of the regularizer rrr. Its sample complexity is classical…

12 thms2 active usersReviewed
Functional AnalysisMarkov ChainProbability+1·Captain: mikedeng1

Spectral Gaps for a Metropolis–Hastings Algorithm in Infinite Dimensions I: The pCN Algorithm Has a Wasserstein Spectral Gap Uniform in the Dimension When the Potential Is Globally LipschitzResearch Paper

Sampling from a distribution described relative to a Gaussian reference law is common in Bayesian inverse problems, where an unknown function or initial condition is inferred from noisy observations. Such a distribution is naturally infinite dimensional before it is approximated on a computer. A numerical method must therefore behave reliably as the…

10 thms2 active usersReviewed
Dynamical SystemsHarmonic AnalysisMachine Learning+1·Captain: mikedeng1

Approximation Bounds for Random Neural Networks and Reservoir Systems II: Echo State Networks with Random Weights Approximate Regular Functionals with an Explicit L² Error Bound (Theorem 2)Research Paper

Reservoir computing learns an input/output system from data in two stages. A dynamical system, the reservoir, is driven by the input sequence and its state is recorded; then only a linear readout of that state is trained, by least squares. The echo state network (ESN) is the most widely used reservoir: its state evolves by …

11 thms2 active usersReviewed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

A Two-Timescale Stochastic Algorithm Framework for Bilevel Optimization: Complexity Analysis and Application to Actor-Critic: Explicit Error Bounds for TTSA with a Strongly Convex Outer ObjectiveResearch Paper

Bilevel optimization asks for an outer decision while an inner optimization problem responds to that decision. In hyperparameter selection, for example, the outer objective evaluates a model whose parameters are chosen by a training problem. A two-timescale algorithm updates both levels in one stochastic loop, so its outer step uses an inner solution that…

10 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Generalized Turán Problems for Even Cycles 7: The Maximum Number of Paths on l Vertices in a C_{2k+1}-Free Graph on n Vertices Is (1+o(1))(n/2)^lResearch Paper

An extremal graph problem asks how many copies of a chosen small graph can occur when a different graph is forbidden. The usual Turán problem counts edges; counting paths or cycles gives a more detailed view of the structure that can survive a forbidden subgraph. Gerbner, Győri, Methuku and Vizer study these generalized Turán numbers for paths and cycles in…

9 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Generalized Turán Problems for Even Cycles 2: The Maximum Number of 2l-Cycles in a C_{2k}-Free Graph on n Vertices Is Θ(n^l), with Explicit Upper and Lower ConstantsResearch Paper

The classical Turán problem asks for the maximum number of edges of an nnn-vertex graph that avoids a fixed subgraph. For even cycles this is one of the central open problems of extremal graph theory: Bondy and Simonovits proved that a C2kC_{2k}C2k​-free graph has O(n1+1/k)O(n^{1+1/k})O(n1+1/k) edges, and this order is known to be sharp only for k=2,3,5k=2,3,5k=2,3,5.

12 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Cycle Lengths in Expanding Graphs 3: For 0 < β < 1/20, Every β-Graph on n Vertices Has a Cycle of Every Length from O(1/log(1/β))·log n to (1−O(β))·nResearch Paper

Which cycle lengths a graph must contain is a classical question of extremal graph theory. A graph on nnn vertices is pancyclic if it has cycles of every length from 333 to nnn; Bondy's meta-conjecture (Bondy 1971) and a long line of results ask which density or expansion conditions force pancyclicity or, more modestly, force the set of cycle lengths to contain a…

10 thms2 active usersReviewed
Machine LearningReinforcement LearningStatistics·Captain: mikedeng1

The Statistical Complexity of Interactive Decision Making III: E2D with Hellinger Confidence Sets Has Regret at Most Σ_t sup dec_γ(M_εt(M̄), M̄) + γ·Est_H(T,δ)Research Paper

Interactive decision making covers bandits, contextual bandits and reinforcement learning: a learner repeatedly chooses a decision, observes a reward and an observation drawn from an unknown model, and tries to accumulate nearly as much reward as the best decision for that model. Foster, Kakade, Qian and Rakhlin (arXiv:2112.13487) introduced the Decision-Est…

13 thms2 active usersReviewed
Harmonic AnalysisMachine LearningProbability·Captain: mikedeng1

Approximation Bounds for Random Neural Networks and Reservoir Systems I: Random ReLU Networks with Sampled Inner Weights Approximate Fourier-Represented Functions on a Hilbert Space (Theorem 1)Research Paper

In random-feature models, also called extreme learning machines or random neural networks, the inner weights of a one-hidden-layer network are drawn at random and only the linear readout is trained. Training is then a least-squares problem, which is why such models, and their dynamic counterparts reservoir computing and echo state networks, are used in…

8 thms2 active usersReviewed
Dynamical SystemsMachine LearningProbability·Captain: mikedeng1

Approximation Bounds for Random Neural Networks and Reservoir Systems III: Echo State Networks with Output Feedback and Random Weights Approximate Contracting Reservoirs (Theorem 4)Research Paper

An echo state network with output feedback is a recurrent model whose previous output is fed back into its next hidden-state update. In reservoir computing only the linear output weights are trained, while the internal weights are fixed, typically after being drawn at random. This raises a quantitative question: if the internal rows are sampled from a fixed…

8 thms2 active usersReviewed
CombinatoricsGraph Theory·Captain: mikedeng1

Cycle Lengths in Expanding Graphs 1: Every α-Expander on n Vertices Has a Cycle of Length in [ℓ, ℓ+O(1/α)] for Every Integer ℓ from O(1/α)·log n up to 2^(−O(log(1/α)/α))·nResearch Paper

Which cycle lengths a graph must contain is a long-standing theme of extremal graph theory, studied for graphs of given minimum degree, chromatic number or density. A natural class in which to ask it is that of expanders: graphs in which every not-too-large vertex set has many neighbours outside it (Hoory, Linial and Wigderson). It is known that an α\alphaα-ex…

10 thms2 active usersReviewed
Machine LearningReinforcement LearningStatistics·Captain: mikedeng1

The Statistical Complexity of Interactive Decision Making II: Every Algorithm Has Expected Regret at Least (1/6)·dec_γ(M^∞_ε̄γ(M̄), M̄)·T, the Localized DEC Lower BoundResearch Paper

In interactive decision making, an algorithm chooses actions while learning which model governs its observations. A low-regret guarantee for one algorithm does not by itself say whether every algorithm could do better. The Decision-Estimation Coefficient (DEC) was introduced to express the cost of choosing useful decisions while distinguishing plausible…

12 thms2 active usersReviewed
PreviousPage 33 of 52Next

Top contributors

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