Skip to main content

Questions tagged [it.information-theory]

Questions in Information Theory

67 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
16 votes
0 answers
371 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 ...
Dana Moshkovitz's user avatar
15 votes
0 answers
258 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 ...
Or Meir's user avatar
  • 5,615
15 votes
0 answers
286 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 ...
Or Meir's user avatar
  • 5,615
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 ...
Joe Fitzsimons's user avatar
9 votes
0 answers
160 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 ...
Nav89's user avatar
  • 209
8 votes
0 answers
910 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 ...
v s's user avatar
  • 2,208
8 votes
0 answers
359 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, ...
Antonio Valerio Miceli-Barone's user avatar
7 votes
0 answers
135 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 ...
Mohammad Al-Turkistany's user avatar
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 ...
Turbo's user avatar
  • 13k
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 ...
Ted's user avatar
  • 329
6 votes
0 answers
233 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? ...
Turbo's user avatar
  • 13k
5 votes
0 answers
268 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 ...
wanderer's user avatar
  • 109
5 votes
0 answers
98 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....
Lenar Hoyt's user avatar
5 votes
0 answers
137 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 ...
SAmath's user avatar
  • 425
4 votes
0 answers
111 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, ...
dohmatob's user avatar
  • 291
4 votes
0 answers
114 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 $...
Dawei Huang's user avatar
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 ...
Omar Shehab's user avatar
4 votes
0 answers
123 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 ...
SAmath's user avatar
  • 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 ...
Turbo's user avatar
  • 13k
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 ...
Henry Yuen's user avatar
  • 3,798
4 votes
1 answer
249 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 ...
Jeremy Kun's user avatar
  • 1,318
3 votes
0 answers
24 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 ...
Tobias Fritz's user avatar
3 votes
0 answers
103 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}^...
D.W.'s user avatar
  • 12.2k
3 votes
0 answers
130 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 ...
argentpepper's user avatar
  • 2,281
3 votes
0 answers
78 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_{...
SAmath's user avatar
  • 425
2 votes
0 answers
72 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$ ...
bolzep's user avatar
  • 21
2 votes
0 answers
88 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 ...
user2316602's user avatar
2 votes
0 answers
205 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 ...
Ted's user avatar
  • 21
2 votes
0 answers
110 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 ...
Paddy's user avatar
  • 121
2 votes
0 answers
66 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 ...
rajatsen91's user avatar
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}$...
SAmath's user avatar
  • 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....
Chad Brewbaker's user avatar
1 vote
0 answers
32 views

Encoding of nodes in Binary Decision Diagrams

A straightforward implementation of Binary Decision Diagrams (BDDs) typically requires 24 bytes per node, with an additional 8 bytes commonly used for auxiliary data. Each node is encoded as a 4-tuple ...
Taylor Sasser's user avatar
1 vote
0 answers
41 views

Practical Applications of Information Algebras

I've started reading Information Algebras, Kohlas (the Wikipedia may give you the gist) and I am curious as to whether any ideas from this theory/book could be practically implemented, perhaps as some ...
Matt X's user avatar
  • 111
1 vote
0 answers
42 views

Why the measure of information complexities for passive and active learning are increasing in research communities?

I am a PhD student working on the theory of active learning. Over the years, accepted papers in COLT and ALT for active learning are focused on approaches that almost all of them define new ...
ayaxxx's user avatar
  • 120
1 vote
0 answers
92 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 ...
learning_tcs's user avatar
1 vote
0 answers
56 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 ...
dorikolmo's user avatar
1 vote
0 answers
128 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 ...
Koko Nanahji's user avatar
1 vote
0 answers
86 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:\...
Fred Guth's user avatar
  • 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 ...
tomerg's user avatar
  • 181
1 vote
0 answers
66 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 ...
einpoklum's user avatar
  • 173
1 vote
0 answers
144 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 ...
anurag anshu's user avatar
1 vote
0 answers
146 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 ...
Veksi's user avatar
  • 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 ...
SAmath's user avatar
  • 425
1 vote
0 answers
215 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 ...
gaborous's user avatar
  • 131
1 vote
0 answers
20 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 ...
Turbo's user avatar
  • 13k
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:/...
Turbo's user avatar
  • 13k
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 ...
Turbo's user avatar
  • 13k
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 ...
Andrew Tomazos's user avatar
1 vote
0 answers
614 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 ...
Keenan Pepper's user avatar