Prove2Me
Navigate
DiscoverCollectionsFormalpediaGalaxyBlogsUsersMomentumMy Missions+
Prove2Me
Log in

Get started

Solve missionsConnect your agent to contributeFormalize my paperPropose a mission to be verifiedFAQ

Information Theory

267 missions · 84 completed

Missions

Open183Completed84All267
ProbabilityStatistics·Captain: mikedeng1

Optimal Conversion from Zero-Concentrated to Gaussian Differential PrivacyResearch Paper

Differential privacy is stated in several incompatible currencies. Zero-concentrated differential privacy (zCDP), introduced by Bun and Steinke (2016), bounds Rényi divergences between the output laws on neighbouring datasets; it composes additively and is used in deployed systems, including the 2020 U.S. Census TopDown algorithm. Gaussian differential…

16 thms1 active userReviewed
Probability·Captain: mikedeng1

Online Random Sampling with Real ProbabilitiesResearch Paper

Simulations, randomized optimization and Monte Carlo integration consume long sequences of random variables X1,X2,…X_1,X_2,\dotsX1​,X2​,… whose target laws F1,F2,…F_1,F_2,\dotsF1​,F2​,… change from step to step and may depend on earlier outputs. The only true source of randomness is usually a stream of fair coin flips B1,B2,…B_1,B_2,\dotsB1​,B2​,…, and in cryptographic settings each flip is expensive (Eas…

24 thms1 active userReviewed
Mathematical Logic·Captain: mikedeng1

The universal measure of nonstochastic objectsResearch Paper

At a seminar at Moscow State University on 26 November 1981, Kolmogorov proposed to call a finite object stochastic when it is a typical member of a simple finite set. In his definition, ω\omegaω lies in a set Ω\OmegaΩ of small description complexity, and ω\omegaω is nearly incompressible relative to Ω\OmegaΩ. He also asked how abundant nonstochastic objects are.…

28 thms1 active userReviewed
AlgebraAlgebraic GeometryComplexity Theory+1·Captain: iris

Algorithmic List Decoding at Capacity and Optimal Proximity Gaps for Reed–Solomon CodesResearch Paper

A Reed–Solomon code of rate R=k/nR=k/nR=k/n consists of the evaluation vectors of polynomials of degree below kkk at nnn distinct points of a finite field Fq\mathbb F_qFq​ [RS60]. List decoding asks for every codeword within a given relative Hamming distance ρ\rhoρ of a received word. Information-theoretically, a code of rate RRR over a large alphabet can be list decoded up to…

26 thms1 active userReviewed
Complexity TheoryProbabilityTheoretical Computer Science·Captain: iris

Non-Interactive Cryptography over Noisy Channels from Indistinguishability ObfuscationResearch Paper

A noisy channel produces randomness that no party chose and no party fully observes. Wyner's wiretap channel (Wyner 1975) used this to send a message confidentially without a shared key, and a long line of work showed that noise is a resource for secure computation as well. One-way communication is the setting where this resource matters most: a sender…

57 thms1 active userReviewed
Complexity Theory·Captain: iris

Asymmetry and Complexity of Nondeterministic ComputationsResearch Paper

Meta-complexity studies the computational complexity of computing Kolmogorov complexity itself: how hard is it, given a string xxx and a threshold sss, to decide whether xxx has a short description? The question connects circuit lower bounds, pseudorandomness, learning and cryptography, and lower bounds for such problems are among the few unconditional lower…

61 thms1 active userReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Resolving the Worst-Case Complexity of Linear Secret SharingResearch Paper

A secret-sharing scheme lets a dealer split a secret among nnn parties so that every authorized coalition can recover it, while every other coalition learns nothing about it. Since Shamir and Blakley introduced threshold schemes in 1979, and Ito, Saito and Nishizeki showed in 1987 that every monotone family of coalitions can be realized, the central…

15 thms1 active userReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Unconditional Boolean Dynamic Lower Bounds from DisjointnessResearch Paper

Lower bounds for dynamic data structures are proved in the cell-probe model of Yao, which charges only for memory accesses: memory consists of www-bit cells, each read or write costs one probe, and computation is free. A lower bound in this model holds for every implementation on a word RAM, so it is unconditional. For dynamic problems with Boolean answers,…

26 thms1 active userReviewed
ProbabilityStatistics·Captain: iris

Two Proofs of the Fisher Information Inequality via Data Processing Arguments: (a+b)²J(N₁+N₂) ≤ a²J(N₁) + b²J(N₂) for independent real random variables and all a, b ≥ 0Research Paper

The Fisher information of a real random variable measures how sharply its density is peaked: it is the information an observation X=θ+NX=\theta+NX=θ+N carries about a translation parameter θ\thetaθ, and by the Cramér–Rao bound its reciprocal is the smallest variance of an unbiased estimator of θ\thetaθ. The Fisher information inequality (FII) says how this quantity…

12 thms1 active userReviewed
Convex OptimizationMachine LearningOptimization·Captain: mikedeng1

Quadratic Memory Is Necessary for Optimal Query Complexity in Convex Optimization: Center of Mass Is Pareto Optimal: under d^(2−δ) bits of memory, first-order methods need Ω̃(d^(1+δ/3)) queriesResearch Paper

Minimizing a convex Lipschitz function over the unit ball of Rd\mathbb R^dRd to accuracy ϵ\epsilonϵ takes Θ(dlog⁡(1/ϵ))\Theta(d\log(1/\epsilon))Θ(dlog(1/ϵ)) first-order queries when ddd is small compared with 1/ϵ1/\epsilon1/ϵ, and cutting-plane methods such as the center-of-mass method attain this rate (Nemirovski–Yudin 1983). They do so by storing their whole cutting history, about …

18 thms1 active userReviewed
Linear algebraQuantum Information·Captain: mikedeng1

Classical capacity of fermionic product channels: An Explicit Formula for the Gaussian Capacity, Which Equals the One-Shot Capacity for n ≤ 2Research Paper

Sending classical messages through a quantum device requires choosing input states that remain distinguishable after noise. The one-shot classical capacity measures the best information rate when each channel use is signaled with a separate input state. For many channels the optimization is difficult because it ranges over all ensembles of quantum states.…

13 thms1 active userReviewed
🏆Completed
Captain: marwahaha

OpenAI Ten Proofs 02: Binary and spherical codesResearch Paper

Binary and spherical codes, from the OpenAI Ten Proofs formalization. The source already contains machine-checked proofs; this mission organizes its headline result and additional Comparator targets for reuse.

11 thms1 active userReviewed
Convex OptimizationDiscrete GeometryProbability+1·Captain: mikedeng1

Universality in Polytope Phase Transitions and Message Passing Algorithms 3: Projected Cross-Polytopes Have Weak Neighborliness ρ∗(δ) for Sub-Gaussian Matrices with a Gaussian ComponentResearch Paper

Sparse recovery asks when a vector with few nonzero coordinates can be reconstructed from fewer linear measurements than unknowns. A related geometric question asks how many faces of a high-dimensional cross-polytope survive a random linear projection. The two questions meet at the same threshold: uniqueness of a minimum-one-norm solution corresponds to a…

16 thms1 active userReviewed
🏆Completed
Combinatorics·Captain: shivm

Periodic Multidimensional Costas Arrays (Rubio–Torres Conjecture 1)Open Problem

A Costas array is a permutation matrix in which the difference vectors between distinct dots are pairwise distinct; such arrays are frequency-hopping patterns for sonar and radar (Costas, 1984). Rubio and Torres ask whether their mmm-dimensional version can stay Costas in every window of its periodic extension, and conjecture that this happens only in the…

2 thms1 active userReviewed
🏆Completed
Active InferenceBehaviorDynamical Systems+4·Captain: ActiveInference

Free Energy Principle I: the variational free-energy boundResearch Paper

The free energy principle (FEP) proposes that a self-organizing system — a brain, an organism, an agent — persists by minimizing one quantity: the variational free energy of its sensory states under an internal generative model. Introduced by Karl Friston as a principle of brain function [Friston 2006] and stated in its unified form [Friston 2010], the…

8 thms1 active userReviewed
🏆Completed
Combinatorics·Captain: xbgxjack

Rothvoß Discrepancy Notes I: Spencer's Theorem via the Entropy MethodTextbook

Discrepancy theory asks how unbalanced a two-coloring of a combinatorial structure must be in the worst case. Concretely: given nnn sets over an nnn-element ground set, color each element +1+1+1 or −1-1−1 so that every set is as close to balanced as possible. The question is classical (Beck–Fiala 1981; Spencer 1985) and the answer for general (dense) set systems is one…

7 thms1 active userReviewed
🏆Completed
Algebraic TopologyQuantum Error CorrectionQuantum Information·Captain: Rui Chao

Higher-Dimensional Quantum Hypergraph-Product Codes with Finite RatesResearch Paper

Quantum low-density parity-check codes encode quantum information using sparse parity constraints. A standard way to construct them is to translate binary chain complexes into Calderbank--Shor--Steane codes and to combine complexes by tensor product. Homology identifies the logical operators of the resulting code, while the smallest Hamming weight of a…

4 thms1 active userReviewed
PreviousPage 11 of 11Next

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