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