Research Interest

Probabilistic Combinatorics, including randomized algorithms, random graphs and Galton-Watson trees.

Papers

  1. X. Shi 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].

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

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

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

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

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

Thesis

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

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

See also Google Scholar, dblp, or Research Gate.

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