Questions tagged [it.information-theory]

Questions in Information Theory

55 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
16 votes
0 answers
370 views

Looking for an operator on polynomials

I have a small, self-contained, math question, whose motivation is from theoretical computer science (specifically, list decoding of algebraic codes, derivative/multiplicity codes, etc). I wonder ...
user avatar
15 votes
0 answers
236 views

Fano's inequality in the high error regime

Fano's inequality says that given a random variable $X$, and a random variable $Y$ that "guesses" $X$ correctly with some probability, we can lower bound the information that $Y$ gives on $X$. More ...
user avatar
  • 5,190
15 votes
0 answers
279 views

Mutual information vs. Product sets

Suppose we have two dependent random variables $X$ and $Y$, each of which is uniform over $\{0,1\}^n$, such that their mutual information $I(X;Y)$ is small, say, at most $\sqrt{n}$. Does this imply ...
user avatar
  • 5,190
10 votes
0 answers
152 views

Threshold for non-zero quantum capacity of depolarizing channels

In "Quantum-channel capacity of very noisy channels", DiVincenzo, Shor and Smolin showed that it is possible to perform quantum communication over depolarizing channels provided that the fidelity was ...
user avatar
8 votes
0 answers
157 views

"Looking for help understanding a proof by Gossner (1998)."

Although there is no use of cryptographic protocols in Gossner (1998), the author refers to protocols of communication and he has a main result that I struggle to prove, because he does not use a ...
user avatar
  • 199
8 votes
0 answers
346 views

Approximation of Quantum Channels

Background: In quantum information theory, a wide class of processes acting on stochastic quantum states can be described using the formalism of Quantum Channels: A quantum channel is a linear, ...
user avatar
7 votes
0 answers
133 views

Information theoretic characterization and consequences of reductions between computational problems

For two computational problems $A$ and $B$ in complexity class C (let say $NP$), the existence of a reduction $A <_m^L B$ computable in class (say $L$) implies that $A$ is not computationally ...
user avatar
7 votes
0 answers
198 views

Geometric Intuition behind Locally testable codes

Conventional coding theory provides a good geometric picture behind linear error correction codes in terms of Hamming distance. What additional geometric requirement one should add to make a code ...
user avatar
  • 12.5k
7 votes
0 answers
875 views

Applications of Theoretical Computer Science in Information Theory

Inspired by this question: Information Theory used to prove neat combinatorial statements? Are there any nice applications of theoretical computer science in information theory (the other way has ...
user avatar
  • 2,198
6 votes
0 answers
37 views

Different definitions of optimal decompressors

Let $B^{<\omega}$ be the set of finite binary strings. I will only consider functions from $B^{<\omega}$ to $B^{<\omega}$. I recall the definition of the algorithmic complexity of a string ...
user avatar
  • 329
6 votes
0 answers
229 views

Physical Proof for P versus BPP

Lipton asks for a physical proof of $P\neq NP$. Can we even ask for a physical proof for understanding $P=BPP$ or $P\neq BPP$? Is there anything in physics that lets us avoid randomness? ...
user avatar
  • 12.5k
5 votes
0 answers
133 views

Largest size for randomness extractor

Suppose we have a source $X$ with min-entropy $\ell$. A randomness extractor is defined as a function $f$ which satisfies the total variation $||f(X, R)-U_M||_{TV}\leq \epsilon$ where $R$ is an ...
user avatar
  • 415
4 votes
0 answers
204 views

Maximize the mutual information between 2 discrete random variables

I have two random variables $X$ and $Y$. $X$ follows Poisson-Binomial distribution with parameters $\{q_1, \ldots, q_k\}$. Thus, $X$ can take values in the set $\{0,1,\ldots,k\}$. $Y$ is a binary ...
user avatar
4 votes
0 answers
89 views

Strong data-processing inequality: bound $TV(T_{\#}P_0,T_{\#}P_1)$ if $\|T(x)-x\|_\infty \le \varepsilon;\forall x \in \mathbb R^p$

Disclaimer. I've moved this question from MO hoping that here is the right venue. Also, this is my first post on this channel, so please have some patience. So, Iet $X = (X,d)$ be a Polish space, ...
user avatar
  • 217
4 votes
0 answers
107 views

Expected vs actual amount of information leaked by an $l$-bits message

Say we have a random variable $X$ that contains $k$ bits of information, and a message $M = f(X)$ ($M$ is deterministic given $X$) that is $l$ bits long, where $l<k$. This implies $H(X) = k$ and $...
user avatar
4 votes
0 answers
106 views

Why primitive rotation is $53.13^\circ$ in the quantum Turing machine used by Vitanyi for Quantum Kolmogrov Complexity?

Right now I am going through Quantum Kolmogorov Complexity Based on Classical Descriptions by Vitanyi. In the introduction, the author assumed the primitive rotation $\theta = 53.13^\circ$ to have ...
user avatar
4 votes
0 answers
73 views

What is the shortest description of a universal computational structure that includes a meta-circular evaluator?

I am wondering whether there is a minimal (or the shortest known) way of specifying a universal computational structure that includes a specification of a meta-circular evaluator within that structure....
user avatar
4 votes
0 answers
117 views

Inf-entropy rate and min-entropy

I am reading the paper "Generating random bits from an arbitrary source: fundamental limits" by Vembu and Verdu. This paper is written in the language of information theory, however, I need to ...
user avatar
  • 415
4 votes
0 answers
133 views

Lovasz Theta as a short certificate

Lovasz Theta Function provides short proof for the question, "is the Shannon Capacity of a graph($\Theta(G)$) greater than $r\in\Bbb R$?" if the answer is NO when $r$ is above a certain value (this ...
user avatar
  • 12.5k
4 votes
0 answers
107 views

Games where $\omega(G) < \omega^*(G) < \omega^{ns}(G) < 1$?

A two player game $G = (I,O,V,p)$ is such that, if two non-communicating players Alice and Bob are given questions $(x,y)\in I^2$ drawn from the probability distribution $p$, they are supposed to ...
user avatar
  • 3,708
4 votes
1 answer
236 views

Is "normalized distance" (as per Li & Vitanyi, Kolmogorov Complexity) a reasonable thing?

In "The Similarity Metric" (Li, Vitanyi, et. al) they define a normalized distance (or similarity distance) as a function $\Omega \times \Omega \to [0,1]$ which is both symmetric and satisfies the ...
user avatar
  • 1,318
3 votes
0 answers
86 views

Estimate smooth vector, from dot-product queries

I have a secret $n$-dimensional vector $\mathbb{s} \in \mathbb{Z}^n$. I don't know $\mathbb{s}$; my goal is to estimate $\mathbb{s}$. I do have an oracle for the function $f_\mathbb{s} : \mathbb{Z}^...
user avatar
  • 10.5k
3 votes
0 answers
126 views

What is the problem of finding a largest subset of smallest Kolmogorov complexity?

What do you call the problem of finding a largest possible subset of strings with smallest possible information content? I'm studying a particular instantiation of this problem in a different setting ...
user avatar
  • 2,271
3 votes
0 answers
76 views

One kind of dependence relation between a pair of random variables

I have been working on privacy and come across a neat problem. Suppose two random variables $X$ and $Y$, over finite alphabets $\mathcal{X}$ and $\mathcal{Y}$, are given with joint distribution $P_{...
user avatar
  • 415
2 votes
0 answers
62 views

Origin of Berge's (Weak) Perfect Graph Conjecture

In an account of his thought process (refer p. 3) leading up to the perfect graph conjecture (which I'm preparing a seminar talk on), C. Berge states what seems to be a crucial step: (1) a graph $G$ ...
user avatar
  • 21
2 votes
0 answers
81 views

Approximate (in hamming distance) subset representation

Let us have a set $S$ and a subset $T \subseteq S$. I want to find an approximate representation of $T$, i.e. I want to represent (exactly) a set $T'$ that is close to $T$. That is, I want the ...
user avatar
2 votes
0 answers
100 views

Damerau–Levenshtein distance with transposition of non-adjacent characters?

Wondering if it's possible to calculate Damerau–Levenshtein distance with transposition of non-adjacent characters (DL distance allows transposition of immediately adjacent characters only). I want ...
user avatar
  • 21
2 votes
0 answers
105 views

Representing data with Shannon entropy predicted bits

Let us assume a file based on a character set where each character has equal probability of occurance. This will result in the maximum entropy for that character set. On calculating the entropy, let ...
user avatar
  • 121
2 votes
0 answers
131 views

Strong Dependence

I asked this question on MO, but no answer. I don't know if this definition has been already given. Suppose $X$ and $Y$ are two random variables over finite alphabets $\mathcal{X}$ and $\mathcal{Y}$...
user avatar
  • 415
2 votes
0 answers
66 views

Boltzmann sampling software

I'm looking for an implementation of Boltzmann sampling for combinatorial structures. Recent paper in the area for context: http://hal.inria.fr/docs/00/74/77/09/PDF/NonRedundantGeneration-TCS-2010....
user avatar
1 vote
0 answers
52 views

sophistication or logical depth to detect intelligent extra-terrestrial species

From my understanding, Algorithmic information theory (AIT) gives some ways to define the amount of « structure » in a string: for example sophistication or logical depth (see for instance [1]), can ...
user avatar
1 vote
0 answers
113 views

Deterministic one way communication complexity for message with arbitrary length

Let Alice have a binary string of length $n$ that it wants to send to Bob along a one-bit communication channel. However, Bob does not know the length of the message. I have been looking into ...
user avatar
1 vote
0 answers
78 views

Difference between a lossy encoder and a noisy channel in Information Theory

$S \to X \to Y \to \hat{S}$ $\text{source} \to \text{input} \to \text{output} \to \text{target}$ In information theory introductory books, an encoder is usually defined as a deterministic function $f:\...
user avatar
  • 133
1 vote
0 answers
65 views

Is there a theoretical guarantee that an autoencoder $g$ has $I(x;g(x)) \approx H(x)$?

I know that in general, a function $g$ can be a good auto-encoder (i.e., $g(x) \approx x$ for $x \sim D$) and on the same time $I(g(x);x)$ is small. This is the case when $g$ forms a good correlation ...
user avatar
  • 181
1 vote
0 answers
55 views

Problem dependent lower bound for stochastic bandits with full information

Suppose you have a $K$ armed stochastic bandit problem but with full information. There are $K$ arms with mean rewards $\mu_1,...,\mu_K$. At each step we have to select an arm, collect the reward from ...
user avatar
1 vote
0 answers
65 views

Parametrically-relaxed Kolmogorov complexity

Consider the following problem: Input: An integer $n$ and a subset $S \subseteq \{0...n-1\}$ in some representation. Output: The encoding of some kind of automaton (say, a Turing machine) which ...
user avatar
  • 173
1 vote
0 answers
134 views

Connection between diamond norm and output purity norm

Setting of the problem: Given a quantum channel $\mathcal{E}: \mathcal{H}_A\rightarrow \mathcal{H}_B$ (where $\mathcal{H}$ refers to a Hilbert space and subscript refers to the quantum register ...
user avatar
1 vote
0 answers
136 views

Information theoretic lower-bound on object graph serialization

This might be a daft quesstion, but here comes. I became intriqued about data serialization formats and tried to look for research on what could be the information theoric lower bound on encoding ...
user avatar
  • 111
1 vote
0 answers
167 views

Maximal correlation vs correlation coefficient when one RV is Gaussian

Last week I asked a question on MOF (see here), but I got no reply. So I am asking my question here. Let a pair of random variables $(X,Y)$ be continuous random variables (i.e., they both have ...
user avatar
  • 415
1 vote
0 answers
191 views

Initialization of errata evaluator polynomial for simultaneous computation in Berlekamp-Massey for Reed-Solomon

This is a continuation of this post on SO. I am trying to implement an errata (errors-and-erasures) decoder for Reed-Solomon. My current approach is to use Berlekamp-Massey (because it's the most ...
user avatar
  • 131
1 vote
0 answers
19 views

can constant weight codes achieve channel capacity

Can a sequence of constant weight linear codes achieve channel capacity on Additive White Gaussian Noise channel? (by a sequence achieving capacity I mean a sequence of linear codes of increasing ...
user avatar
  • 12.5k
1 vote
0 answers
7 views

The relation between Shannon capacity and Witsenhausen rate of graphs

The Witsenhausen rate of a graph $G$ is given by $$R(G)=\lim_{m\rightarrow\infty}\chi(G^{\boxtimes m})^{\frac{1}{m}}$$ where $\boxtimes$ is the strong product (refer formula $1$ on page $2$ here http:/...
user avatar
  • 12.5k
1 vote
0 answers
22 views

Shannon capacity of Union

Alon showed that a counter example to the Shannon conjecture on the Zero-error capacity of disjoint union of graphs. The conjecture is that the sum of Zero-error capacities of the constituent graphs ...
user avatar
  • 12.5k
1 vote
0 answers
63 views

Finding Most Compressible Vector Within Bounds?

Given large positive integers $m$ and $n$: Let $S$ be the set of integers $\{1,2,\dots,m\}$ We are given as input two vectors $L$ and $U$ both over $S^n$ such that: $$\bigwedge_{i=1}^{n}{L_i \le ...
user avatar
1 vote
0 answers
603 views

Information channel with symmetric channel matrix

It took me a while to figure out that a "symmetric channel" does not mean a channel with a symmetric channel matrix. (Rather, "symmetric channel" means that the rows of the matrix are all permutations ...
user avatar
1 vote
0 answers
124 views

High Dimensional Volume (HDV) estimator for Entropy estimation

I am writing a program using high-dimensional volume (HDV) estimator to estimate entropy and mutual information for variable selection. Let $ D = (x^i_1, x^i_2, ..., x^i_M)$, N is the number of data ...
user avatar
  • 11
1 vote
0 answers
135 views

Information theory and Tsfasman-Manin's problem

Yuri Manin recently posted an interesting paper on computability of boundary regions of distance-rate trade-offs for error correction codes. http://arxiv.org/PS_cache/arxiv/pdf/1107/1107.4246v1.pdf I ...
user avatar
  • 2,198
0 votes
0 answers
24 views

Is there a name/terminology for binary codes with evenly spaced number of ones?

I am generating a random binary matrix $A \in \{0, 1\}^{m \times n}$ with the number of ones in each row set to evenly spaced numbers from an interval. For example, if $n=50$, the number of ones for $...
user avatar
0 votes
0 answers
56 views

Interesting statistical experiment concerning data compression

I want to present the following statistical experiment concerning data compression, on which I will ask you to predict the result obviously justifying the choice made. The statistical experiment is ...
user avatar
  • 1
0 votes
0 answers
165 views

Error in entropy properties in Mathematical Theory of Cryptography by Claude E. Shannon

I am reading this classic paper by Claude E. Shannon and I think there may be a couple of errors in his description of the properties of Entropy/Uncertainty. The screenshot shown at the bottom of this ...
user avatar