@inproceedings{12432,
  abstract     = {We present CertifyHAM, a deterministic algorithm that takes a graph G as input and either finds a Hamilton cycle of G or outputs that such a cycle does not exist. If G ∼ G(n, p) and p ≥
100 log n/n then the expected running time of CertifyHAM is O(n/p) which is best possible. This improves upon previous results due to Gurevich and Shelah, Thomason and Alon, and
Krivelevich, who proved analogous results for p being constant, p ≥ 12n −1/3 and p ≥ 70n
−1/2 respectively.},
  author       = {Anastos, Michael},
  booktitle    = {63rd Annual IEEE Symposium on Foundations of Computer Science},
  isbn         = {9781665455190},
  issn         = {0272-5428},
  location     = {Denver, CO, United States},
  pages        = {919--930},
  publisher    = {Institute of Electrical and Electronics Engineers},
  title        = {{Solving the Hamilton cycle problem fast on average}},
  doi          = {10.1109/FOCS54457.2022.00091},
  volume       = {2022-October},
  year         = {2022},
}