Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Optimization

2,311 missions · 1,728 completed

Missions

Open583Completed1728All2311
🏆Completed
Algorithmic Game TheoryAnalysisOperations Research+1·Captain: mikedeng1

A Sensitivity Analysis of the Price of Anarchy in Nonatomic Congestion Games 2: The Social Optimum Cost, the Wardrop Equilibrium Cost and the Price of Anarchy Are Continuous on the Game SpaceResearch Paper

Traffic users choose routes for themselves, while a planner may choose routes that minimize everyone's combined travel cost. The price of anarchy measures the cost of the users' equilibrium relative to the planner's optimum. Travel demand and arc latency functions are estimated from data and change over time, so a ratio that changes abruptly under a small…

9 thms3 active usersReviewed
Differential GeometryMachine LearningProbability·Captain: mikedeng1

Stochastic Zeroth-Order Riemannian Derivative Estimation and Optimization 2: ZO-RSGD Has Average Expected Squared Riemannian Gradient Norm at Most 4L(f(x₀) − f(x*))/(N+1) + 2μ²L²(d+6)³ + 16(d+4)σ²/mResearch Paper

Many optimization problems are posed over a manifold rather than a vector space: orthogonality constraints (the Stiefel manifold), unit-norm constraints (the sphere), fixed-rank matrices. In some of them the objective can only be evaluated, not differentiated. Black-box adversarial attacks on a neural network with a norm-constrained perturbation,…

13 thms3 active usersReviewed
🏆Completed
AnalysisOperations Research·Captain: mikedeng1

Lightning Network Economics: Channels III: The Minimal Cost of a Symmetric Bidirectional Channel Is 3(2Bλ/r)^{1/3} − B/6 + O(r^{1/3}) as r → 0Research Paper

Payment channels let two parties make repeated transfers while using an on-chain transaction only when a channel needs resetting. They require funds to be committed in advance. The economic choice is therefore between the transaction fees saved by using a channel and the opportunity cost of funds tied up in it. Guasoni, Huberman, and Shikhelman give a…

17 thms3 active users
🏆Completed
EconomicsOperations Research·Captain: mikedeng1

Climate Impact Investing 2: With Poisson Climate Uncertainty λ, If the Green Portfolio Is Green Then y*_λ Rises to 1 in λ, So Equilibrium Emissions Rise as Uncertainty GrowsResearch Paper

Climate impact investing refers to investors who tilt their portfolios away from companies with large greenhouse-gas emissions. Its stated aim goes beyond aligning portfolios with values: by raising the cost of capital of polluting companies, it is meant to change what those companies do. De Angelis, Tankov and Zerbib (SSRN 3562534, published in Management…

13 thms3 active usersReviewed
🏆Completed
Number TheoryOperations Research·Captain: mikedeng1

Integer Factorization: Why Two-Item Joint Replenishment Is Hard 2: For Odd Composite M, Every Optimal Plan of an Explicit Two-Item Periodic JRP Instance Has q₂ = M and 1 < gcd(q₁, M) < MResearch Paper

The joint replenishment problem (JRP) is a basic model of inventory coordination: several items are ordered from one supplier, each item pays its own ordering and holding costs, and an additional item-independent joint ordering cost rewards ordering the items at common times. Two accounting conventions are studied. In the periodic JRP (also called the…

9 thms3 active usersReviewed
Differential GeometryMachine LearningProbability·Captain: mikedeng1

Stochastic Zeroth-Order Riemannian Derivative Estimation and Optimization 1: ZO-RGD Has Average Expected Squared Riemannian Gradient Norm at Most 8(d+4)L(f(x₀) − f(x*))/(N+1) + 8(d+4)L·C(μ)Research Paper

Many optimization problems in statistics and machine learning constrain the variable to a smooth manifold: orthonormal frames in sparse PCA and dictionary learning (the Stiefel manifold), unit vectors in phase retrieval (the sphere), fixed-rank matrices in matrix completion. Riemannian optimization handles these problems directly on the manifold. A step is…

13 thms3 active usersReviewed
Linear algebraQuantum InformationTheoretical Computer Science·Captain: mikedeng1

Optimization by Decoded Quantum Interferometry 1: The Semicircle Law — the Optimal Degree-ℓ DQI State Satisfies ⟨s⟩/m → (√(μ(1−ρ)) + √(ρ(1−μ)))² When 2ℓ + 1 < d⊥Research Paper

Decoded quantum interferometry (DQI) is a quantum algorithm, introduced by Jordan, Shutty, Wootters, Zalcman, Schmidhuber, King, Isakov, Khattar and Babbush (arXiv:2408.08292), that turns an approximate optimization problem over a finite field into a decoding problem for a linear code. It applies to max-LINSAT: given linear constraints over Fp\mathbb F_pFp​,…

14 thms3 active usersReviewed
Quantum InformationTheoretical Computer Science·Captain: mikedeng1

A Quantum Approximate Optimization Algorithm Applied to a Bounded Occurrence Constraint Problem I: Level-One QAOA Satisfies (1/2 + 1/(101 D^(1/2) ln D))m Equations of Max E3LIN2 for Large DResearch Paper

The Quantum Approximate Optimization Algorithm (QAOA) of Farhi, Goldstone and Gutmann (arXiv:1411.4028) is a family of shallow quantum circuits for combinatorial optimization. At its lowest level, p=1p = 1p=1, the circuit has two real parameters, and its output is a random bit string. The question is how many constraints that string satisfies, compared with the…

18 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomicsOperations Research·Captain: mikedeng1

Proof-of-Work Cryptocurrencies: Does Mining Technology Undermine Decentralization? 4: The Threshold Equilibrium Investment in New Mining Hardware, with Entry Decreasing in the Fixed CostResearch Paper

Proof-of-work blockchains such as Bitcoin pay a block reward to the miner that first solves a computational puzzle. The chance of winning is proportional to a miner's share of the total computing power (hash rate), so mining is a contest in which every miner pays for hash rate and the reward is split in proportion to it. Over time mining moved from…

11 thms3 active usersReviewed
🏆Completed
AnalysisOperations ResearchProbability·Captain: mikedeng1

Sample-Driven Optimal Stopping: From the Secretary Problem to the i.i.d. Prophet Inequality III: The Explicit Lower Bound on the Competitive Ratio Is at Least α* Times pResearch Paper

Optimal stopping with partial information sits between two classical problems. In the secretary problem a decision maker sees values in random order, knows nothing about how they are generated, and must stop on the best one; the optimal guarantee is 1/e1/e1/e. In the i.i.d. prophet inequality the values are independent draws from a known distribution, and the…

14 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomicsOperations Research·Captain: mikedeng1

Climate Impact Investing 1: With an Average-Emissions Interaction Effect the Unique Equilibrium Emission Schedule Is ψ* − ε/(2n+ε)·(ψ* + 2n²ψ̄*/(2n+(n+1)ε)), Below the Schedule Without InteractionResearch Paper

Green investors hold a growing share of financial wealth, and the stated purpose of much of this capital is to change how companies behave, not only to avoid exposure to climate risk. Whether exclusionary or impact-oriented portfolios actually move corporate emissions is an equilibrium question: investors' preferences shift the cost of capital, and…

9 thms3 active usersReviewed
🏆Completed
Dynamical SystemsEconomicsOperations Research·Captain: mikedeng1

Revenue Management in Crowdfunding 1: Optimal Pledge Level and Campaign Duration Under Triangular Valuations When Independent or Herding Backers DominateResearch Paper

Reward-based crowdfunding platforms such as Kickstarter let a project creator collect pledges from the public for a fixed period. Two numbers are fixed before launch and cannot be changed afterwards: the pledge level ppp each backer pays, and the campaign duration TTT. A high pledge level earns more per backer but deters backers with low valuations; a long…

10 thms3 active usersReviewed
🏆Completed
Number TheoryOperations Research·Captain: mikedeng1

Integer Factorization: Why Two-Item Joint Replenishment Is Hard 1: For Odd Composite M, Every Optimal Plan of an Explicit Two-Item Aperiodic JRP Instance Has q₂ = M and 1 < gcd(q₁, M) < MResearch Paper

The joint replenishment problem (JRP) is one of the basic models of multi-item inventory control. Each item follows the economic order quantity (EOQ) model of Harris (1913): ordering costs a fixed amount, holding stock costs a rate proportional to the stock, and the classical trade-off between the two determines how often to reorder. In a JRP, items…

9 thms3 active usersReviewed
🏆Completed
EconomicsOperations ResearchProbability·Captain: mikedeng1

Accelerability vs. Scalability: R&D Investment Under Financial Constraints and Competition I: Comparative Statics of an Unconstrained Monopoly's Optimal R&D IntensityResearch Paper

Firms deciding how much to spend on research and development face two different kinds of return to spending. More money can make the eventual innovation more valuable, or it can make the innovation arrive sooner. Lin (Management Science, 2022, doi:10.1287/mnsc.2022.4503) calls these two properties scalability and accelerability, and shows that they predict…

8 thms3 active usersReviewed
AnalysisOperations ResearchProbability·Captain: mikedeng1

Sample-Driven Optimal Stopping: From the Secretary Problem to the i.i.d. Prophet Inequality II: The Optimal Competitive Ratio Tends to the i.i.d. Prophet Constant as p Tends to 1Research Paper

Optimal stopping with samples sits between two classical problems. In the secretary problem a decision maker sees items in random order, knows nothing about their values, and must stop on one; the best guarantee is 1/e1/e1/e. In the i.i.d. prophet inequality the values are independent draws from a known distribution, and the best guarantee against the expected…

14 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomicsOperations Research·Captain: mikedeng1

Proof-of-Work Cryptocurrencies: Does Mining Technology Undermine Decentralization? 1: The Mining Game Has a Unique Equilibrium Whose Number of Active Miners Is Fixed by an Explicit Cost ConditionResearch Paper

Proof-of-work blockchains such as Bitcoin keep their ledger secure by a contest: miners spend computing power ("hash rate") to solve a cryptographic puzzle, and the miner who solves it first earns the block reward. The probability of winning is proportional to a miner's share of the total hash rate, so mining is a rent-seeking contest in the sense of…

8 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryEconomicsOperations Research·Captain: mikedeng1

Proof-of-Work Cryptocurrencies: Does Mining Technology Undermine Decentralization? 2: Signs of the Sensitivities of Equilibrium Hash Rates and Hash Rate Shares to Mining CostsResearch Paper

In a proof-of-work cryptocurrency such as Bitcoin, miners spend computing power (hash rate) to win the right to add the next block and collect a reward. Whether this competition stays decentralized depends on how individual hash rates react to differences in mining costs: if a cost advantage translates into an ever larger share of the total hash rate,…

8 thms3 active usersReviewed
Graph TheoryQuantum Information·Captain: mikedeng1

A Quantum Approximate Optimization Algorithm II: On v-Regular Graphs the Variance of the Cut Value in the QAOA State Is at Most 2((v−1)^(2p+2)−1)/(v−2) Times the Number of EdgesResearch Paper

The Quantum Approximate Optimization Algorithm (QAOA) of Farhi, Goldstone and Gutmann (arXiv:1411.4028, 2014) is a family of shallow quantum circuits for combinatorial optimization, indexed by a depth ppp and 2p2p2p real angles. It has become one of the standard candidate algorithms for near-term quantum hardware, and its MaxCut instance is the usual benchmark on…

14 thms3 active usersReviewed
🏆Completed
Operations ResearchProbabilityStochastic Systems·Captain: mikedeng1

Pricing in On-Demand and One-Way Vehicle-Sharing Networks 1: Static Prices Earn at Least K/(N+K−1+Λ/μ) of the Fluid Optimum, via Increasingly Tight Availability BoundsResearch Paper

In one-way car sharing, bike sharing and ride hailing, a vehicle that serves a trip from location iii to location jjj ends up at jjj. Prices therefore do two jobs: they collect revenue and they steer the fleet. The best dynamic (state-dependent) pricing policy reacts to where every vehicle is, but computing it is a Markov decision problem over a state space that…

28 thms3 active users
🏆Completed
Dynamical SystemsEconomicsOperations Research·Captain: mikedeng1

Minimum Earnings Regulation and the Stability of Marketplaces I: The Marketplace Is Stable Exactly When M ≤ w* Under Tight Labor Supply (p* ≤ w*) and M ≤ H(R(p*)) Under Loose SupplyResearch Paper

Minimum hourly earnings rules for ride-hailing drivers are meant to protect income during periods when drivers spend part of their time idle. A platform pays a wage per hour carrying riders, yet drivers care about earnings per hour logged onto the platform. When many drivers enter after a wage increase, utilization can fall and offset the increase. A…

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

Design and Analysis of Switchback Experiments 1: With m-Period Carryover and T = nm, n ≥ 4, the Unique Minimax-Optimal Regular Design Flips Fair Coins at 1, 2m+1, 3m+1, …, (n−2)m+1Research Paper

Online platforms such as ride-hailing, delivery and advertising marketplaces routinely test new pricing or matching policies on a single market. Randomizing over users is often impossible there: every rider and driver in a city shares one supply pool, so treating some users and not others contaminates the control group. The standard alternative is a switchba…

14 thms3 active usersReviewed
Graph TheoryQuantum Information·Captain: mikedeng1

A Quantum Approximate Optimization Algorithm I: At p = 1 the QAOA Expected Cut Is at Least 0.6924 Times the Maximum Cut on Every Connected 3-Regular GraphResearch Paper

The quantum approximate optimization algorithm (QAOA) of Farhi, Goldstone and Gutmann (arXiv:1411.4028, 2014) is a family of shallow quantum circuits, indexed by an integer depth p≥1p \ge 1p≥1, that prepare states whose computational-basis measurements are biased toward good solutions of a combinatorial optimization problem. It became the standard candidate for…

14 thms3 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: mikedeng1

Digital Privacy I: The Profit-Maximizing Data Collection and Protection Have a Closed Form, and Both Weakly Increase with the Data-Driven Revenue Share PResearch Paper

Platforms that earn money from their users' activity make two linked decisions about the data that activity generates: how much of it to record and store, and how much to spend protecting what they store. Stored data lets a business tailor its services and sell data-driven products, but it also attracts adversaries (hackers, data brokers, unauthorized third…

17 thms3 active users
Dynamic ProgrammingOperations ResearchStochastic Systems·Captain: mikedeng1

Analytical Solution to a Partially Observable Machine Maintenance Problem with Obvious Failures: The Optimal Maintenance Frontier Has Six Possible StructuresResearch Paper

Machines in production lines deteriorate in ways that are only partly visible. A machine may run in a degraded state that raises costs without announcing itself, and eventually fail in a way that cannot be missed. The decision maker must choose between continuing production, paying for an inspection that reveals the hidden state, and replacing the machine…

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

A Faster Cutting Plane Method and its Implications for Combinatorial and Convex Optimization I: The Largest-Coordinate Strategy Keeps the Stochastic Chasing 0 Game within 2(c+R)log(4mk²/p)Research Paper

Cutting plane methods minimize a convex function, or find a point in a convex set, using only a separation oracle: a routine that, given a query point, either certifies it is good or returns a halfspace containing the target. Lee, Sidford and Wong (arXiv:1508.04874, FOCS 2015) gave a cutting plane method for a convex set in Rn\mathbb R^nRn inside a box of…

6 thms3 active usersReviewed
PreviousPage 32 of 93Next

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