David Eppstein - Publications

Publications with Xianping Ge

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