Other works

We have also examined other problems during the course of developing this dissertation. For one, we have looked at full-rank tilings in eight and nine dimensions [59], based on an open problem in [21]. Such tilings are related to the existence of perfect codes. We modified computational techniques based on the graph-isomorphism problem, pioneered in [46], and added some manual analysis to prove the non-existence of these tilings.

Secondly, we have looked at the problem of reconciling two physically separated, unordered databases whose contents are related [44,57]. Specifically, we have considered determining the mutual difference of these databases with a minimum communication complexity. This type of problem arises naturally from gossip protocols used for the distribution of information. We analyzed two instances of the reconciliation problem, a client-server model and a more general peer-to-peer model, and provided interactive solutions for both models. For the former instance, we also provided a simple one-message reconciliation algorithm, based on elementary symmetric polynomials, which has an almost optimal communication complexity. Finally, we demonstrated several applications of our reconciliation algorithms, including an improvement of [30]'s solution of the resource discovery problem.