Questions tagged [it.information-theory]
Questions in Information Theory
60
questions with no upvoted or accepted answers
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 ...
- 11k
15
votes
0
answers
250
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 ...
- 5,290
15
votes
0
answers
284
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 ...
- 5,290
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 ...
- 13.5k
9
votes
0
answers
159
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 ...
- 209
8
votes
0
answers
893
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 ...
- 2,208
8
votes
0
answers
352
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, ...
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 ...
- 20.8k
7
votes
0
answers
199
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 ...
- 12.6k
6
votes
0
answers
38
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 ...
- 329
6
votes
0
answers
232
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?
...
- 12.6k
5
votes
0
answers
89
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....
- 314
5
votes
0
answers
135
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 ...
- 425
4
votes
0
answers
232
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 ...
- 99
4
votes
0
answers
96
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, ...
- 291
4
votes
0
answers
112
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 $...
- 223
4
votes
0
answers
107
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 ...
- 331
4
votes
0
answers
119
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 ...
- 425
4
votes
0
answers
134
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 ...
- 12.6k
4
votes
0
answers
108
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 ...
- 3,718
4
votes
1
answer
243
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 ...
- 1,318
3
votes
0
answers
20
views
Modelling channels without specifying input alphabets
The standard mathematical model of a communication channel is that of a stochastic matrix $(C(x|a))_{a \in A, x \in X}$, where $A$ is the input alphabet and $X$ the output alphabet.
This definition ...
- 131
3
votes
0
answers
97
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}^...
- 11.3k
3
votes
0
answers
129
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 ...
- 2,281
3
votes
0
answers
77
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_{...
- 425
2
votes
0
answers
70
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$ ...
- 21
2
votes
0
answers
86
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 ...
- 610
2
votes
0
answers
145
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 ...
- 21
2
votes
0
answers
107
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 ...
- 121
2
votes
0
answers
63
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 ...
- 245
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}$...
- 425
2
votes
0
answers
67
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....
- 2,351
1
vote
0
answers
81
views
Generalizing Fano's inequality
Fano's inequality says the following:
Theorem: Let $X$ be a random variable with range $M$. Let $\hat{X} = g(Y)$ be the predicted value of $X$ given some transmitted value $Y$, where $g$ is a ...
- 11
1
vote
0
answers
53
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 ...
- 21
1
vote
0
answers
122
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 ...
- 11
1
vote
0
answers
83
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:\...
- 143
1
vote
0
answers
73
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 ...
- 181
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 ...
- 173
1
vote
0
answers
143
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 ...
- 243
1
vote
0
answers
139
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 ...
- 111
1
vote
0
answers
170
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 ...
- 425
1
vote
0
answers
201
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 ...
- 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 ...
- 12.6k
1
vote
0
answers
8
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:/...
- 12.6k
1
vote
0
answers
25
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 ...
- 12.6k
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 ...
- 171
1
vote
0
answers
610
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 ...
- 111
1
vote
0
answers
128
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 ...
- 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 ...
- 2,208
0
votes
0
answers
27
views
What are the two quantities involved in the tradeoff for a language to follow Zipf's law?
In any human (and non-human) language the frequency distribution of words follows Zipf's law, which states that the slope of the linear regression for the frequency distribution of words vs the rank ...
- 101