Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

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

Probability

2,743 missions · 1,549 completed

Missions

Open1194Completed1549All2743
🏆Completed
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: Shuze Chen

Stratifying Markets for Efficient TradeResearch Paper

In bilateral trade a seller owns one item and a buyer wants it; each knows only their own cost or value. Myerson and Satterthwaite (1983) showed that no incentive-compatible, individually rational, budget-balanced mechanism trades efficiently whenever the supports of the value and the cost overlap, so the question becomes which simple mechanisms capture a…

30 thms3 active usersReviewed
🏆Completed
Optimization·Captain: mikedeng1

Adaptivity Gaps for Welfare-Maximizing Pooled TestingResearch Paper

Pooled screening uses a limited number of assays to clear potentially valuable individuals or resources. A negative test certifies every member of its pool as healthy. With a fixed budget, later tests can respond to earlier outcomes, directing the remaining resources toward different people after positive and negative results. The mathematical question is…

17 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

Robust Shattering ArgumentsResearch Paper

Many fast randomized distributed algorithms, for the Lovász Local Lemma, maximal independent set, matching and coloring, follow the shattering paradigm (Barenboim, Elkin, Pettie, Schneider, JACM 2016). A randomized pre-shattering phase solves the problem on most of the graph. It leaves a residual set BBB of unresolved nodes, and the analysis has to show that…

10 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchOptimization+1·Captain: Shuze Chen

Consistent Submodular Maximization with Full ForesightResearch Paper

Online algorithms with recourse maintain a good solution while the input grows, and limit how much the solution changes at each update. For monotone submodular maximization under a cardinality constraint, the consistent version of this problem was introduced by Dütting et al. (2024) and studied further by Dütting et al. (2025) and Fu et al. (2026). In those…

30 thms3 active usersReviewed
🏆Completed
Machine Learning·Captain: Shuze Chen

Sample Complexity of Multiclass OmnipredictionResearch Paper

Omniprediction, introduced by Gopalan, Kalai, Reingold, Sharan and Wieder (arXiv:2109.05389), asks for one predictor that serves every downstream decision maker at once. Each decision maker has their own loss, best-responds to the predicted label distribution, and should do as well as the best benchmark in a fixed class FFF. For binary labels, randomized…

15 thms3 active usersReviewed
🏆Completed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: mikedeng1

Top-Down Lower Bounds for All DepthsResearch Paper

A Boolean circuit computes a function by composing gates. Parity asks whether an input word contains an odd number of ones. It is a basic test of the power of bounded-depth computation: unrestricted AND and OR gates can inspect many bits at once, yet computing parity at fixed depth requires exponentially many wires. The quantitative lower-bound form…

21 thms3 active usersReviewed
🏆Completed
Random Matrix Theory·Captain: mikedeng1

Anticoncentration of the Permanent in Ginibre EnsemblesResearch Paper

The permanent of an n×nn\times nn×n matrix, per⁡A=∑σ∈Sna1σ(1)⋯anσ(n)\operatorname{per}A=\sum_{\sigma\in S_n}a_{1\sigma(1)}\cdots a_{n\sigma(n)}perA=∑σ∈Sn​​a1σ(1)​⋯anσ(n)​, is the determinant without signs. Computing it exactly is #P-hard, and its behaviour on random Gaussian matrices sits at the centre of the complexity-theoretic case for quantum advantage in BosonSampling. Aaronson and Arkhipov (AA13) reduced…

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

The Harmonic Online k-Server Algorithm Is Poly(k)-CompetitiveResearch Paper

The online k-server problem concerns mobile servers that must answer requests without knowing future requests. Moving a server costs the distance it travels. A decision rule can achieve a strong comparison with other service schedules while still requiring substantial computation or memory to make each decision. Harmonic addresses the computational side…

21 thms3 active usersReviewed
🏆Completed
OptimizationTheoretical Computer Science·Captain: mikedeng1

The Optimizer's Windfall: Bounding Hindsight Gain under Random RestrictionsResearch Paper

Sampling variables is a basic way to estimate large optimization problems. An algorithm reads the interactions among the retained variables, optimizes that smaller instance, and rescales the answer. Every fixed assignment has the right expected score after rescaling. The assignment chosen after seeing the sample can do better, however, because it responds…

33 thms3 active usersReviewed
🏆Completed
Linear algebraOperations ResearchStatistics·Captain: mikedeng1

Low-Rank Denoising for Predict-then-OptimizeResearch Paper

A predict-then-optimize pipeline estimates unknown costs and passes the estimate to an optimizer. In shortest-path problems, edge costs can come from noisy measurements or simulation replications. Averaging more replications reduces noise, but costs across different instances may also share structure: several edges can vary together. A projection estimator k…

6 thms3 active usersReviewed
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

Is Randomness Necessary for Adaptive Data Analysis?Research Paper

A dataset is often reused to answer questions chosen after seeing earlier answers. Each answer can influence the next question, so the usual guarantee for one question fixed in advance does not automatically extend to the resulting interaction. Adaptive data analysis asks what a mechanism can reliably reveal about a population from a single finite sample in…

14 thms3 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: iris

Linear Max Load and Additive StructureResearch Paper

A hash function compresses a large universe into a small number of bins, and its quality is judged by how evenly it spreads a set of inputs. For a set SSS of nnn items hashed into nnn bins by a fully random function, the expected size of the fullest bin, the expected max load, is (1+o(1))ln⁡n/ln⁡ln⁡n(1+o(1))\ln n/\ln\ln n(1+o(1))lnn/lnlnn. Fully random functions are expensive in time, space and…

28 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: iris

Optimal universal sets for submodular functionsResearch Paper

A set function f:2[n]→Rf:2^{[n]}\to\mathbb Rf:2[n]→R is submodular if f(S∪T)+f(S∩T)≤f(S)+f(T)f(S\cup T)+f(S\cap T)\le f(S)+f(T)f(S∪T)+f(S∩T)≤f(S)+f(T) for all S,T⊆[n]S,T\subseteq[n]S,T⊆[n]. Cut functions of graphs and digraphs, coverage functions, entropy of subsets of random variables and many utility functions in economics are submodular. Maximizing a nonnegative submodular function with no constraint generalizes Max-Cut and…

18 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchTheoretical Computer Science·Captain: iris

Single-or-Sample: Online Fair Allocation for Combinatorial AgentsResearch Paper

Consider a relief center that hands out indivisible supplies to people arriving over time, each with different needs. Everything handed out is gone, and nothing is known about who comes next. Maximin share (MMS) fairness, introduced by Budish 2011, measures an agent's share using only that agent's own valuation: the value the agent could guarantee by…

32 thms3 active usersReviewed
🏆Completed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: iris

Randomized Greedy MIS is Fast at Every NodeResearch Paper

A local computation algorithm answers a query about one part of a global solution (here: is vertex vvv in the maximal independent set?) by inspecting only a small neighbourhood of vvv, so that answers to different queries are consistent with one global solution. Nguyen and Onak (FOCS 2008) simulated the randomized greedy maximal independent set (RGMIS) this…

41 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchOptimization·Captain: iris

Markov Decision Processes with Applications to Finance VI: With Proportional Transaction Costs the Optimal Portfolio Has Buy, Hold and Sell Regions Given by ConesTextbook

In frictionless discrete-time portfolio models the investor rebalances freely, and with a homogeneous utility the optimal policy keeps a constant fraction of wealth in the stock. Real trading is costly: every purchase or sale of stock pays a fee proportional to the traded amount. A constant-fraction policy then trades every period and pays the fee every…

34 thms3 active usersReviewed
🏆Completed
Dynamic ProgrammingOperations ResearchTheoretical Computer Science·Captain: iris

Online Policies for Efficient Volunteer Crowdsourcing: The Sparse Notification Policy Is 12−q(1−1e)\frac{1}{2-q}(1-\frac{1}{e})2−q1​(1−e1​)-CompetitiveResearch Paper

Nonprofit crowdsourcing platforms rely on volunteers to perform time-sensitive tasks. On Food Rescue U.S., for example, a task is a scheduled pickup of a perishable donation, and when a task goes unclaimed the platform can push a notification to a subset of volunteers. Notifying more volunteers raises the chance that the current task gets done, but…

19 thms3 active usersReviewed
🏆Completed
cryptographyQuantum Information·Captain: iris

Universally-composable privacy amplification from causality constraints: almost every fixed hash function yields a key secure against nonsignaling eavesdroppers, bounded by the CHSH valueResearch Paper

Device-independent key distribution asks whether two parties can establish a secret key without trusting the devices that prepare and measure their systems. If the outcomes of local measurements violate a Bell inequality, they cannot have been fixed in advance, and this limits what any third party can know about them. The only physical assumption needed is n…

28 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimizationStatistics·Captain: iris

Learning-based Robust Optimization: Procedures and Statistical Guarantees: with n₂ ≥ log δ/log(1 − ϵ), the data-split order-statistic set covers 1 − ϵ of P with confidence 1 − δResearch Paper

A chance-constrained program (CCP) asks for a decision xxx minimizing a cost f(x)f(x)f(x) subject to P(g(x;ξ)∈A)≥1−ϵP(g(x;\xi)\in A)\ge 1-\epsilonP(g(x;ξ)∈A)≥1−ϵ, where ξ\xiξ is a random parameter with law PPP and ϵ\epsilonϵ is a tolerance level. Chance constraints model reliability requirements in operations, finance and engineering, but they are hard to solve: the feasible set is usually nonconvex,…

10 thms3 active usersReviewed
🏆Completed
Linear algebraOperations Research·Captain: iris

Processing Networks XVII: A Relative-Entropy Lower Bound for the Traffic Equations of a Transient Routing MatrixTextbook

In a multiclass processing network, jobs of class iii arrive from outside at rate λi\lambda_iλi​ and, after service, move to class jjj with probability PijP_{ij}Pij​ or leave the network. The traffic equations α=λ+P′α\alpha=\lambda+P'\alphaα=λ+P′α give the total arrival rate αi\alpha_iαi​ into each class. Chapter 10 of Dai and Harrison's Processing Networks: Fluid Models and Stability proves…

15 thms3 active usersReviewed
🏆Completed
Operations ResearchStochastic Systems·Captain: iris

How Does Risk Hedging Impact Operations? Insights from a Price-Setting Newsvendor Model: When the Asset Trend Raises Demand, Hedging Lowers the Optimal Price and Virtual Production QuantityResearch Paper

Manufacturers whose demand moves with a traded asset (automakers with oil prices, airlines with fuel, exporters with exchange rates) can trade that asset continuously while they set prices and production. Whether such financial hedging should change operational decisions, and in which direction, is a question operations management has asked since Gaur and…

34 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: iris

Conditional Distributionally Robust Functionals: The Conditional Risk Measure of Atom-Supported Sets 𝔄ᵢ Equals the Conditional Distributionally Robust Functional of Their Mixture 𝔐_ν = Σ νᵢ𝔄ᵢResearch Paper

A distributionally robust functional evaluates a random cost ZZZ by its worst expectation over a set M\mathfrak MM of probability measures, the ambiguity set: R(Z)=sup⁡Q∈MEQ[Z]\mathcal R(Z)=\sup_{Q\in\mathfrak M}\mathbb E_Q[Z]R(Z)=supQ∈M​EQ​[Z]. Functionals of this form are the dual representation of coherent risk measures and the objective of distributionally robust optimization. Multistage…

9 thms3 active usersReviewed
🏆Completed
Operations ResearchReinforcement Learning·Captain: iris

Quantile Markov Decision Processes: Backward Dynamic Programming over State and Quantile Level Computes the Optimal Quantile of the Cumulative RewardResearch Paper

A classical Markov decision process (MDP) chooses a policy that maximizes the expected cumulative reward. In many applications the expectation is the wrong summary: a clinician choosing when to start a treatment, or an investor facing ruin, cares about the bad outcomes, and two policies with equal means can have very different lower tails. A natural…

11 thms3 active usersReviewed
🏆Completed
Linear OptimizationOperations ResearchOptimization·Captain: iris

Stochastic Linear Programming: Models, Theory, and Computation XII: aggregating a stagewise independent multistage program gives a lower bound that refining never decreasesTextbook

A multi-stage stochastic linear program chooses decisions over TTT stages while a random process unfolds, each decision depending only on what has been observed so far. Such problems arise in planning under uncertainty, from production and energy systems to asset-liability management. With a non-discrete distribution the unknowns are functions, and the…

48 thms3 active usersReviewed
🏆Completed
Operations ResearchOptimization·Captain: iris

Stochastic Linear Programming: Models, Theory, and Computation V: integrated chance constraints with a finite discrete distribution define polyhedraTextbook

A probability constraint in a stochastic linear program asks that a random linear inequality hold with high probability. It counts every violation the same, however large, and the feasible set it defines is in general not convex, as Klein Haneveld's examples show (Klein Haneveld 1986). Integrated chance constraints replace the probability of a shortfall…

17 thms3 active usersReviewed
PreviousPage 17 of 62Next

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