Research Interest

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

Publications and Preprints

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

  • X. S. Cai, C. Holmgren, S. Janson, T. Johansson, and F. Skerman. “Inversions in Split Trees and Conditional Galton-Watson Trees”. In: 29th International Conference on Probabilistic, Combinatorial and Asymptotic Methods for the Analysis of Algorithms (AofA 2018). Vol. 110. Leibniz International Proceedings in Informatics (LIPIcs). Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum fuer Informatik, 2018, 15:1–15:12. doi: 10.4230/LIPIcs.AofA.2018.15.

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

  • X. S. Cai, L. Devroye, C. Holmgren, and F. Skerman. “Cutting resilient networks”. In: ArXiv e-prints 2018. arXiv: 1804.03069 [math.PR].

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

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

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

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

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

  • 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

See also Google Scholar, dblp, or arxiv.

Talks

My coauthors