All Questions
Tagged with it.information-theory algorithms
18 questions
3
votes
0
answers
68
views
Does this information theoretical thought experiment have a name or corresponding area of research?
I came up with the following thought experiment in my research in order to better understand the way Turing machines can transfer information through their tapes (the motivation is detailed below, isn'...
- 509
6
votes
0
answers
105
views
Computing the zeta transform of a Boolean function: Space-time tradeoff
Let $f : \mathbb{F}_2^n \to \mathbb{F}_2$ be a Boolean function in $n$ variables. The zeta transform of $f$ is the Boolean function $\zeta_f : \mathbb{F}_2^n \to \mathbb{F}_2$ defined by
$$\zeta_f(y) :...
- 71
1
vote
0
answers
108
views
A variant of Huffman code
Given an alphabet of $n$ symbolswith probabilities $p_i$ for symbol $i$, we need to encode the symbols (in a prefix-free way) to binary codewords $c(i)$ with length $\ell(c(i))$ to minimize the ...
- 367
2
votes
0
answers
76
views
Finding k elements with count queries
Given a 'count in range' query access to an array of $N$ elements, our goal is to find $K$ missing elements with as few queries as possible (worst case, deterministic).
To clarify, we can query
how ...
- 21
6
votes
1
answer
721
views
Formalizing Entropy Compression (as used to constructify the Lovász Local Lemma)
In 2009, Moser published a breakthrough paper constructifying the Lovász Local Lemma (LLL). His talk at STOC was described in a blog post by Fortnow that proves a slightly weakened result using ...
- 103
1
vote
0
answers
92
views
Binary search extension for determining a hyperplane splitting a set of points in $\mathbb{R}^d$
We are given a set $S$ of $n$ points in $\mathbb{R}^d$ and a (hidden) vector $\mathbf{w}\in\mathbb{R}^d$, where each point $\mathbf{v}\in S$ is associated with a binary label equal to the sign of $\...
- 1,677
4
votes
1
answer
264
views
Information for discovering an item-colour assignment in a combinatorial game
We are given a set $S=\{i_1, i_2, \ldots, i_n\}$ of items and a set $C=\{c_1, c_2, \ldots, c_m\}$ of colours. Each item in $S$ is tinted with one colour $c\in C$. Let $\mathcal{A}$ be the set of all ...
- 1,677
4
votes
1
answer
254
views
Combinatorial computational problem about 0-1 vectors and sampling algorithms
Let $M \in \{0,1\}^{m\times n}$, where $n\gg 1$ and $m\le n$. A procedure consisting of the following three steps is repeated $t\gg 1$ times:
A row $\require{amsmath} \boldsymbol{r}$ of $M$ picked in ...
- 1,677
1
vote
0
answers
49
views
Subset with largest information gain [closed]
I am competing in a programming contest where the submission phase can be stated abstractly as follows : There is a known universe set, $U$, and a hidden target $T \subset U$. I submit $S \subset U$, ...
0
votes
1
answer
167
views
Comparisons and sorting from point of view of information theory [closed]
Suppose we have list of numbers and make some comparisons. What is known about amount of information which we gain by certain comparisons, by certain sequences of comparisons? Is there algorithm which ...
- 195
3
votes
0
answers
263
views
"Kolmogorov complexity" of models of computation
This question was partly inspired by my learning about John Tromp's binary lambda calculus and similar minimal languages such as Jot. A more detailed discussion of some of these ideas is in Michael ...
- 3,612
2
votes
1
answer
810
views
Set of distributions that minimize KL divergence,
Assuming that $p,q$ are probability distributions defined on the same support $\{x_i\}_{0 \leq i \leq n}$, $\epsilon$ a small real number, and $D_{KL}$ the Kullback-Leibler divergence,
is there a ...
- 167
7
votes
2
answers
955
views
Distribution of the computable numbers on the real number line
If we order all the positive computable real numbers $r_1,r_2,r_3...$ by their Kolmogorov complexity in some language $L$, then make a histogram plot of the $r_i$ on the real line, and we scale it ...
- 71
2
votes
1
answer
328
views
Doing column permutation under row overlap constraint
In coding theory, there are parity-check codes whose parity-check matrices $H$ are generated via column permutations. For instance, the binary LDPC codes constructed in Gallager's 1962 IRE Trans paper ...
- 285
8
votes
1
answer
1k
views
When the Lovász theta-function saturates its upper bound
The Lovász $\vartheta$-function of a graph $G$, $\vartheta(G)$, is well-known to be "sandwiched" between the independence number of the graph, $\alpha(G)$, and the chromatic number of its complement, $...
user3409
20
votes
4
answers
8k
views
FFTs over finite fields?
I'm trying to understand how to compute a fast Fourier transform over a finite field. This question arose in the analysis of some BCH codes.
Consider the finite field $F$ with $2^n$ elements. It is ...
- 3,979
0
votes
1
answer
185
views
Building optimal rewriting rules.
Please give me some pointers where I can learn more about the following problem:
I have two alphabets A and B. A have a dictionary which contains words in A together with their translation in B (ie. ...
- 173
14
votes
3
answers
3k
views
Computing the maximum salary
To motivate my question, I will describe a related problem and then give a solution to it. My question will then be a variant of this problem.
N individuals sit around a table and want to compute the ...
- 13k