Phase Transition in a Random Fragmentation Problem with Applications to Computer Science
<|reference_start|>Phase Transition in a Random Fragmentation Problem with Applications to Computer Science: We study a fragmentation problem where an initial object of size x is broken into m random pieces provided x>x_0 where x_0 is an atomic cut-off. Subsequently the fragmentation process continues for each of those daughter pieces whose sizes are bigger than x_0. The process stops when all the fragments have sizes smaller than x_0. We show that the fluctuation of the total number of splitting events, characterized by the variance, generically undergoes a nontrivial phase transition as one tunes the branching number m through a critical value m=m_c. For m<m_c, the fluctuations are Gaussian where as for m>m_c they are anomalously large and non-Gaussian. We apply this general result to analyze two different search algorithms in computer science.<|reference_end|>
@article{dean2002phase,
    title={Phase Transition in a Random Fragmentation Problem with Applications to
  Computer Science},
    author={David S. Dean and Satya N. Majumdar},
    journal={J. Phys. A. 35, L501 (2002)},
    year={2002},
    doi={10.1088/0305-4470/35/32/101},
    archivePrefix={arXiv},
    eprint={cond-mat/0205034},
    primaryClass={cond-mat.stat-mech cond-mat.dis-nn cs.DS math.PR}
}