David Eppstein - Publications

Publications with Jenny Lam

• Models and algorithms for graph watermarking.
  D. Eppstein, M. T. Goodrich, J. Lam, N. Mamano, M. Mitzenmacher, and M. Torres.
  arXiv:1605.09425.
  Proc. 19th Information Security Conference (ISC 2016), Honolulu, Hawaii.
  Springer, Lecture Notes in Comp. Sci. 9866 (2016), pp. 283–301.

  We show how to modify a small number of edges in a large social network in order to make the modified copy easy to identify, even if an adversary tries to hide the modification by permuting the vertices and flipping a much larger number of edges. The result depends on the random fluctuation of vertex degrees in such networks, and the ability to uniquely identify vertices by their adjacencies to a small number of high-degree landmark vertices. This paper won the best student paper award at ISC for its student co-authors Lam, Mamano, and Torres.