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
Operations ResearchOptimizationTheoretical 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
Information TheoryQuantum InformationStatistical Mechanics·Captain: iris

Tight Information-Theoretic Threshold for Decoded Quantum Interferometry with Local Quantum DecodersResearch Paper

Decoded quantum interferometry (DQI) is a quantum algorithm for sparse constraint problems such as Max-kkk-XORSAT: it prepares a state whose amplitudes favour good assignments by reducing optimization to the decoding of a classical linear code (Jordan et al., Nature 2025). How well DQI does is therefore governed by how well that code can be decoded from the…

25 thms1 active userReviewed
AnalysisCombinatoricsTheoretical Computer Science·Captain: Shuze Chen

Inside the Critical Window of Random 2-SATResearch Paper

Random 2-SAT is the one case of random kkk-SAT whose satisfiability threshold and scaling window are both known. With nnn Boolean variables and mmm random 2-clauses, a formula is satisfiable with probability tending to one when m/n<1m/n<1m/n<1 and unsatisfiable with probability tending to one when m/n>1m/n>1m/n>1, a result proved independently by Chvátal and Reed (FOCS 1992), Goerdt…

22 thms1 active userReviewed
Information TheoryOperations ResearchTheoretical Computer Science·Captain: Shuze Chen

Eliminating Ongoing Interaction in Long-Running Verification AgentsResearch Paper

A long-running verification agent completes a chain of tasks, each of which must be submitted exactly, and it can consult a human expert along the way. Every consultation is paid, and every experiment the agent runs on its own tools is paid. A basic design question is whether the expert must stay available throughout the run, answering questions as they…

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

Optimal Online Stochastic MatchingResearch Paper

In online bipartite matching, mmm offline vertices are known in advance and online vertices arrive one at a time, each revealing its neighbourhood; every arrival must be rejected or irrevocably matched to an unmatched neighbour, and the goal is a large matching. Under adversarial arrivals the Ranking algorithm of Karp, Vazirani and Vazirani is optimal with…

27 thms1 active userReviewed
CombinatoricsComplexity TheoryHarmonic Analysis+1·Captain: Shuze Chen

Low Soundness Linearity Testing on Subsets of the HypercubeResearch Paper

A linearity test reads a function f:F2n→F2f:\mathbb F_2^n\to\mathbb F_2f:F2n​→F2​ at a few random points and accepts or rejects. It is perfectly complete if it always accepts linear functions. It has low soundness if, whenever it accepts with probability at least (1+δ)/2(1+\delta)/2(1+δ)/2, fff agrees with an affine function on at least a (1+s(δ))/2(1+s(\delta))/2(1+s(δ))/2 fraction of inputs, with s(δ)>0s(\delta)>0s(δ)>0…

22 thms1 active userReviewed
Algorithmic Game TheoryEconomicsOperations Research·Captain: Shuze Chen

The Price of Anarchy in Markets for LemonsResearch Paper

Trade in a market for lemons can fail even when trade is efficient: when the seller knows more than the buyer about the quality of the good, a price at which the seller is willing to sell signals bad news to the buyer, and adverse selection can unravel the market (Akerlof 1970). Securities markets, used-asset markets and insurance all share this structure.…

19 thms1 active userReviewed
Linear algebraRandom Matrix TheoryTheoretical Computer Science·Captain: Shuze Chen

Random tensor isomorphism under orthogonal and unitary actions: Smoothed and average-case analysisResearch Paper

Two 3-tensors A,B∈Cn×n×nA,B\in\mathbb C^{n\times n\times n}A,B∈Cn×n×n are unitarily isomorphic when a change of orthonormal basis in each of the three modes turns one into the other. Deciding this, and its robust version (is BBB close to some basis change of AAA?), is the tensor analogue of comparing two matrices up to unitary equivalence. It arises in quantum information, where a…

19 thms1 active userReviewed
Quantum Information·Captain: mikedeng1

Estimating a Transition Point from Gibbs and Ground StatesResearch Paper

Learning a phase transition from a finite quantum system involves two independent choices: how many state copies to observe and how large a system each copy contains. A transition is defined by an infinite-volume limit, whereas every available density matrix belongs to a finite cube with a specified boundary. More copies refine information about that finite…

23 thms1 active userReviewed
cryptographyTheoretical Computer Science·Captain: Shuze Chen

Optimal Semi-Honest Information-Theoretic Secure Multi-Party Computation with Servers and ErasuresResearch Paper

Secure multi-party computation lets parties compute a joint function of private inputs while revealing nothing beyond the output. In the client–server setting, a few clients with inputs delegate the work to nnn servers that have no inputs, and an adversary may corrupt one client and a fraction α\alphaα of the servers. Oblivious transfer (OT) is the basic…

24 thms1 active userReviewed
Theoretical Computer Science·Captain: iris

Initialization with Exponentially Fewer BitsResearch Paper

Wireless sensor networks and ad hoc radio networks often consist of mass-produced devices that start out indistinguishable: they carry no identifiers, run identical code, and share one radio channel. Many distributed algorithms assume that nodes have distinct IDs. So a basic first task is initialization: the nnn nodes must give themselves the distinct IDs …

12 thms1 active userReviewed
Machine LearningTheoretical Computer Science·Captain: Shuze Chen

Agnostic Learning by ImitatingResearch Paper

Given a class CCC of models c:X→[−1,1]c:X\to[-1,1]c:X→[−1,1] and labeled data (x,y)∈X×{±1}(x,y)\in X\times\{\pm1\}(x,y)∈X×{±1}, two learning goals relative to CCC are standard. Agnostic learning (Haussler 1992; Kearns, Schapire and Sellie 1994) asks for a predictor whose absolute error is nearly as small as that of the best model in CCC. Multiaccuracy (Trevisan, Tulsiani and Vadhan 2009; Hébert-Johnson,…

13 thms1 active userReviewed
Information TheoryStatistics·Captain: iris

Functional inequalities from the fundamental limits of Bayesian estimationResearch Paper

Functional inequalities bound how much a function can fluctuate under a probability measure by the size of its gradient. The two central examples are the Poincaré inequality, which bounds the variance, and the log-Sobolev inequality, which bounds the entropy [Gro75]. Their constants control the mixing times of Langevin diffusions and Markov chains, the…

26 thms1 active userReviewed
Graph TheoryTheoretical Computer Science·Captain: iris

Tight Query Depth of Recursive Randomized Greedy MISResearch Paper

A maximal independent set (MIS) of a graph is an inclusion-wise maximal set of pairwise nonadjacent vertices. The randomized greedy MIS (RGMIS) algorithm draws a uniformly random permutation π\piπ of the vertices, scans them in that order, and adds a vertex whenever none of its earlier neighbours has been added. Its output V∗V^*V∗ is the lexicographically first…

45 thms1 active userReviewed
CombinatoricsNumber Theory·Captain: mikedeng1

Quadratic Probing Insertions Are ϵ−(1+o(1))\epsilon^{-(1+o(1))}ϵ−(1+o(1)) TimeResearch Paper

A hash table stores keys in an array and uses a hash value to choose where to begin searching for a free slot. Its insertion cost matters when memory use is high: a small vacant fraction can turn a short search into many memory accesses. Quadratic probing searches at square offsets from the hash. Introduced by Maurer in 1968, it has a long history of use,…

26 thms1 active userReviewed
Complexity TheoryGraph Theory·Captain: mikedeng1

A Fully Polynomial Randomized Approximation Scheme for Hypergraph UnreliabilityResearch Paper

Network unreliability quantifies the risk that independent component failures disconnect a system. A hyperedge models one component connecting a whole set of vertices, so one failure can remove a connection among arbitrarily many endpoints. All-terminal unreliability is the probability that the surviving hypergraph has more than one connected component. The…

29 thms1 active userReviewed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

The Online Steinitz ProblemResearch Paper

In the online Steinitz problem, a sequence of real vectors arrives one vector at a time. Each vector must immediately receive an unused position in a fixed output array. The final order should distribute cancellation across the array, keeping every prefix close to its proportional share of the total. This differs from choosing a permutation after seeing the…

17 thms1 active userReviewed
Bandit AlgorithmsMachine Learning·Captain: mikedeng1

Toward Optimal Switching Regret for Multi-Armed Bandits with Oblivious AdversaryResearch Paper

A multi-armed bandit models a learner that repeatedly chooses one of several actions while observing only the loss of the chosen action. The learner might have benefited from a different action, but the feedback does not reveal that action's loss. A standard benchmark is the best single arm in hindsight. A changing environment calls for a more flexible…

17 thms1 active userReviewed
Markov Chain·Captain: mikedeng1

Learning AI Agents, Market Makers, and Stress in Automated MarketsResearch Paper

Two markets can exhibit the same distribution of individual returns while arranging losses differently in time. For a monitor concerned with consecutive losses, the duration of a stressed interval is a separate object from the frequency of stressed periods. The question here is whether this distinction survives a model in which trades respond to the…

5 thms1 active userReviewed
Graph Theory·Captain: mikedeng1

Adaptive Steps and Certificates for Semi-Streaming Shortest PathsResearch Paper

A graph can have too many edges to keep in memory while its vertices and a sparse collection of edges still fit. In the semi-streaming model, an algorithm reads an insertion-only stream repeatedly and keeps a small working memory between scans. For shortest paths, the number of complete scans is a substantial part of the cost. Assadi, Hoppenworth and…

12 thms1 active userReviewed
Combinatorics·Captain: mikedeng1

Fluid Limits and Upper Bounds for Randomized Greedy MatchingResearch Paper

A matching is a set of graph edges with no shared endpoint. Matching algorithms assign disjoint pairs when each participant can receive at most one partner. A local algorithm can build a matching without inspecting the whole graph, but its decisions can prevent later pairs from forming. The Modified Randomized Greedy algorithm, abbreviated MRG, introduces…

8 thms1 active userReviewed
Graph TheoryTheoretical Computer Science·Captain: mikedeng1

LOCAL LLL in poly(loglog n) RoundsResearch Paper

The variable Lovász Local Lemma concerns systems of constraints whose individual failures are rare and whose interactions are local. A variable may describe a color, a choice of a neighbor, or a random decision in another algorithm. Each constraint inspects its own variables. The aim is to select their values so that every constraint holds simultaneously.…

20 thms1 active userReviewed
Complexity Theory·Captain: mikedeng1

Perfect Local Sampling and Subquadratic Counting below the Hard-Core Uniqueness ThresholdResearch Paper

The hard-core model samples an independent set III of a finite graph with probability proportional to λ∣I∣\lambda^{|I|}λ∣I∣; at λ=1\lambda=1λ=1 this is the uniform distribution on independent sets. It is a standard test case for the computational phase transition in counting and sampling, because the tree-uniqueness threshold …

25 thms1 active userReviewed
Algorithmic Game TheoryMechanism Design·Captain: mikedeng1

The Power of Simple Mechanisms: A Tight eee-Approximation for Gains from Trade in Matching MarketsResearch Paper

A two-sided market brings together buyers who value an item and sellers who hold it at a cost. The first-best gains from trade (GFT) match each trade whose value exceeds its cost. The Myerson–Satterthwaite theorem says that no incentive-compatible, individually rational and budget-balanced mechanism attains this benchmark, even in bilateral trade. So the…

23 thms1 active userReviewed
Graph Theory·Captain: mikedeng1

Two choices suffice: kkk-out sampling leaves O(n/k)O(n/k)O(n/k) intercomponent edges for k≥2k\geq 2k≥2Research Paper

Random kkk-out sampling sparsifies a graph by local choices: every vertex independently picks kkk of its incident edges. The question is how much connectivity information the sample loses, measured by the number of original edges that join distinct components of the sample. Contracting each sampled component leaves exactly these edges, and adding them to a…

17 thms1 active userReviewed
PreviousPage 39 of 48Next

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