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.
Co-authors – Publications – David Eppstein – Theory Group – Inf. & Comp. Sci. – UC Irvine
Semi-automatically filtered from a common source file.