David Eppstein - Publications

Publications with Padhraic Smyth

• The distribution of cycle lengths in graphical models for iterative decoding.
  X. Ge, D. Eppstein, and P. Smyth.
  arXiv:cs.DM/9907002.
  Tech. Rep. 99-10, ICS, UCI, 1999.
  IEEE Int. Symp. Information Theory, Sorrento, Italy, 2000.
  IEEE Trans. Information Theory 47(6):2549-2553, 2001.

  We compute the expected numbers of short cycles of each length in certain classes of random graphs used for turbocodes, estimate the probability that there are no such short cycles involving a given vertex, and experimentally verify our estimates. The scarcity of short cycles may help explain the empirically observed accuracy of belief-propagation based error-correction algorithms. Note, the TR, conference, and journal versions of this paper have slightly different titles.

  (BibTeX -- Citations: TR/ISIT -- CiteSeer)

• Windows into relational events: data structures for contiguous subsequences of edges.
  M. J. Bannister, C. DuBois, D. Eppstein, and P. Smyth.
  NIPS 2012 Workshop on Algorithmic and Statistical Approaches for Large Social Networks, South Lake Tahoe, California, 2012 (poster and invited talk).
  24th ACM-SIAM Symp. Discrete Algorithms, New Orleans, Louisiana, 2013, pp. 856-864.
  arXiv:1209.5791.

  We study relational event data in which a collection of actors in a social network have a sequence of pairwise interactions. Contiguous subsequences of these interactions form graphs, and we develop efficient data structures for querying the parameters of these graphs.

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

Semi-automatically filtered from a common source file.