Research Interest

Probabilistic Combinatorics, including randomized algorithms, random graphs and random tree e.g., Galton-Watson trees, split trees, etc.

Publications

See also Google Scholar, dblp, or arxiv.

  1. X. S. Cai and J. L. López. “A note on the asymptotic expansion of the Lerch’s transcendent”. In: ArXiv e-prints (2018). arXiv: 1806.01122 [math.CV].

  2. X. S. Cai, C. Holmgren, S. Janson, T. Johansson, and F. Skerman. “Inversions in split trees and conditional Galton–Watson trees”. In: ArXiv e-prints (2017). arXiv: 1709.00216 [math.PR].

  3. X. S. Cai and S. Janson. “Non-fringe subtrees in conditioned Galton–Watson trees”. In: ArXiv e-prints (2018). arXiv: 1803.02230 [math.CO].

  4. X. S. Cai, G. Perarnau, B. Reed, and A. B. Watts. “Acyclic edge colourings of graphs with large girth”. In: Random Structures and Algorithms (2016). doi: 10.1002/rsa.20695. url: http://dx.doi.org/10.1002/rsa.20695.

  5. X. S. Cai and L. Devroye. “A study of large fringe and non-fringe subtrees in conditional Galton-Watson trees”. In: Latin American Journal of Probability and Mathematical Statistics XIV (2016), pp. 579–611. url: http://alea.impa.br/articles/v14/14-29.pdf.

  6. X. S. Cai and L. Devroye. “The graph structure of a deterministic automaton chosen at random”. In: Random Structures and Algorithms (2016). doi: 10.1002/rsa.20707. url: http://dx.doi.org/10.1002/rsa.20707.

  7. X. S. Cai and L. Devroye. “The Analysis of Kademlia for Random IDs”. In: Internet Mathematics 11.6 (2015), pp. 572–587. doi: 10.1080/15427951.2015.1051674.

  8. X. S. Cai, L. Devroye, X. S. Cai, and L. Devroye. “A probabilistic analysis of Kademlia networks”. In: Algorithms and Computation. 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings. Vol. 8283. Heidelberg, Germany: Springer-Verlag, 2013, pp. 711–721. doi: 10.1007/978-3-642-45030-3_66.

  9. X. S. Cai. “A study of large fringe and non-fringe subtrees in conditional Galton-Watson trees”. PhD thesis. McGill University, 2016. url: http://cs.mcgill.ca/~xcai9/doc/phd-thesis.pdf.

  10. X. S. Cai. “A probabilistic analysis of Kademlia networks”. MA thesis. McGill University, 2012. url: http://cs.mcgill.ca/~xcai9/doc/master-thesis.pdf.

Talks

  1. A study of large fringe and non-fringe subtrees in conditional Galton-Watson trees. Sweden Probabilistic Midwinter Meeting 2017, Meeting of the Catalan, Spanish, Swedish Math Societies, RS&A 2017. [slides]

  2. The graph structure of a deterministic automaton chosen at random. RSA 2015. CanaDAM 2015. [slides]

My colleagues