**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.

**2-3 cuckoo filters for faster triangle listing and set intersection**.

D. Eppstein, M. T. Goodrich, M. Mitzenmacher, and M. Torres.

*Proc. 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems (PODS 2017)*, Chicago, 2017, pp. 247–260.

We show that bit-parallel algorithm design techniques, on a machine of word size

*w*, can speed up the time for sparse set intersection by a factor of log*w*/*w*. The main data structure underlying our algorithms is the cuckoo filter, a variant of cuckoo hash tables that has operations similar to a Bloom filter but outperforms Bloom filters in several respects.

Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine

Semi-automatically filtered from a common source file.