21 citations · 60 across the 30 of their papers we have counts for
Showing 2011Show all
2 papers · 1 filter
cs.IT2011
On essentially conditional information inequalities
Tarik Kaced, Andrei Romashchenko
In 1997, Z.Zhang and R.W.Yeung found the first example of a conditional information inequality in four variables that is not "Shannon-type". This linear inequality for entropies is…
cs.DS2011
Pseudo-random graphs and bit probe schemes with one-sided error
Andrei Romashchenko
We study probabilistic bit-probe schemes for the membership problem. Given a set A of at most n elements from the universe of size m we organize such a structure that queries of ty…