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
🏆Completed
Machine LearningStatistics·Captain: mikedeng1

The Statistical Complexity of Interactive Decision Making I: Subadditivity of Squared Hellinger Distance for Sequential Laws, D²_H(P,Q) ≤ 10² log(n)·E_P[Σᵢ D²_H(P⁽ⁱ⁾, Q⁽ⁱ⁾)] for n ≥ 2Research Paper

Lower bounds for interactive decision making (bandits, reinforcement learning, and the general decision making with structured observations framework of Foster, Kakade, Qian and Rakhlin, arXiv:2112.13487) compare what a learner observes under two different environments. A learner's whole interaction history is generated one step at a time: each observation…

23 thms4 active users
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Information-Theoretic Analysis of Generalization Capability of Learning Algorithms I: The Expected Generalization Error Is at Most √(2σ²I(S;W)/n) (Theorem 1)Research Paper

A learning algorithm trained on a finite sample generalizes when its empirical risk on that sample is close to its risk on fresh data. Classical guarantees come from uniform convergence over the hypothesis class (VC dimension, Rademacher complexity) or from algorithmic stability, such as uniform stability (Bousquet and Elisseeff, 2002) and on-average…

7 thms4 active usersReviewed
🏆Completed
Operations ResearchProbabilityStatistics·Captain: mikedeng1

Bootstrap Robust Prescriptive Analytics 3: Any Distance Exceeding the Bootstrap Distance Near Some D Loses the Disappointment Rate −rResearch Paper

Data-driven decision making estimates the cost of a decision from training data and then optimizes that estimate. The optimized estimate is biased downwards: the decision that looks best on the training data tends to disappoint on fresh data. Distributionally robust optimization counters this by optimizing the worst case of the estimate over all…

9 thms4 active usersReviewed
🏆Completed
Probability·Captain: wurtle

Sharp binary-information contraction on the discrete cubeResearch Paper

Draw nnn independent fair bits XXX, compute a one-bit summary f(X)f(X)f(X), and send the bits through independent binary symmetric channels with crossover probability ε\varepsilonε, producing YYY. Which summary tells the receiver the most about YYY? Kumar and Courtade conjectured that a single coordinate, f(X)=X1f(X)=X_1f(X)=X1​, is optimal: I(f(X);Y)≤1−h2(ε)I(f(X);Y)\le 1-h_2(\varepsilon)I(f(X);Y)≤1−h2​(ε) bits for every…

111 thms4 active usersReviewed
🏆Completed
AlgebraTheoretical Computer Science·Captain: mikedeng1

Fuzzy Extractors: How to Generate Strong Keys from Biometrics and Other Noisy Data 3: Shingling plus PinSketch Gives an Average-Case Secure Sketch for Edit DistanceResearch Paper

Biometric readings, physical unclonable functions and typed passphrases share two defects as cryptographic keys: they are not uniformly distributed, and they are never reproduced exactly. Dodis, Ostrovsky, Reyzin and Smith (SIAM J. Comput. 38(1), 2008; preprint arXiv:cs/0602007v4) introduced the secure sketch to handle the second defect without destroying…

13 thms4 active usersReviewed
🏆Completed
OptimizationProbabilityStatistics·Captain: mikedeng1

I-Divergence Geometry of Probability Distributions and Minimization Problems 1: Cyclic I-Projections onto Linear Sets of a Finite Space Converge to the I-Projection onto Their IntersectionResearch Paper

Fitting a probability distribution to prescribed margins or moments is a basic task in statistics and information theory. Starting from a reference distribution, one can enforce one constraint at a time by choosing the closest distribution in I-divergence, then cycle through the constraints. In a contingency table this procedure is iterative proportional…

14 thms4 active usersReviewed
🏆Completed
Operations ResearchOptimizationProbability·Captain: mikedeng1

Worst-Case Value-At-Risk and Robust Portfolio Optimization: A Conic Programming Approach 2: Closed Form of the Entropy-Constrained Worst-Case VaRResearch Paper

Value-at-Risk (VaR) is the loss level that a portfolio exceeds with probability at most ε\varepsilonε. It is the standard risk measure of banking regulation, and its classical computation assumes Gaussian returns: for a Gaussian return vector with mean x^\hat xx^ and covariance Γ\GammaΓ it equals −Φ−1(ε)w⊤Γw−x^⊤w-\Phi^{-1}(\varepsilon)\sqrt{w^\top\Gamma w} - \hat x^\top w−Φ−1(ε)w⊤Γw​−x^⊤w, where …

9 thms4 active usersReviewed
🏆Completed
Captain: Elsie66

Shannon's Source Coding TheoremResearch Paper

How short can a code for a data source be, if the code must still be uniquely decodable — if every string of concatenated codewords can be unambiguously split back into the original symbols? Shannon's 1948 source coding theorem answers this exactly: the entropy of the source is a hard lower bound on the average codeword length of any uniquely decodable…

7 thms4 active usersReviewed
🏆Completed
Graph TheoryProbability·Captain: mikedeng1

Entropy-Weighted Soundness for Multi-Answer Birthday GraphsResearch Paper

A collection of small partial assignments can encode a complete satisfying assignment: retain every restriction of that assignment to a fixed number of coordinates. The converse question asks whether a comparably large collection of local assignments can be densely compatible when no global assignment satisfies most constraints. This question concerns the De…

34 thms3 active usersReviewed
🏆Completed
CombinatoricsTheoretical Computer Science·Captain: mikedeng1

Making Every Edit Count: Efficient Binary Edit Correction at the Gilbert–Varshamov BoundResearch Paper

An insertion or deletion changes the positions of later symbols. A receiver therefore faces uncertainty about alignment as well as about the values of damaged bits. Edit-correcting codes address this problem by restricting the transmitted words so that nearby received sequences identify a unique original message. File synchronization is one concrete…

33 thms3 active usersReviewed
🏆Completed
Combinatoricscryptography·Captain: mikedeng1

Expanding Codes with Polynomial StretchResearch Paper

A collection of sparse parity equations can involve almost as many variables as its total number of variable occurrences. This expansion property excludes small linear dependencies and is relevant to the complexity of recognizing noisy planted equations. It is therefore useful to distinguish what expansion guarantees from what it leaves possible. Hair and…

23 thms3 active usersReviewed
🏆Completed
Quantum Information·Captain: iris

From Classical to Quantum Shannon Theory XVII: The Entanglement Manipulation Limit Is H(A)ψ / H(A)φTextbook

Two parties, Alice and Bob, who share many copies of a pure entangled state ∣ψ⟩AB|\psi\rangle_{AB}∣ψ⟩AB​ and may act only by local operations and classical communication (LOCC) can transform their resource into many copies of another pure state ∣φ⟩AB|\varphi\rangle_{AB}∣φ⟩AB​. The question of how efficiently this can be done is the question of whether pure-state entanglement can…

26 thms3 active usersReviewed
🏆Completed
cryptography·Captain: iris

Strong Converse for a Degraded Wiretap Channel via Active Hypothesis Testing: with public feedback, the (ε, δ)-wiretap capacity is at most max over P_X of I(X ∧ Y | Z) whenever ε + δ < 1Research Paper

A wiretap channel W:X→Y×ZW:\mathcal X\to\mathcal Y\times\mathcal ZW:X→Y×Z models secure transmission over a noisy medium: a transmitter sends a symbol xxx, a legitimate receiver observes YYY and an eavesdropper observes a correlated ZZZ, with joint probability W(y,z∣x)W(y,z|x)W(y,z∣x). The transmitter wants to deliver a message MMM reliably to the receiver while revealing (almost) nothing about…

33 thms3 active usersReviewed
🏆Completed
cryptographyTheoretical Computer Science·Captain: Victorized

How to Share a Secret — Shamir’s Threshold SchemeResearch Paper

A cryptographic key can become unavailable when a single custodian loses it, while distributing complete copies gives every custodian the ability to use it alone. A threshold scheme distributes evaluations of one hidden object so that a sufficiently large coalition can recover a secret and a smaller coalition learns no information from its observations. Adi…

13 thms3 active usersReviewed
🏆Completed
Algorithmic Game TheoryOperations ResearchProbability·Captain: mikedeng1

Simulation of a Random Variable and its Application to Game Theory: With a Leaked Randomness Source, Alice Can Secure J_cav(H(X|Y)) in the n-Stage Repeated Game up to the Error Term (10)Research Paper

A mixed strategy assumes a player can draw from any distribution. A real player may only have a limited or imperfect source of randomness, and an opponent may observe part of it. Repeated games with bounded randomness ask how much a player can guarantee in that situation. Gossner and Vieille (2002, Games Econ. Behav. 41(2), 206–226) studied a repeated…

16 thms3 active usersReviewed
🏆Completed
EconomicsOperations Research·Captain: mikedeng1

Human and Machine: The Impact of Machine Input on Decision-Making Under Cognitive Limitations II: Machine Input Never Lowers the Decision-Maker's Accuracy or Expected ValueResearch Paper

Machine-learning systems are increasingly placed beside human experts — physicians reading scans, loan officers screening applications, judges assessing risk — rather than replacing them. The machine processes the structured data it can see; the human also has access to information the algorithm cannot observe, but her attention is limited. Whether such a…

11 thms3 active usersReviewed
🏆Completed
EconomicsOperations ResearchOptimization·Captain: mikedeng1

Human and Machine: The Impact of Machine Input on Decision-Making Under Cognitive Limitations I: The Rationally Inattentive Decision-Maker's Optimal Choice Probability in Closed FormResearch Paper

A person using a machine's advice may decide more accurately, but attention is costly. Before asking what a machine changes, the baseline decision has to be understood: how often would the person choose the action associated with a good state without machine input? Boyacı, Canyakmaz, and de Véricourt study this question in a model of a decision maker who…

7 thms3 active usersReviewed
🏆Completed
Linear algebraQuantum Error CorrectionQuantum Information·Captain: mikedeng1

Reversing quantum dynamics with near-optimal quantum and classical fidelity I: The Reversal Operation Attains at Least the Square of the Optimal Average Entanglement FidelityResearch Paper

Quantum error correction and quantum communication both ask the same question: after a known noise process A\mathcal AA has acted on a quantum system, how well can its effect be undone? For a given noise model the best recovery is the solution of a semidefinite program, which gives a number but no structure and no formula. Barnum and Knill showed in 2000 that…

7 thms3 active usersReviewed
🏆Completed
Combinatorics·Captain: chaikon

Essential Coding Theory I: Generalized Hamming BoundTextbook

An error-correcting code stores or transmits messages as words over a finite alphabet, adding redundancy so that the original word can be recovered after some symbols are corrupted. The basic question of coding theory is the trade-off between the amount of redundancy and the number of errors that can be corrected. The Hamming bound (also called the sphere-pa…

2 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningOperations Research·Captain: mikedeng1

Regret in Online Combinatorial Optimization II: Under Bandit Feedback Every Strategy Has Minimax Regret at Least 0.02 m√(dn) on Some Set of Actions with m OnesResearch Paper

An online player repeatedly chooses a subset of coordinates and pays the sum of their losses. In many applications the player sees only that sum, not the losses of the selected coordinates. This bandit feedback makes it harder to identify which coordinate within each chosen subset is responsible for a favorable or unfavorable outcome. Audibert, Bubeck and…

13 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsOperations ResearchProbability·Captain: mikedeng1

Data-Based Dynamic Pricing and Inventory Control with Censored Demand and Limited Price Changes 2: Any Policy with at Most m Price Changes Has Regret at Least KT^(1/(m+1)) on a Bernoulli InstanceResearch Paper

A seller learning a demand curve normally adjusts prices as new observations arrive. A price-change limit prevents that continual adjustment: a price may have to be chosen before the seller knows which demand curve it faces, then held through a block of sales. This matters when repricing is operationally costly, constrained by contracts, or visible to…

10 thms3 active usersReviewed
🏆Completed
Machine LearningOptimal TransportOptimization·Captain: mikedeng1

Computational Optimal Transport IX: The Entropic Cost L^ε_C(a, b) Equals max ⟨f, a⟩ + ⟨g, b⟩ − ε⟨e^{f/ε}, K e^{g/ε}⟩, with Optimal Scalings (e^{f/ε}, e^{g/ε})Textbook

Optimal transport compares two distributions by finding the least expensive way to move mass between them. For finite histograms, the resulting linear program is precise but its optimal coupling can be sparse. In applications where the coupling represents traffic, matching, or a differentiable loss, a sparse plan may be undesirable or expensive to compute…

9 thms3 active users
🏆Completed
Machine LearningOptimal TransportOptimization·Captain: mikedeng1

Computational Optimal Transport VII: The Entropic Optimal Coupling P_ε Tends to the Maximum-Entropy Optimal Plan as ε → 0 and to a ⊗ b as ε → ∞Textbook

The discrete optimal transport problem of Kantorovich asks for the cheapest way to move a probability histogram a\mathbf aa onto a histogram b\mathbf bb when moving a unit of mass from iii to jjj costs Ci,j\mathbf C_{i,j}Ci,j​. Its optimal couplings are vertices of a polytope and are typically sparse: they rely on a few routes. Two communities have reasons to blur them. In…

7 thms3 active usersReviewed
🏆Completed
Machine LearningProbabilityStatistics·Captain: mikedeng1

Information-Theoretic Analysis of Generalization Capability of Learning Algorithms III: The Gibbs Algorithm Has Excess Risk at Most (1/β)log(1/Q(wₒ)) + β/(2n) (Corollary 2)Research Paper

Statistical learning algorithms fit hypotheses to data that are available during training, while their performance is judged on new data. A rule that minimizes training loss can fit peculiarities of the sample, so its training loss and population loss need not agree. Xu and Raginsky study this difference through information quantities associated with the…

10 thms3 active usersReviewed
🏆Completed
Bandit AlgorithmsMachine LearningProbability·Captain: mikedeng1

A Tutorial on Thompson Sampling I: Any Algorithm Whose Information Ratio Is at Most Γ̄ Has Expected Regret at Most √(Γ̄·H(x*)·T)Research Paper

Thompson sampling (TS) chooses each action with the posterior probability that it is optimal. Its practical success in online advertising, recommendation and experimentation raised the question of why it works and when it does not. The tutorial of Russo, Van Roy, Kazerouni, Osband and Wen (Found. Trends Mach. Learn. 11(1), 2018) answers part of that…

9 thms3 active users
PreviousPage 2 of 4Next

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