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
Complexity TheoryTheoretical Computer Science·Captain: iris

XOR Functions and Beyond in the Random Query ModelResearch Paper

In the random query model an algorithm cannot choose which input bit to read. At each of TTT time steps it receives a pair (i,x(i))(i, x(i))(i,x(i)) with iii drawn uniformly at random, and between steps it keeps only SSS bits of memory. The model, introduced by Raz and Zhan (ITCS 2020), describes streaming access to unordered data and learning from random examples, and it asks a…

33 thms2 active usersReviewed
CombinatoricsProbabilityTheoretical Computer Science·Captain: iris

Secret Sharing Despite Non-Extractable RandomnessResearch Paper

Information-theoretic cryptography is usually analysed with perfectly uniform randomness, while physical sources are imperfect and only known to belong to some source class, a fixed family of distributions. If a single deterministic extractor maps every source of the class to a nearly uniform string, every task that needs uniform randomness becomes…

18 thms2 active usersReviewed
Algebraic GeometryComplexity Theory·Captain: iris

On Proximity Gaps for One-Point Algebraic Geometric CodesResearch Paper

Succinct proof systems of the FRI, STIR and WHIR family test whether a committed word lies close to a code. To test many words at once, they combine them with a random challenge: words u0,…,uℓu_0,\dots,u_\ellu0​,…,uℓ​ are replaced by the single word r(z)=∑j=0ℓujzjr(z)=\sum_{j=0}^{\ell}u_jz^jr(z)=∑j=0ℓ​uj​zj for a random zzz. Correlated agreement (CA) is the property that makes this batching sound. If…

36 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: iris

On the most informative Boolean function under noiseResearch Paper

A uniformly random string X∈{0,1}nX\in\{0,1\}^nX∈{0,1}n is sent through a binary symmetric channel: each coordinate is flipped independently with probability ppp, producing YYY. A single bit CCC is then computed from YYY. How much can one bit of the noisy output reveal about the input? Courtade and Kumar asked this in 2013 and conjectured that a dictator bit C=Y1C=Y_1C=Y1​ is optimal:

24 thms2 active usersReviewed
Machine LearningTheoretical Computer Science·Captain: iris

Should We Combine Our Data? Algorithms and Limits for Privately Assessing Data SharingResearch Paper

Two organizations that each hold a labelled dataset often want to know, before any costly data-sharing agreement, whether their data are compatible: whether one classifier from a fixed class fits both datasets at once. Answering this question by exchanging the data defeats its purpose, since the records are private. Haghifam, Patel, Blum, Fanti and Ziani (ar…

30 thms2 active usersReviewed
CombinatoricsComplexity TheoryTheoretical Computer Science·Captain: iris

Low-Error ExtractorsResearch Paper

A randomness extractor turns a weak random source into nearly uniform bits. Since no deterministic function extracts from a single weak source, the two-source extractor takes two independent sources: a deterministic function 2Ext:{0,1}n×{0,1}n→{0,1}m\mathrm{2Ext}:\{0,1\}^n\times\{0,1\}^n\to\{0,1\}^m2Ext:{0,1}n×{0,1}n→{0,1}m such that, whenever X,Y\mathbf X,\mathbf YX,Y are independent with min-entropy at least kkk,…

45 thms2 active usersReviewed
Complexity TheoryTheoretical Computer Science·Captain: iris

Zero-Knowledge PCPs of Quasilinear Size via Locally Simulatable Sheaf CodesResearch Paper

A probabilistically checkable proof (PCP) is a proof that a verifier can check by reading a few randomly chosen locations. The PCP theorem of Arora and Safra and Arora, Lund, Motwani, Sudan and Szegedy gives such proofs for NP with a constant number of queries, and is a central result of complexity theory, with consequences for hardness of approximation and…

34 thms2 active usersReviewed
ProbabilityQuantum InformationTheoretical Computer Science·Captain: iris

Regev's Reduction Reaches ReconstructionResearch Paper

Sampling from the Gibbs distribution of a spin glass at low temperature is a central primitive of statistical physics and optimization. For sparse random constraint systems, the question of which temperatures are reachable in polynomial time is usually tied to the dynamical glass transition, which Mézard and Montanari identified with a reconstruction…

34 thms2 active usersReviewed
ProbabilityTheoretical Computer Science·Captain: iris

Optimal Communication for Distributed Sparse Histogram AggregationResearch Paper

Histogram estimation asks how often each item of a large universe occurs in a collection of data; it underlies stream summaries, frequent-item identification and counting queries. When the data are spread over many users, a server learns the frequencies from short messages, and the question is how many bits an accurate aggregate requires. A typical regime…

45 thms2 active usersReviewed
ProbabilityStatistics·Captain: iris

Beyond least-favorable distribution pairs: asymptotically instance-optimal robust hypothesis testingResearch Paper

A sequential test observes data one at a time and may stop and reject the null hypothesis at any moment, while keeping the probability of a false rejection below a prescribed level α\alphaα no matter how the data are monitored. Modern constructions of such tests are e-processes: nonnegative wealth processes that start at one and cannot grow in expectation…

24 thms2 active usersReviewed
CombinatoricsTheoretical Computer Science·Captain: iris

Marton's conjecture in polynomial timeResearch Paper

A finite set A⊆F2nA\subseteq\mathbb F_2^nA⊆F2n​ has doubling constant KKK when ∣A+A∣≤K∣A∣|A+A|\le K|A|∣A+A∣≤K∣A∣. Marton's conjecture, also called the polynomial Freiman–Ruzsa (PFR) conjecture, asserts that such a set is essentially a subspace up to polynomial losses: there is a subspace VVV with ∣V∣≤∣A∣|V|\le|A|∣V∣≤∣A∣ such that AAA is covered by KO(1)K^{O(1)}KO(1) translates of VVV. It was proved by Gowers, Green,…

27 thms2 active usersReviewed
Harmonic AnalysisProbabilityTheoretical Computer Science·Captain: iris

Quasipolynomial Trace ReconstructionResearch Paper

A deletion channel with retention probability ppp takes a binary string x∈{0,1}nx\in\{0,1\}^nx∈{0,1}n, keeps each bit independently with probability ppp, and outputs the kept bits in order; the output is a trace. The trace reconstruction problem asks how many independent traces are needed to recover an unknown xxx with probability at least 2/32/32/3. It is a basic question about…

26 thms2 active usersReviewed
Complexity TheoryConvex Optimization·Captain: iris

Exponential memory/query-complexity tradeoffs in high-accuracy feasibility problemsResearch Paper

Cutting-plane methods solve convex feasibility problems with an optimal number of separation-oracle queries, but they store a description of the current localization set, about d2log⁡(1/ϵ)d^2\log(1/\epsilon)d2log(1/ϵ) bits. Gradient-type methods need only O(dlog⁡(1/ϵ))O(d\log(1/\epsilon))O(dlog(1/ϵ)) bits but converge polynomially. Whether low memory forces a large query cost is a question about the…

79 thms2 active usersReviewed
cryptographyQuantum Information·Captain: iris

Universally composable privacy amplification against quantum adversaries: two-universal hashing yields a key within 122−(S2−S0−s)/2\frac12 2^{-(S_2-S_0-s)/2}21​2−(S2​−S0​−s)/2 of idealResearch Paper

Two parties who share a partially secret string ZZZ can turn it into a short, highly secret key by privacy amplification: one of them publicly picks a hash function FFF and both compute S=F(Z)S=F(Z)S=F(Z) (Bennett, Brassard, Robert 1988). The step ends almost every quantum key distribution protocol, so the security of those protocols rests on what an adversary who holds a…

30 thms2 active usersReviewed
cryptographyQuantum Information·Captain: iris

Quantum Key Distribution and String Oblivious Transfer in Noisy Channels: Security of String-QOT Against Bob, I(B;V∣Pass=1,C=1)⋅Pr⁡(Pass=1)≤2−ξnI(B;V\mid Pass=1,C=1)\cdot\Pr(Pass=1)\le 2^{-\xi n}I(B;V∣Pass=1,C=1)⋅Pr(Pass=1)≤2−ξnResearch Paper

Quantum key distribution lets two parties who share no secret agree on one over a public quantum channel, with security resting on physics and not on a computational assumption. The BB84 scheme of Bennett and Brassard is the standard protocol, and the question that drove the field through the 1990s was whether it stays secure when the eavesdropper applies…

26 thms2 active usersReviewed
Functional AnalysisQuantum Information·Captain: iris

Rényi relative entropies and noncommutative LpL_pLp​-spaces: The Sandwiched Rényi Data Processing Inequality for Positive Trace-Preserving Maps on von Neumann Algebras, With Bounds on the Entropy DropResearch Paper

Rényi relative entropies Dα(ρ∥σ)D_\alpha(\rho\|\sigma)Dα​(ρ∥σ) are one-parameter deformations of the Umegaki relative entropy. In quantum information theory they give the strong converse exponents of hypothesis testing and of channel coding, and the sandwiched Rényi relative entropy

24 thms2 active usersReviewed
Quantum Information·Captain: iris

From Classical to Quantum Shannon Theory XVIII: The Holevo–Schumacher–Westmoreland Theorem: C(N) = χreg(N)Textbook

Shannon's noisy channel coding theorem identifies the largest rate at which classical messages can be sent reliably over a classical channel. When the channel is a quantum system, for example photons sent through an optical fibre, the sender may prepare arbitrary quantum states, entangled across many uses of the channel, and the receiver may perform…

30 thms2 active usersReviewed
ProbabilityQuantum Information·Captain: iris

From Classical to Quantum Shannon Theory XV: The Covering LemmaTextbook

Many protocols in quantum Shannon theory must make a message invisible to an eavesdropper rather than readable by a receiver. A sender who wants Eve's system to carry no information about a secret bit randomizes over a small set of codewords so that, whichever bit was sent, Eve receives (approximately) the same average state. The covering lemma quantifies…

14 thms2 active usersReviewed
Quantum Information·Captain: iris

From Classical to Quantum Shannon Theory VII: The Uncertainty Principle with Quantum Memory: H(X∣B)+H(Z∣B)≥log⁡(1/c)+H(A∣B)H(X|B) + H(Z|B) \ge \log(1/c) + H(A|B)H(X∣B)+H(Z∣B)≥log(1/c)+H(A∣B)Textbook

The Heisenberg–Robertson uncertainty relation bounds a product of standard deviations by a quantity that depends on the state, and it can vanish even when both measurement outcomes are uncertain. Entropic uncertainty relations replace standard deviations by Shannon entropies of the outcome distributions and give a state-independent bound. Deutsch proved the…

30 thms2 active usersReviewed
Mathematical PhysicsQuantum Information·Captain: iris

Unconditional optimality of Gaussian attacks against continuous-variable QKD: the Gaussian state with the same covariance matrix minimizes the collective-attack secret key rate K(ρAB)K(\rho_{AB})K(ρAB​)Research Paper

Continuous-variable quantum key distribution (CV-QKD) lets two parties, Alice and Bob, establish a secret key by sending Gaussian-modulated coherent or squeezed states of light and detecting them with homodyne or heterodyne receivers (Grosshans–Grangier 2002; Grosshans et al. 2003). The protocols use standard telecom components, so the security question has…

18 thms2 active usersReviewed
Quantum Information·Captain: iris

Equivalence of Additivity Questions in Quantum Information Theory: additivity of minimum output entropy, Holevo capacity and entanglement of formation and strong superadditivity of EF are equivalentResearch Paper

A quantum channel can be used many times, and the inputs to different uses may be entangled. Whether entangled inputs ever help to send classical information was, around 2000, one of the central open questions of quantum Shannon theory. The single-use answer is the Holevo capacity χN\chi_NχN​: by the Holevo–Schumacher–Westmoreland theorem the classical capacity…

32 thms2 active usersReviewed
Bandit AlgorithmsMachine Learning·Captain: iris

Satisficing in Time-Sensitive Bandit Learning: Every Policy's Discounted Satisficing Regret Is at Most Γ(A~,ψ) I(A~;θ)/(1−α2)\sqrt{\Gamma(\tilde A,\psi)\,I(\tilde A;\theta)/(1-\alpha^2)}Γ(A~,ψ)I(A~;θ)/(1−α2)​Research Paper

Bayesian bandit algorithms such as Thompson sampling are analyzed through the information ratio: the squared expected shortfall of a period divided by the information the period's observation reveals about the optimal action A∗A^*A∗ (Russo & Van Roy 2016). That analysis bounds regret by Γ H(A∗) T\sqrt{\Gamma\, H(A^*)\, T}ΓH(A∗)T​, where H(A∗)H(A^*)H(A∗) is the entropy of the optimal…

18 thms2 active usersReviewed
Quantum Information·Captain: iris

Distinguishability and Accessible Information in Quantum Theory VII: the quantum fidelity is the minimal statistical overlap over all measurementsTextbook

Two quantum states cannot in general be told apart perfectly, and how well they can be told apart depends on the measurement. Classically, the statistical overlap (Bhattacharyya coefficient) ∑bp0(b)p1(b)\sum_b\sqrt{p_0(b)p_1(b)}∑b​p0​(b)p1​(b)​ of two probability distributions controls how quickly repeated samples separate them. The quantum question is which measurement makes the…

14 thms2 active usersReviewed
Quantum Information·Captain: iris

Distinguishability and Accessible Information in Quantum Theory IV: Daróczy's derivation of the Shannon entropyTextbook

The Shannon information function H(p)=−∑ipiln⁡piH(p) = -\sum_i p_i \ln p_iH(p)=−∑i​pi​lnpi​ measures the average information gained when one samples a discrete probability distribution ppp. Its use as a measure of distinguishability (the mutual information of Chapter 2 of C. A. Fuchs's thesis, arXiv:quant-ph/9601020) is only as convincing as the reasons for the formula itself. Section 2.4.1…

10 thms2 active usersReviewed
Quantum Information·Captain: mikedeng1

General Benchmarks for Quantum Repeaters: For the Qudit Dephasing Channel the Entanglement-Flux Upper Bound Meets the Coherent Information, log₂ d − H(P)Research Paper

A quantum repeater is judged by how much it beats direct transmission over a point-to-point link. The natural yardsticks are the two-way assisted capacities of the link's channel E\mathcal EE: the quantum capacity Q2(E)Q_2(\mathcal E)Q2​(E) and the secret-key capacity K(E)K(\mathcal E)K(E), the best rates of entanglement and key that two parties can obtain over many uses of …

15 thms2 active usersReviewed
PreviousPage 6 of 8Next

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