We start by introducing avoidance coupling of Markov chains, with an overview of existing results. We then introduce and motivate a new notion, uniform coupling. We show that the only Markovian avoidance coupling on a cycle is of this type, and that uniform avoidance coupling of simple random walks is impossible on trees, and prove that it is possible on several classes of graphs. We also derive a condition on the vertex neighborhoods in a graph equivalent to that graph admitting a uniform avoidance coupling of simple random walks, and an algorithm that tests this with run time polynomial in the number of vertices. We then discuss a conjecture that no Markovian avoidance coupling can be possible on a tree and propose how a proof might proceed.
In the second half of this work, we talk about the design of online communication systems that aim to guarantee anonymity for their users. A popular paradigm is k-anonymity. We notice that the scarcity of a typical social relation makes k-anonymity vulnerable to traffic analysis, and propose a way to use this scarcity to reduce the efficiency cost to exactly the amount of cover traffic we might need. Then we use Bregman's theorem to show that for a given infrastructure cost, modelled by the number of edges in a bipartite graph, k-anonymity offers the highest number of possible perfect matchings between users and observed behaviors.
|Commitee:||Bratus, Sergey, Elizalde, Sergi, Holroyd, Alexander|
|School Location:||United States -- New Hampshire|
|Source:||DAI-B 77/12(E), Dissertation Abstracts International|
|Subjects:||Mathematics, Computer science|
|Keywords:||Anonymity, Avoidance coupling, Markov chains, Random walks|
Copyright in each Dissertation and Thesis is retained by the author. All Rights Reserved
The supplemental file or files you are about to download were provided to ProQuest by the author as part of a
dissertation or thesis. The supplemental files are provided "AS IS" without warranty. ProQuest is not responsible for the
content, format or impact on the supplemental file(s) on our system. in some cases, the file type may be unknown or
may be a .exe file. We recommend caution as you open such files.
Copyright of the original materials contained in the supplemental file is retained by the author and your access to the
supplemental files is subject to the ProQuest Terms and Conditions of use.
Depending on the size of the file(s) you are downloading, the system may take some time to download them. Please be