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
Convex OptimizationMachine LearningRandom Matrix Theory+1·Captain: mikedeng1

The Power of Convex Relaxation: Near-Optimal Matrix Completion I: Exact Nuclear-Norm Recovery with Quadratic Dependence on the RankResearch Paper

Matrix completion asks to recover a low-rank matrix from a small random subset of its entries. It models collaborative filtering (a ratings matrix with most entries missing), sensor-network localization from partial distance matrices, and system identification. The natural estimator, the matrix of least rank that agrees with the observations, is NP-hard to…

14 thms2 active usersReviewed
AnalysisPartial Differential Equations·Captain: LG

Hairer: A Theory of Regularity Structures I — The Reconstruction TheoremResearch Paper

Several equations of mathematical physics are written down formally but have no classical meaning as stated. The dynamical Φ34\Phi^4_3Φ34​ model ∂tu=Δu−u3+ξ\partial_t u = \Delta u - u^3 + \xi∂t​u=Δu−u3+ξ on the three-dimensional torus, the KPZ equation ∂th=∂x2h+(∂xh)2−∞+ξ\partial_t h = \partial_x^2 h + (\partial_x h)^2 - \infty + \xi∂t​h=∂x2​h+(∂x​h)2−∞+ξ, and the parabolic Anderson model ∂tu=Δu+u ξ\partial_t u = \Delta u + u\,\xi∂t​u=Δu+uξ all…

13 thms2 active usersReviewed
Functional AnalysisMathematical Physics·Captain: LG

Wilson Yang-Mills ConstructionResearch Paper

Yang–Mills theory is the gauge-field framework underlying the strong and electroweak interactions. A Euclidean Yang–Mills field is a connection valued in the Lie algebra of a compact group, with action 14∫R4∥F∥2\frac14\int_{\mathbb R^4}\lVert F\rVert^241​∫R4​∥F∥2 for curvature FFF. Physically it is extremely well tested, yet constructing a four-dimensional interacting quantum…

8 thms1 active userReviewed
Stochastic Systems·Captain: WillR

Kyprianou (2006), Chapter 9: Applications to Optimal Stopping ProblemsTextbook

Chapter 9 of Andreas Kyprianou's introductory lectures develops optimal stopping and optimal stopping games for Lévy processes, as described in Kyprianou (2006). A stopping problem asks when an observer should exercise a reward that depends on the evolving process. Time discounting competes with the possibility of a more favourable future value. The jumps…

42 thms1 active userReviewed
Stochastic Systems·Captain: WillR

Kyprianou (2006), Chapter 7: Lévy Processes at First Passage and Insurance RiskTextbook

First-passage questions concern the first time a stochastic process moves beyond a fixed level and the behaviour at that crossing. For a Lévy process, the barrier may be passed by a jump or reached continuously, so distributions of crossing times, jump overshoots and the last maximum before passage have different features. These quantities are also relevant…

89 thms1 active userReviewed
Stochastic Systems·Captain: WillR

Kyprianou (2006), Chapter 6: The Wiener–Hopf FactorisationTextbook

A Lévy process is a stochastic process with stationary independent increments and càdlàg sample paths. Its jumps and its continuous fluctuations can each produce new record maxima. In the bounded-variation examples considered earlier in the book, these records can sometimes be indexed by an elementary counting process. In general, a process may make…

76 thms1 active userReviewed
Information TheoryReinforcement LearningTheoretical Computer Science·Captain: iris

Deep Q-Operator: Fixed-Accuracy Adaptive Information and Shared Bellman DecisionsResearch Paper

A Bellman decision compares the scores of a few actions, each built from maxima of a shared critic: ta(Q)=ra+γ∑iwaimax⁡h≤KiQi(h)t_a(Q)=r_a+\gamma\sum_i w_{ai}\max_{h\le K_i}Q_i(h)ta​(Q)=ra​+γ∑i​wai​maxh≤Ki​​Qi​(h) with 0<γ<10<\gamma<10<γ<1. In approximate dynamic programming and value-based reinforcement learning the critic is learned from costly scalar values, so a basic question is how much information about the critic a…

37 thms1 active userReviewed
Machine LearningTheoretical Computer Science·Captain: mikedeng1

Sketching Language Models for Context AttributionResearch Paper

Context attribution asks how parts of a prompt affect a chosen measurement of a language model's output. For a prompt with nnn tokens, leave-one-out attribution records the measurement after deleting each token individually. Direct evaluation takes nnn model calls. Liaw, Mehta, Velegkas and Zhou study when all these values can be estimated with fewer calls,…

20 thms1 active userReviewed
Convex OptimizationMachine LearningOptimization+1·Captain: Shuze Chen

Bias-Reduced and Parallel Heavy-Tailed Stochastic Convex Optimization in ℓp\ell_pℓp​ GeometriesResearch Paper

Stochastic convex optimization (SCO) asks for an approximate minimizer of a convex function that can only be probed through noisy subgradients. Two features of modern instances are not captured by the textbook Euclidean, bounded-variance setting. First, the natural geometry is often an ℓp norm with p>2p>2p>2: the feasible region is an ℓp ball and the Lipschitz…

15 thms1 active userReviewed
Operations ResearchOptimization·Captain: mikedeng1

Random-Order Online Facility Location Beyond Uniform Opening CostsResearch Paper

A facility-location decision trades a one-time setup cost against repeated travel or service costs. In the online facility-location problem, demand points arrive one at a time, and an arriving point must immediately receive service from a facility that has already opened. An expensive facility may be worthwhile for many nearby requests, but those future…

29 thms1 active userReviewed
CombinatoricscryptographyTheoretical Computer Science·Captain: Shuze Chen

Algorithms for Sparse LWE and LPN with Small SecretsResearch Paper

Learning with errors (LWE) asks to tell noisy linear equations b=As+e mod qb = As + e \bmod qb=As+emodq apart from uniformly random right-hand sides; its hardness underlies most lattice-based cryptography (Regev 2005). Sparse LWE, where every row of AAA has only kkk nonzero entries, was introduced by Jain, Lin and Saha (2024) as a source of efficient primitives, and the modulus-qqq ana…

21 thms1 active userReviewed
Computational GeometryOptimizationTheoretical 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
CombinatoricsTheoretical Computer Science·Captain: Shuze Chen

Catalan Hashing: Efficient Linear Probing for Variable-Length ItemsResearch Paper

Linear probing stores each key in the first free cell at or after its hash position, so a query is a single forward scan over a contiguous region of memory. That locality is why linear probing is the default hash table in practice and in external memory, and its analysis goes back to Knuth's 1963 note and its many refinements (Knuth, The Art of Computer…

10 thms1 active userReviewed
Quantum InformationStatistics·Captain: iris

Quantum Multivariate Mean Estimation: O~(n)\tilde O(n)O~(n) Queries Give Error TrΣ/n+∥Σ∥log⁡(1/δ)/n\sqrt{\mathrm{Tr}\Sigma/n}+\sqrt{\|\Sigma\|\log(1/\delta)/n}TrΣ/n​+∥Σ∥log(1/δ)/n​ if n≤dn\le dn≤d, dTrΣlog⁡(d/δ)/n\sqrt{d\mathrm{Tr}\Sigma}\log(d/\delta)/ndTrΣ​log(d/δ)/n if n>dn>dn>dResearch Paper

Estimating the mean of a random vector from samples is a basic task in statistics, learning and simulation. Classically, the optimal answer is known: with nnn samples, the sub-Gaussian estimators of Lugosi and Mendelson achieve error Tr(Σ)/n+∥Σ∥log⁡(1/δ)/n\sqrt{\mathrm{Tr}(\Sigma)/n}+\sqrt{\|\Sigma\|\log(1/\delta)/n}Tr(Σ)/n​+∥Σ∥log(1/δ)/n​ in Euclidean norm with probability 1−δ1-\delta1−δ, for every…

24 thms1 active userReviewed
AnalysisOperations ResearchOptimization+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 LearningStatisticsTheoretical Computer Science·Captain: Shuze Chen

The Sample Complexity of Multi-Class OmnipredictionResearch Paper

A predictor of class probabilities is often used by many downstream decision makers, each with its own loss. Omniprediction (Gopalan, Kalai, Reingold, Sharan, Wieder, 2022, arXiv:2109.05389) asks for one predictor whose best-response post-processing competes, for every loss in a class simultaneously, with every rule in a benchmark class. For binary labels…

20 thms1 active userReviewed
Machine LearningOptimizationStatistics+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
Algorithmic Game TheoryMechanism DesignOperations Research·Captain: Shuze Chen

One Trap Is Enough: The Structure and Complexity of Robust Contracts for Sequential SearchResearch Paper

In research and development, procurement and delegated experimentation, an agent tries costly options with random outcomes one at a time, keeps the best outcome found, and decides when to stop; the principal sees only the outcome that is finally submitted and pays a wage that depends on it. Without an incentive problem this is Pandora's box problem (Weitzman…

19 thms1 active userReviewed
Theoretical Computer Science·Captain: Shuze Chen

An Information Hierarchy of Privacy Filters and OdometersResearch Paper

Differential privacy is usually analysed for a fixed sequence of releases, but in practice an analyst queries a database adaptively, choosing each request after seeing earlier answers, and the privacy cost of the next answer may itself depend on what has been released. Two kinds of procedures control the cumulative privacy loss of such an interaction: privac…

11 thms1 active userReviewed
Algorithmic Game TheoryOperations Research·Captain: Shuze Chen

Order-selection Prophet Inequality (Almost) Goes I.I.D.Research Paper

In the prophet inequality a gambler sees independent nonnegative values V1,…,VnV_1,\dots,V_nV1​,…,Vn​ with known distributions one at a time and may accept at most one, irrevocably, when it is revealed; the benchmark is the prophet's E[max⁡iVi]\mathbb E[\max_i V_i]E[maxi​Vi​]. In an adversarial order the best ratio is 1/21/21/2 (Krengel–Sucheston 1977; Samuel-Cahn 1984). In the order-selection varian…

22 thms1 active userReviewed
Random Matrix TheoryTheoretical Computer Science·Captain: Shuze Chen

Improved Bounds for Certifying Injective Norm of Sparse Random TensorsResearch Paper

The injective norm of a symmetric tensor is the largest value of its multilinear form on the unit sphere. For matrices it is the largest absolute eigenvalue and is computable in polynomial time; for tensors of order k≥3k\ge3k≥3 computing it, or even approximating it, is NP-hard in the worst case (Hillar–Lim 2013). For random tensors the injective norm is small…

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

Minimizing Key Schedules for Key-Alternating CiphersResearch Paper

A key-alternating cipher (KAC) encrypts a block mmm of a finite abelian group GGG by alternately adding round keys and applying fixed public permutations: x0=k0−mx_0=k_0-mx0​=k0​−m, xj=kj−πj(xj−1)x_j=k_j-\pi_j(x_{j-1})xj​=kj​−πj​(xj−1​). Its provable security in the random permutation model is well understood when the t+1t+1t+1 round keys are independent and uniform (Hoang–Tessaro 2016), but real ciphers derive…

13 thms1 active userReviewed
cryptographyInformation TheoryTheoretical Computer Science·Captain: Shuze Chen

The Information-Theoretic Limits of Hiding Among Decoys in the Shuffle ModelResearch Paper

Hiding a genuine secret among plausible decoys is a recurring pattern in security and privacy. A honeyword system stores a user's real password together with n−1n-1n−1 fake ones and raises an alarm when a fake one is used (Juels–Rivest 2013). A computationally unbounded adversary who decrypts a ciphertext under every key of a small key space obtains one genuine…

16 thms1 active userReviewed
CombinatoricsMarkov ChainTheoretical Computer Science·Captain: mikedeng1

Tight Variable-Occurrence Bounds and Exponential Separations for Moser–Tardos and WalkSAT on 3-CNFResearch Paper

WalkSAT and the Moser–Tardos algorithm (MT) are the two standard clause-driven local-repair procedures for satisfiability. Both keep a complete assignment and repeatedly pick an unsatisfied clause. WalkSAT flips one variable of it (Papadimitriou 1991, Schöning 1999); MT resamples all of its variables with fresh random bits, which is the algorithmic form of…

28 thms1 active userReviewed
Complexity TheoryGroup Theory·Captain: mikedeng1

On Testing Finite GroupsResearch Paper

A multiplication table describes a binary operation on a finite labelled set. Reading the whole table requires quadratically many entries. Property testing instead asks for a decision from substantially fewer entries: accept a genuine group and reject an operation that requires many changes to become any group. This question concerns algorithms that receive…

36 thms1 active userReviewed
PreviousPage 37 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