@inproceedings{14344,
  abstract     = {We study the Hamilton cycle problem with input a random graph G ~ G(n,p) in two different settings. In the first one, G is given to us in the form of randomly ordered adjacency lists while in the second one, we are given the adjacency matrix of G. In each of the two settings we derive a deterministic algorithm that w.h.p. either finds a Hamilton cycle or returns a certificate that such a cycle does not exist for p = p(n) ≥ 0. The running times of our algorithms are O(n) and  respectively, each being best possible in its own setting.},
  author       = {Anastos, Michael},
  booktitle    = {Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms},
  isbn         = {9781611977554},
  location     = {Florence, Italy},
  pages        = {2286--2323},
  publisher    = {Society for Industrial and Applied Mathematics},
  title        = {{Fast algorithms for solving the Hamilton cycle problem with high probability}},
  doi          = {10.1137/1.9781611977554.ch88},
  volume       = {2023},
  year         = {2023},
}

@inproceedings{12676,
  abstract     = {Turn-based stochastic games (aka simple stochastic games) are two-player zero-sum games played on directed graphs with probabilistic transitions. The goal of player-max is to maximize the probability to reach a target state against the adversarial player-min. These games lie in NP ∩ coNP and are among the rare combinatorial problems that belong to this complexity class for which the existence of polynomial-time algorithm is a major open question. While randomized sub-exponential time algorithm exists, all known deterministic algorithms require exponential time in the worst-case. An important open question has been whether faster algorithms can be obtained parametrized by the treewidth of the game graph. Even deterministic sub-exponential time algorithm for constant treewidth turn-based stochastic games has remain elusive. In this work our main result is a deterministic algorithm to solve turn-based stochastic games that, given a game with n states, treewidth at most t, and the bit-complexity of the probabilistic transition function log D, has running time O ((tn2 log D)t log n). In particular, our algorithm is quasi-polynomial time for games with constant or poly-logarithmic treewidth.},
  author       = {Chatterjee, Krishnendu and Meggendorfer, Tobias and Saona Urmeneta, Raimundo J and Svoboda, Jakub},
  booktitle    = {Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms},
  isbn         = {9781611977554},
  location     = {Florence, Italy},
  pages        = {4590--4605},
  publisher    = {Society for Industrial and Applied Mathematics},
  title        = {{Faster algorithm for turn-based stochastic games with bounded treewidth}},
  doi          = {10.1137/1.9781611977554.ch173},
  year         = {2023},
}