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
Algorithmic Game TheoryProbabilityTheoretical Computer Science·Captain: Shuze Chen

Correlated Forest Rounding for Unweighted Nash Social WelfareResearch Paper

In the Nash social welfare (NSW) problem, mmm indivisible items are divided among nnn agents with valuations vi:2M→R≥0v_i:2^M\to\mathbb R_{\ge0}vi​:2M→R≥0​, and the goal is to maximize the geometric mean (∏ivi(Si))1/n\big(\prod_i v_i(S_i)\big)^{1/n}(∏i​vi​(Si​))1/n of the agents' values. The objective sits between utilitarian welfare and max-min fairness and is invariant under rescaling any single valuation,…

16 thms3 active usersReviewed
Algorithmic Game TheoryOperations ResearchTheoretical Computer Science·Captain: Shuze Chen

Efficient Equilibrium Computation in Colonel Blotto GamesResearch Paper

The Colonel Blotto game (Borel, 1921) is the basic model of competitive resource allocation: two players divide fixed budgets among several contests, and each contest goes to the larger allocation. It models military and security planning, elections and R&D races. In the continuous version, allocations are arbitrary nonnegative reals, so each player has a…

29 thms3 active usersReviewed
Functional AnalysisProbabilityTheoretical Computer Science·Captain: mikedeng1

Primal/Dual Method for the Grothendieck ConstantResearch Paper

The real Grothendieck constant KGK_GKG​ measures how much a semidefinite relaxation can overestimate a bilinear ±1\pm1±1 optimization problem. It appears in Banach-space theory, where it is the best constant in Grothendieck's inequality Pis12; in quantum information, where it bounds the violation of correlation Bell inequalities AGT06; and in approximation…

24 thms3 active usersReviewed
Operations ResearchProbabilityTheoretical Computer Science·Captain: mikedeng1

Optimal Contention Resolution from SamplesResearch Paper

A contention resolution scheme receives a random collection of available elements and selects a feasible subset. With a capacity of kkk, feasibility means selecting at most kkk elements. The input can respect capacity on average while exceeding it on particular realizations. A useful selection rule must resolve these conflicts while preserving a guarantee for…

40 thms3 active usersReviewed
🏆Completed
Probability·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
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: Shuze Chen

Tight Algorithms for Conservative Finite-Valued CSPs Parameterized by TreewidthResearch Paper

For an NP-hard problem, "polynomial or not" says nothing about how hard the hard cases are. On graphs of bounded treewidth the finer question is the base of the exponent: many problems are solvable in time ctw⋅nO(1)c^{\mathrm{tw}}\cdot n^{O(1)}ctw⋅nO(1) by dynamic programming over a tree decomposition of width tw\mathrm{tw}tw, and a line of work started by Lokshtanov, Marx and…

26 thms3 active usersReviewed
Linear algebraQuantum Information·Captain: iris

Spectral Structure and Exact Arithmetic of Finite-Feedback Measurement DiscriminationResearch Paper

A receiver that measures a quantum system and reports back through a classical channel with only a few symbols can transmit only part of what the measurement learned. In Qi's manuscript Spectral Structure and Exact Arithmetic of Finite-Feedback Measurement Discrimination (November 2026), the value of such finite-feedback discrimination experiments reduces…

25 thms3 active usersReviewed
🏆Completed
Complexity TheoryLinear OptimizationOperations Research·Captain: Shuze Chen

A Better-than-2 Approximation for k-MedianResearch Paper

In uncapacitated facility location (UFL) one opens a set of facilities, each at a cost, and connects every client to its nearest open facility. In k-median one opens at most kkk facilities and pays only connection costs. The two problems are linked by a Lagrangian relaxation: replacing the constraint ∣S∣≤k|S|\le k∣S∣≤k by a penalty f⋅∣S∣f\cdot|S|f⋅∣S∣ turns k-median into UFL…

25 thms3 active users
Mathematical PhysicsNumerical AnalysisProbability+1·Captain: Shuze Chen

A Fully Polynomial Approximation Algorithm for the Sherrington-Kirkpatrick ModelResearch Paper

The Sherrington–Kirkpatrick (SK) model is the basic mean-field spin glass: for a random symmetric Gaussian matrix AAA, find a spin vector σ∈{−1,1}N\sigma\in\{-1,1\}^Nσ∈{−1,1}N maximizing the energy HN(σ)=12σ⊤AσH_N(\sigma)=\tfrac12\sigma^\top A\sigmaHN​(σ)=21​σ⊤Aσ. Finding the exact maximizer is a hard combinatorial problem in the worst case, and the question of how close polynomial-time algorithms can…

23 thms3 active usersReviewed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

Rounded Potentials Certify Exact Maximum FlowResearch Paper

A maximum flow measures how much material can move from a source to a sink while respecting directed edge capacities and conserving material at other vertices. The classical certificate for its exact value contains both a feasible flow and a separating cut of the same value. The maximum-flow/minimum-cut theorem guarantees that these witnesses exist Ford and…

23 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations ResearchProbability+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
Convex OptimizationGraph TheoryTheoretical Computer Science·Captain: Shuze Chen

Efficient Correlation Clustering in Single-pass Graph Streams: Deterministic and Adversarially RobustResearch Paper

Correlation clustering asks for a partition of a vertex set that agrees as much as possible with pairwise "similar / dissimilar" labels. It is a standard model for deduplication and community detection, introduced by Bansal, Blum and Chawla (2004); minimizing disagreements is APX-hard, and a line of offline work has pushed the approximation ratio from 3 (Ail…

23 thms3 active usersReviewed
Operations ResearchProbabilityTheoretical Computer Science·Captain: Shuze Chen

A PTAS for the Minimum Sum of Radii ProblemResearch Paper

In Minimum Sum of Radii (MSR) one is given a finite metric space (P,d)(P, d)(P,d) with ∣P∣=n|P| = n∣P∣=n and an integer k∈[n]k \in [n]k∈[n], and must partition PPP into at most kkk clusters so as to minimise the sum of their radii, where the radius of a cluster CCC is rad(C)=min⁡p∈Pmax⁡q∈Cd(p,q)\mathrm{rad}(C) = \min_{p \in P} \max_{q \in C} d(p, q)rad(C)=minp∈P​maxq∈C​d(p,q). Equivalently, one covers PPP by at most kkk balls and pays the sum of…

24 thms3 active usersReviewed
Operations ResearchTheoretical Computer Science·Captain: Shuze Chen

Fully Dynamic Weighted Set Cover: Worst-Case Recourse and Update TimeResearch Paper

In weighted set cover, a universe of nnn elements and a family of sets with positive costs are given, and the task is a cheapest subfamily whose union covers the universe. The greedy algorithm is an O(log⁡n)O(\log n)O(logn)-approximation, and this is essentially optimal for polynomial-time algorithms. In the fully dynamic setting, elements are inserted into and deleted from…

25 thms3 active usersReviewed
🏆Completed
CombinatoricsOperations Research·Captain: mikedeng1

Improved Bounds for Online Matching with Random Edge ArrivalsResearch Paper

An online matching algorithm receives edges sequentially and immediately decides whether to accept each one. Accepted edges must have disjoint endpoints, and decisions are irrevocable. This captures a basic allocation constraint: an accepted pair consumes both of its participants, while future opportunities remain unknown. The order in which opportunities…

32 thms3 active usersReviewed
🏆Completed
Computational Geometry·Captain: mikedeng1

Tight Coreset Bounds for (k,z)(k,z)(k,z)-Clustering in Euclidean and Doubling MetricsResearch Paper

A coreset compresses a clustering dataset into a weighted subset whose cost approximates the original cost for every permitted choice of centers. An optimization algorithm can work on that subset after the input has been read. The number of retained locations therefore matters independently of the time needed to inspect the original data. The question here…

17 thms3 active usersReviewed
Algorithmic Game TheoryTheoretical Computer Science·Captain: iris

Breaking the One-Player Extension Barrier: History-Aware Repair for Multiplayer Approximate Nash EquilibriaResearch Paper

Every finite game has a Nash equilibrium, but computing one is PPAD-complete already for two players (Chen–Deng–Teng 2009; Daskalakis–Goldberg–Papadimitriou 2009) and FIXP-complete for three or more (Etessami–Yannakakis 2010). For payoffs normalized to [0,1][0,1][0,1] the computational question therefore becomes: how small an error ε\varepsilonε can a polynomial-time…

35 thms3 active usersReviewed
🏆Completed
Operations ResearchProbability·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
Algorithmic Game TheoryConvex Optimization·Captain: mikedeng1

Robustly Obedient Data Driven Persuasion under State-dependent Sender PayoffsResearch Paper

In Bayesian persuasion (Kamenica and Gentzkow, 2011, https://doi.org/10.1257/aer.101.6.2590), a Sender commits to a signaling policy that maps the state of the world to recommendations, and a Receiver who knows the prior updates on the recommendation and acts. The standard analysis assumes the Sender knows the prior. In many applications the Sender instead…

8 thms3 active usersReviewed
Graph Theory·Captain: mikedeng1

Deterministic directed minimum cut via capacity-selected terminalsResearch Paper

A directed minimum cut measures the least total capacity whose removal prevents some vertex from reaching another. When both endpoints are prescribed, maximum flow determines this value. When only a root is prescribed, or neither endpoint is fixed, the algorithm must also locate an appropriate terminal. This distinction matters in algorithms that use…

14 thms3 active usersReviewed
CombinatoricsOperations Research·Captain: mikedeng1

Proximity Theorem and FPT Algorithm for Minimum Group-labeled Matroid BasesResearch Paper

A matroid describes a finite family of feasible subsets closed under taking subsets, with an exchange property that makes all maximal feasible subsets have the same size. Those maximal subsets are its bases. Spanning trees of a connected graph give one familiar example. A real cost on each element induces an additive cost on each base. Adding a constraint…

15 thms3 active usersReviewed
🏆Completed
ProbabilityTheoretical 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
Linear OptimizationOperations Research·Captain: mikedeng1

A Fixed-Parameter Algorithm for 4-Block Integer ProgrammingResearch Paper

Many integer optimization models describe small local decisions connected through shared resource constraints. A 4-block integer program also allows a small vector of global decisions to enter every local system. Scheduling, transportation, production planning and stochastic network models motivate these structures; the pinned submission discusses these…

31 thms3 active usersReviewed
🏆Completed
Graph TheoryOperations Research·Captain: mikedeng1

A Deterministic Near-Linear Time Approximation Algorithm for Restricted Shortest Paths in Directed GraphsResearch Paper

The restricted shortest paths problem asks for a route that is short while respecting a separate cost budget. Travel time and monetary cost need not favor the same route. The same distinction appears in quality-of-service routing, where delay is optimized subject to another resource constraint. Ashvinkumar discusses these applications and the difficulty of…

16 thms3 active usersReviewed
Graph TheoryProbability·Captain: mikedeng1

Optimal Sample Complexity for Max-CutResearch Paper

A maximum cut partitions a graph's vertices into two parts to maximize the total weight of edges between them. When a graph is too large to inspect in full, estimating this optimum from a small sample can reduce the amount of graph data needed. A value coreset is a small reweighted graph whose maximum-cut value approximates the original value. Returning a…

34 thms3 active usersReviewed
PreviousPage 23 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