• A
  • A
  • A
  • ABC
  • ABC
  • ABC
  • А
  • А
  • А
  • А
  • А
Regular version of the site
Of all publications in the section: 3
Sort:
by name
by year
Article
Romashchenko A., Kaced T., Vereshchagin N. IEEE Transactions on Information Theory. 2018. Vol. 64. No. 5. P. 3610-3615.

We show that the inequality H(A|B, X) + H(A|B, Y) ≤ H(A|B) for jointly distributed random variables A, B, X, Y, which does not hold in general case, holds under some natural condition on the support of the probability distribution of A, B, X, Y. This result generalizes a version of the conditional Ingleton inequality: if for some distribution I(X : Y|A) = H(A|X, Y) = 0, then I(A : B) ≤ I (A : B|X) + I(A : B|Y)+I(X : Y). We present two applications of our result. The first one is the following easy-to-formulate theorem on edge colorings of bipartite graphs: assume that the edges of a bipartite graph are colored in K colors so that each two edges sharing a vertex have different colors and for each pair (left vertex x, right vertex y) there is at most one color a such both x and y are incident to edges with color a; assume further that the degree of each left vertex is at least L and the degree of each right vertex is at least R. Then K LR. The second application is a new method to prove lower bounds for biclique cover of bipartite graphs.

Added: Apr 6, 2018
Article
Kabatiansky G. A. IEEE Transactions on Information Theory. 2008. Vol. 54. No. 10. P. 4488-4492.
Added: Nov 1, 2008
Article
Kabatiansky G. A., Barg A. IEEE Transactions on Information Theory. 2013. Vol. 59. No. 2. P. 994-003.

An n-word y=(y-{1},dots, y-{n}) over a finite alphabet of cardinality q is called a descendant of a set of t words x1,dots, xt if every coordinate y-i,i=1,\dots, n, is contained in the set x1-i,dots, xt-i. A code {cal C=x1,dots, x M is said to have the t-IPP property if for any n -word y that is a descendant of at most t parents belonging to the code, it is possible to identify at least one of them. From earlier works, it is known that t-IPP codes of positive rate exist if and only if tleq q-1. We introduce a robust version of IPP codes which allows error-free identification of parents in the presence of a certain number of mutations, i.e., coordinates in y that can break away from the descent rule, taking arbitrary values from the alphabet or becoming completely unreadable. We show existence of robust t-IPP codes for all tleq q-1 and some positive proportion of such coordinates. We uncover a relation between the hash distance of codes and the IPP property and use it to find the exact proportion of mutant coordinates that permits identification of pirates with zero probability of error in the case of size-2 coalitions.

Added: Jan 30, 2013