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,760 completed

Missions

Open551Completed1760All2311
Complexity TheoryGraph TheoryTheoretical Computer Science·Captain: mikedeng1

Shortest Disjoint Paths in Planar GraphsResearch Paper

This mission contains the full arbitrary-position search goal, all seventeen numbered milestones, thirteen local definition items and a published planarity reference. The theorem proofs are open Lean declarations.

32 thms1 active userReviewed
Computational GeometryProbabilityTheoretical Computer Science·Captain: Shuze Chen

Adversarially Robust Streaming Algorithms for (k,z)(k, z)(k,z)-ClusteringResearch Paper

kkk-Median and kkk-Means are among the most studied clustering problems. Both are cases of (k,z)(k,z)(k,z)-clustering in Rd\mathbb R^dRd: given a dataset PPP, find at most kkk centers that minimise the sum of the zzz-th powers of the Euclidean distances from the points to their nearest center. In the dynamic geometric stream model of Indyk (2004), the data arrive as insertions and…

11 thms1 active userReviewed
AnalysisOperations ResearchProbability+1·Captain: Shuze Chen

Gain-Sharing Optimization in Randomized Primal–Dual Analysis: Structure and CertificationResearch Paper

Randomized primal–dual analysis is the standard way to prove competitive ratios for online matching and allocation: the algorithm's gain is split between dual variables, and a uniform expected dual-feasibility factor γ\gammaγ certifies a γ\gammaγ-competitive guarantee by weak duality (Devanur, Jain, Kleinberg 2013). The split is governed by a gain-sharing…

23 thms1 active userReviewed
Machine LearningProbabilityStatistics+1·Captain: Shuze Chen

Tensor Decomposition Beyond the Spectral ThresholdResearch Paper

Tensor decomposition asks, given all entries of an order-kkk tensor T=∑i=1mvi⊗kT=\sum_{i=1}^m v_i^{\otimes k}T=∑i=1m​vi⊗k​, to recover the rank-one components viv_ivi​ up to the symmetries of the problem. It underlies algorithms for dictionary learning, topic models and mixtures of spherical Gaussians. For general tensors it is intractable: computing the rank of a third-order tensor is…

18 thms1 active userReviewed
Convex OptimizationQuantum InformationTheoretical Computer Science·Captain: Shuze Chen

Convex optimization on moment polytopes: Hadamard mirror descent and efficient algorithms for quantum functionals and other tensor parametersResearch Paper

Strassen's asymptotic spectrum of tensors governs the asymptotic rank and subrank of tensors, and with them questions such as the exponent of matrix multiplication. The quantum functionals of Christandl, Vrana and Zuiddam (CVZ23) were the first explicit family of universal spectral points for complex tensors of arbitrary order. They are defined as maxima of…

20 thms1 active userReviewed
Graph TheoryOperations Research·Captain: mikedeng1

Optimal Approximation for Constrained Correlation Clustering via RepulsionResearch Paper

Correlation clustering groups vertices when pairwise preferences can conflict: a positive pair prefers one cluster, and a negative pair prefers different clusters. The number of clusters is unrestricted. Must-links and cannot-links add requirements that every returned partition must satisfy. This distinction matters when a preference can be traded against…

40 thms1 active userReviewed
Algorithmic Game TheoryCombinatoricsProbability·Captain: mikedeng1

Single-Sample Prophet Inequalities: A Combinatorial to Single-Item ReductionResearch Paper

In an online allocation problem, buyers arrive one at a time and each must be served irrevocably on arrival; the benchmark is the prophet, who sees all valuations in advance and allocates optimally. When the valuations are random with known distributions, guarantees of this kind are prophet inequalities. A much weaker information model gives the algorithm…

39 thms1 active userReviewed
Computational ComplexityOperations Research·Captain: mikedeng1

Settling the Approximability of Submodular Facility LocationResearch Paper

Submodular facility location asks how to assign clients to facilities when the cost of serving a group has diminishing marginal increments. All facilities share the same cost function. This homogeneous setting distinguishes the question from variants with a different function at each facility. It allows economies of scale while retaining the geometric…

25 thms1 active userReviewed
Operations ResearchTheoretical Computer Science·Captain: mikedeng1

A General Technique for Metrical Task Systems with Action PredictionsResearch Paper

An online movement problem reveals requests one at a time. A decision maker must serve the current request without seeing the remaining requests, and moving between possible decisions has a cost. In caching, the decision records the contents of a cache; in server problems, it records server locations. Predictions can recommend the next decision, but an…

10 thms1 active userReviewed
Operations ResearchProbabilityTheoretical Computer Science·Captain: Shuze Chen

Improved Algorithms in the Random-Order Model: Knapsack, GAP, and BeyondResearch Paper

Online services allocate limited resources to requests arriving over time. Accepting a request earns value but uses capacity a later, more valuable request might have needed, and decisions cannot be revised. The simplest such model is online knapsack; the generalized assignment problem (GAP) extends it to several machines on which an item may have different…

16 thms1 active userReviewed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: Shuze Chen

Precedence-Constrained Decision Trees and CoveringsResearch Paper

In the Optimal Decision Tree problem an unknown target hypothesis h∗h^*h∗ from a finite set HHH of nnn hypotheses must be identified by adaptively performing tests from a family TTT of mmm tests; each test partitions HHH and its reply reveals the block that contains h∗h^*h∗. The problem goes back to Garey and Graham (1974) and appears in medical diagnosis, troubleshooting…

23 thms1 active userReviewed
Algorithmic Game TheoryEconomicsMechanism Design·Captain: Shuze Chen

Otter: A Provably MEV-Resilient Automated Market Maker via Surplus RedistributionResearch Paper

An automated market maker (AMM) is a smart contract that holds reserves of two tokens XXX and YYY and trades with anyone along a fixed pricing curve. On a blockchain the trades of one block are sequenced by a builder, who may also insert trades of its own. Ordering power yields maximal extractable value (MEV): in a sandwich attack the builder buys before a…

18 thms1 active userReviewed
CombinatoricsGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

Better Bounds for Semi-Streaming Maximum Matching via Load BalancingResearch Paper

Graphs too large to store are often processed as a stream: the edges arrive one at a time, in an order nobody controls, and an algorithm may read the stream a few times (passes) while keeping only a small summary in memory. The semi-streaming model of Feigenbaum, Kannan, McGregor, Suri and Zhang (FKM+05) allows O~(n)=O(n⋅polylog n)\tilde O(n)=O(n\cdot\mathrm{polylog}\,n)O~(n)=O(n⋅polylogn) bits…

24 thms1 active userReviewed
CombinatoricsOperations Research·Captain: mikedeng1

Breaking the √3 Barrier for Maximum Weighted 3-Set PackingResearch Paper

A weighted 3-set packing instance describes requests that each use at most three resources. Two requests can be accepted together exactly when their resource sets are disjoint. Their values need not be equal or comparable in magnitude. The objective is to choose compatible requests with maximum total value. This setting includes weighted three-dimensional…

18 thms1 active userReviewed
Dynamic ProgrammingOperations ResearchTheoretical Computer Science·Captain: mikedeng1

A QPTAS for Stochastic Scheduling of Bernoulli JobsResearch Paper

Scheduling systems often know a job's processing-time distribution before they know its realized duration. An adaptive policy chooses the next job after observing previous outcomes. For Bernoulli jobs, a job either completes immediately or occupies a machine for its full positive size. This isolates the scheduling risk created by a small probability of a…

25 thms1 active userReviewed
Complexity TheoryDiscrete GeometryOperations Research+1·Captain: mikedeng1

4-Block Integer Programming is in FPTResearch Paper

An integer program chooses integer values for variables subject to linear equations and bounds, while minimizing a specified objective. Models with repeated local constraints occur in scheduling, allocation and stochastic optimization. Their size can grow with the number of local blocks even when the form of each block stays small. A useful algorithm must…

14 thms1 active userReviewed
Linear algebraMathematical PhysicsQuantum Information·Captain: mikedeng1

Improved classical optimization of fermionic Hamiltonians beyond Gaussian statesResearch Paper

Finding the largest eigenvalue of an interacting fermionic Hamiltonian is a basic optimization problem in quantum chemistry and many-body physics. Even when the Hamiltonian is a low-degree polynomial in Majorana operators, it acts on a space of dimension 2n2^n2n, and computing its extremal eigenvalue to inverse-polynomial precision is QMA-hard. Classical…

15 thms1 active userReviewed
CombinatoricsComplexity Theory·Captain: mikedeng1

Randomized Query Lower Bounds for Submodular Function MinimizationResearch Paper

Submodular function minimization asks for a least-value subset when the only access to a set function is through queries of its values. It provides a common optimization framework for functions with diminishing marginal returns. Even after restricting attention to this structured class, the number of oracle calls needed to solve the problem remains a…

21 thms1 active userReviewed
Graph TheoryProbability·Captain: iris

Adaptivity Gaps for Influence Maximization: Percolation and DepletionResearch Paper

In influence maximization one selects at most kkk vertices of a network, the seeds, so as to maximize the expected number of vertices reached by a random cascade started from them. Kempe, Kleinberg and Tardos (KKT03) introduced the independent cascade model, in which every arc of the network is live independently with a known probability, and showed that the…

41 thms1 active userReviewed
Operations ResearchTheoretical Computer Science·Captain: iris

Optimal Online Joint Replenishment with Linear DelaysResearch Paper

The joint replenishment problem (JRP) is a classical model from inventory theory and one of the basic models of online algorithms with delay. A retailer buys several commodities from one supplier in response to customer demand: combining purchases into one shipment saves delivery cost, but waiting to combine them delays customers. The same trade-off appears…

24 thms1 active userReviewed
Operations ResearchTheoretical Computer Science·Captain: iris

A (3+ϵ)(3+\epsilon)(3+ϵ)-Approximation for Fair kkk-Means and a Matching Lower BoundResearch Paper

The kkk-means problem asks for at most kkk centers in Rd\mathbb R^dRd minimizing the sum of squared distances from nnn input points to their nearest centers. When the points are people, the composition of a cluster can matter as much as its cost: a clustering used for loan approval or school assignment may concentrate a protected group in one cluster. The group-balanc…

26 thms1 active userReviewed
Algorithmic Game TheoryMechanism DesignProbability·Captain: iris

The Exact Welfare Guarantee of Fixed-Price Bilateral TradeResearch Paper

A seller owns one item and a buyer may want it; their values are private and independent. Myerson and Satterthwaite showed that no mechanism is at once efficient, incentive compatible, individually rational and budget balanced (MS83). The simplest mechanism that keeps every property but efficiency is a fixed price: post one price, and trade happens if both…

27 thms1 active userReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

Online and Fully-Dynamic SortingResearch Paper

Keeping data in order while it changes is a basic algorithmic task. In online sorting, introduced by Aamand, Abrahamsen, Beretta and Kleist (AABK23), real numbers arrive one at a time and must be placed immediately into an array of nnn cells; the aim is to keep the sum of absolute differences between neighbouring stored elements small compared with the sorted…

36 thms1 active userReviewed
Algorithmic Game TheoryTheoretical Computer Science·Captain: iris

Arbitrarily Slow Polynomial Convergence of Fictitious PlayResearch Paper

Fictitious play (Brown, 1951) is one of the oldest dynamics for computing a Nash equilibrium of a two-player zero-sum game: at each step, each player best responds to the empirical distribution of the opponent's past actions. Robinson (1951) proved that the empirical strategies converge to the equilibrium set, and Shapiro (1958) extracted the upper bound …

31 thms1 active userReviewed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: iris

Weighted Set Cover with Constant Worst-Case Recourse: From Exponential to Best-Known Update TimeResearch Paper

In fully dynamic weighted set cover, a fixed family of sets with positive costs is given once, and elements of the universe are then inserted into and deleted from an active set. After every update an algorithm must hold a subfamily that covers the active elements at nearly minimum cost. Besides the approximation ratio, two resources are measured per…

24 thms1 active userReviewed
PreviousPage 89 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