Let us say you (Alice) and another agent (Bob) share a large piece of data (say, the Gutenberg project collection of books, or the Linux kernel. You want to send a smaller but still large piece of ...
Lets assume that two extreme intelligent species in the universe can exchange morse code messages for the first time. A can send messages to B and B to A, both have unlimited time, but they can not ...
You have an array of length $n$ containing $n$ distinct elements. You have access to a comparator on the elements (a black-box function that takes $a$ and $b$ and returns true if $a < b$, false ...
It's well-known that the Kolmogorov complexity is uncomputable, essentially because of the halting problem: you can list all programs of length less than one known to generate a given string, but you ...
Suppose I have a multiset of numbers. I'm interested in the number of unique n-tuples that can exist using the numbers from this multiset. Now of course a closed form is of interest here, but what I'm ...
The topic/problem is related to hashing for data structures used in programming, but I seek formal treatment. I hope that by studying the problem I will be enlightened of the fundamental limitations ...