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
Machine LearningStatisticsTheoretical Computer Science·Captain: iris

The Conditional Geometry of Statistical VerificationResearch Paper

A learner that hands over a classifier can be asked to justify it. In statistical verification an untrusted prover proposes a hypothesis and a verifier, using its own private labeled samples, either accepts a hypothesis whose risk is within ε\varepsilonε of the best in the class or rejects. The question is how many private samples verification needs compared…

46 thms3 active usersReviewed
Complexity TheoryInformation Theory·Captain: iris

Can Many Instances Be Cheaper Than One? The Price of Agreement in EliminationResearch Paper

Direct-sum and direct-product questions ask how the cost of solving kkk independent instances of a communication problem relates to the cost of one. Elimination asks for much less than computing: given kkk instances, the parties only have to output some answer vector σ∈{0,1}k\sigma\in\{0,1\}^kσ∈{0,1}k that is not the true one. Guessing a uniformly random σ\sigmaσ already errs…

36 thms3 active usersReviewed
CombinatoricsRandom Matrix TheoryTheoretical Computer Science·Captain: iris

Stable and Online Algorithms for Random Matrix DiscrepancyResearch Paper

Matrix discrepancy asks for signs σ∈{−1,1}N\sigma\in\{-1,1\}^Nσ∈{−1,1}N that make a signed sum of matrices small in operator norm. The worst-case question is the Matrix Spencer conjecture. This mission is about the average case: the matrices are independent random symmetric Gaussian matrices, and the question is at what density a polynomial-time algorithm finds good signs (Kı…

24 thms3 active usersReviewed
CombinatoricsMathematical PhysicsTheoretical Computer Science·Captain: iris

On Zeros and Algorithms for Disordered Systems II: The Antiferromagnetic Ising Model up to Kesten–StigumResearch Paper

The antiferromagnetic Ising model is a standard test case for the complexity of approximate counting. On graphs of maximum degree ddd the picture is settled: polynomial-time approximate counting, rapid mixing of Glauber dynamics, strong spatial mixing and the absence of zeros of the partition function all hold up to the uniqueness threshold …

35 thms3 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Differentially Private Verification of Distribution PropertiesResearch Paper

A distribution property verifier has sample access to an unknown distribution DDD and wants to decide whether DDD has a property PPP (uniformity, independence, a bounded support size) or is far from every distribution with that property. Testing alone can need many samples; an untrusted prover who knows DDD can sometimes cut the cost, provided the verifier can…

27 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
Algorithmic Game TheoryOperations Research·Captain: iris

Mean-only Prophet InequalitiesResearch Paper

A prophet inequality compares an online decision maker, who sees independent random values X1,…,XnX_1,\dots,X_nX1​,…,Xn​ one at a time and may accept at most one of them, with a prophet who sees all of them and receives X∗=max⁡iXiX^*=\max_i X_iX∗=maxi​Xi​. The classical guarantees assume that the distribution of every value is known. In pricing applications this is rarely the case: a seller…

31 thms3 active usersReviewed
Markov ChainTheoretical Computer Science·Captain: iris

Code Swendsen-Wang DynamicsResearch Paper

Sampling from Gibbs distributions near and below a phase transition is the hard regime for Markov chain methods, because local dynamics take exponentially long to cross energy barriers. For the Ising model the remedy is the global update of Swendsen and Wang. Quantum code Hamiltonians are the minimal models of topological phases, and Hangleiter, Ju and…

31 thms3 active usersReviewed
Mathematical PhysicsQuantum InformationStatistical Mechanics·Captain: iris

Parisi formula and product-state optimization of quantum mixed p-spin HamiltoniansResearch Paper

Random Hamiltonians with many-body interactions are the quantum counterpart of classical mean-field spin glasses. They are a test bed for two questions in quantum information: how close product states come to the true ground state, and which optimization problems are easy on average though hard in the worst case. For worst-case two-local Hamiltonians,…

77 thms3 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

A Resolution of Friedgut's Conjecture on Influential CoalitionsResearch Paper

A coalition of coordinates of a Boolean function is influential if, after the other coordinates are drawn at random, its members can choose their own values so as to force the output. The question comes from collective coin flipping, introduced by Ben-Or and Linial (FOCS 1985): in a one-round protocol with independent uniform messages, a coalition is a set…

22 thms3 active usersReviewed
Harmonic AnalysisMachine LearningStatistics+1·Captain: iris

Learning Mixtures with Unknown Scales: Sharp Dependence on SeparationResearch Paper

Finite mixture models describe a heterogeneous population as a weighted combination of component distributions. Recovering the locations, scales and weights of the components from samples is a central problem in statistics and learning theory, with a long line of work on Gaussian mixtures and other parametric families (Kalai, Moitra, Valiant 2010; Moitra,…

27 thms3 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Tight Depth Lower Bounds for Stretch AmplificationResearch Paper

A pseudorandom generator (PRG) with stretch n↦Nn\mapsto Nn↦N is an efficiently computable function G:{0,1}n→{0,1}NG:\{0,1\}^n\to\{0,1\}^NG:{0,1}n→{0,1}N, N>nN>nN>n, whose random outputs no polynomial-time observer can tell from uniform NNN-bit strings. A generator of very small stretch n↦n+1n\mapsto n+1n↦n+1 is often considerably easier to build from a hardness assumption, while key applications need a larger…

28 thms3 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

The Communication Complexity of Verifying Distribution PropertiesResearch Paper

An untrusted analyst holds many samples from an unknown distribution over [N][N][N] and claims that the distribution has some property: for example, that it is close to uniform or has large support. Interactive proofs for distribution properties (Chiesa–Gur 2018, following Goldwasser–Micali–Rackoff) let a verifier with few samples check such a claim by talking to…

26 thms3 active usersReviewed
CombinatoricsOperations ResearchTheoretical Computer Science·Captain: iris

Optimal Online Bin Covering across Stochastic ModelsResearch Paper

In bin covering, items with sizes in (0,1](0,1](0,1] are assigned to bins, and a bin counts when the items in it have total size at least 111. The problem models threshold objectives: packages that must reach a minimum weight, batches that must reach a minimum volume. Its offline theory parallels bin packing with the objective reversed. Assmann, Johnson, Kleitman and…

35 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
Graph TheoryLinear algebraTheoretical Computer Science·Captain: iris

Incremental All-Pairs Effective Resistance in Almost-Linear TimeResearch Paper

The effective resistance between two vertices of a graph with edge conductances is the energy of the electrical flow that sends one unit of current between them. More generally, a demand d∈RVd\in\mathbb R^Vd∈RV with zero sum has energy d⊤LG†dd^\top L_G^\dagger dd⊤LG†​d, where LGL_GLG​ is the graph Laplacian. These quantities drive spectral sparsification (Spielman–Srivastava, SIAM…

35 thms3 active usersReviewed
Harmonic AnalysisOptimizationTheoretical Computer Science·Captain: iris

Hardness of Approximation for Polynomial Optimization over Sphere for Linear Programming Relaxation HierarchyResearch Paper

Maximizing a homogeneous polynomial PPP of degree ddd over the unit sphere, ∥P∥∞=max⁡x∈Sn−1∣P(x)∣\|P\|_\infty=\max_{x\in S^{n-1}}|P(x)|∥P∥∞​=maxx∈Sn−1​∣P(x)∣, is the spectral norm of a symmetric tensor. It is NP-hard already for order-three tensors (Hillar–Lim 2013), so the useful questions are approximation and certification: find a tractable upper bound and measure how far it can be from the truth.

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

Nash Equilibria, Variational Inequalities, and Fixed Points: Beating Brute Force via Smoothed AnalysisResearch Paper

Computing a Nash equilibrium of a finite game is a basic problem of algorithmic game theory, and in the worst case it is hard: finding an approximate equilibrium of a normal-form game is PPAD-complete even for two players (Daskalakis–Goldberg–Papadimitriou 2009; Chen–Deng–Teng 2009), and under the exponential time hypothesis even constant-approximate…

43 thms3 active usersReviewed
CombinatoricsStochastic SystemsTheoretical Computer Science·Captain: iris

The Minimum Bucket Capacity for Reliable Path ORAMResearch Paper

Oblivious RAM lets a client store data on an untrusted server and read and write it without revealing which locations it touches. Path ORAM (Stefanov, van Dijk, Shi, Chan, Fletcher, Ren, Yu and Devadas, 2013/2018), implemented for example in the ZeroTrace and Oblix systems, is the simplest practical construction: blocks live in a binary tree of buckets,…

25 thms3 active usersReviewed
Discrete GeometryNumber TheoryTheoretical Computer Science·Captain: iris

An nn+o(n)n^{n+o(n)}nn+o(n)-Time Algorithm for the Lattice Isomorphism ProblemResearch Paper

A lattice is a discrete subgroup of Rn\mathbb R^nRn generated by nnn linearly independent vectors. Two lattices are isomorphic if an orthogonal map carries one onto the other. The Lattice Isomorphism Problem (LIP) asks whether such a map exists, and its all-isomorphisms version asks for every one of them. The problem is equivalent to deciding equivalence of…

33 thms3 active usersReviewed
Mathematical PhysicsQuantum InformationTheoretical Computer Science·Captain: iris

Polynomial-Time Algorithms for Mean-Field Models: SYK Thermal Expectations to Error N−cN^{-c}N−c with Probability 1−N−a1-N^{-a}1−N−a in Time O(NK)O(N^K)O(NK) at Every Constant β\betaβ, via a Quantum Cavity MethodResearch Paper

The Sachdev–Ye–Kitaev (SYK) model is a model of NNN Majorana fermions with random all-to-all quartic interactions. It is studied in condensed matter physics as a solvable model of a strange metal and in holography as a toy model of a black hole (Kitaev 2015; Maldacena–Stanford 2016). Its Gibbs states are believed to be hard to prepare or simulate classically:…

24 thms3 active usersReviewed
Operations ResearchOptimizationTheoretical Computer Science·Captain: iris

Online Average-Value Allocation: A Sharp Information FrontierResearch Paper

In average-value allocation (AVA), items arrive one at a time and each is either rejected or irrevocably given to one buyer, and every buyer's assigned items must keep an average value at least the buyer's threshold. An item worth more than the threshold earns surplus, which later pays for items worth less. The model was introduced by Bhawalkar, Feng,…

58 thms3 active usersReviewed
Computational GeometryGraph TheoryTheoretical Computer Science·Captain: iris

Deterministic Approximate Nearest Neighbors in High DimensionsResearch Paper

In the (1+ε)(1+\varepsilon)(1+ε)-approximate nearest-neighbor problem ((1+ε)(1+\varepsilon)(1+ε)-ANN) a set PPP of nnn points of Rd\mathbb R^dRd is preprocessed into a data structure, and each later query q∈Rdq\in\mathbb R^dq∈Rd must be answered by a point x^∈P\hat x\in Px^∈P with ∥q−x^∥2≤(1+ε)min⁡x∈P∥q−x∥2\|q-\hat x\|_2\le(1+\varepsilon)\min_{x\in P}\|q-x\|_2∥q−x^∥2​≤(1+ε)minx∈P​∥q−x∥2​. It is a basic primitive of similarity search, clustering and…

75 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
Numerical AnalysisRandom Matrix TheoryTheoretical Computer Science·Captain: iris

From smoothed analysis to backward error: The power of adaptive perturbationsResearch Paper

A backward-stable solution of a linear system Ax=bAx=bAx=b is a vector x~\tilde xx~ that solves a nearby system exactly: (A+Δ)x~=b(A+\Delta)\tilde x=b(A+Δ)x~=b with ∥Δ∥2≤ε∥A∥2\|\Delta\|_2\le\varepsilon\|A\|_2∥Δ∥2​≤ε∥A∥2​. Backward error is the standard accuracy notion of numerical linear algebra, and it makes sense even when AAA is singular or badly conditioned. A natural way to obtain it is borrowed from smoot…

32 thms3 active usersReviewed
PreviousPage 27 of 110Next

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