More Like this

1. Estimates for the Branching Factors of Atari Games

   https://doi.org/10.1109/CoG52621.2021.9619137  

   Nelson, Mark J. (August 2021, Proceedings of the 2021 IEEE Conference on Games)

   The branching factor of a game is the average number of new states reachable from a given state. It is a widely used metric in AI research on board games, but less often computed or discussed for videogames. This paper provides estimates for the branching factors of 103 Atari 2600 games, as implemented in the Arcade Learning Environment (ALE). Depending on the game, ALE exposes between 3 and 18 available actions per frame of gameplay, which is an upper bound on branching factor. This paper shows, based on an enumeration of the first 1 million distinct states reachable in each game, that the average branching factor is usually much lower, in many games barely above 1. In addition to reporting the branching factors, this paper aims to clarify what constitutes a distinct state in ALE. 

   more » « less
2. Measurement of the very rare K+ → $$ {\pi}^{+}\nu \overline{\nu} $$ decay

   https://doi.org/10.1007/JHEP06(2021)093  

   Cortina Gil, E.; Kleimenova, A.; Minucci, E.; Padolski, S.; Petrov, P.; Shaikhiev, A.; Volpe, R.; Numao, T.; Petrov, Y.; Velghe, B.; et al (June 2021, Journal of High Energy Physics)

   A bstract The NA62 experiment reports the branching ratio measurement $$ \mathrm{BR}\left({K}^{+}\to {\pi}^{+}\nu \overline{\nu}\right)=\left({10.6}_{-3.4}^{+4.0}\left|{}_{\mathrm{stat}}\right.\pm {0.9}_{\mathrm{syst}}\right)\times {10}^{-11} $$ BR K + → π + ν ν ¯ = 10.6 − 3.4 + 4.0 stat ± 0.9 syst × 10 − 11 at 68% CL, based on the observation of 20 signal candidates with an expected background of 7.0 events from the total data sample collected at the CERN SPS during 2016–2018. This provides evidence for the very rare K + → $$ {\pi}^{+}\nu \overline{\nu} $$ π + ν ν ¯ decay, observed with a significance of 3.4 σ . The experiment achieves a single event sensitivity of (0 . 839 ± 0 . 054) × 10 − 11 , corresponding to 10.0 events assuming the Standard Model branching ratio of (8 . 4 ± 1 . 0) × 10 − 11 . This measurement is also used to set limits on BR( K + → π + X ), where X is a scalar or pseudo-scalar particle. Details are given of the analysis of the 2018 data sample, which corresponds to about 80% of the total data sample. 

   more » « less
3. An investigation of the very rare $$ {K}^{+}\to {\pi}^{+}\nu \overline{\nu} $$ decay

   https://doi.org/10.1007/JHEP11(2020)042  

   Cortina Gil, E.; Kleimenova, A.; Minucci, E.; Padolski, S.; Petrov, P.; Shaikhiev, A.; Volpe, R.; Numao, T.; Velghe, B.; Bryman, D.; et al (November 2020, Journal of High Energy Physics)

   null (Ed.)

   A bstract The NA62 experiment reports an investigation of the $$ {K}^{+}\to {\pi}^{+}\nu \overline{\nu} $$ K + → π + ν ν ¯ mode from a sample of K + decays collected in 2017 at the CERN SPS. The experiment has achieved a single event sensitivity of (0 . 389 ± 0 . 024) × 10 − 10 , corresponding to 2.2 events assuming the Standard Model branching ratio of (8 . 4 ± 1 . 0) × 10 − 11 . Two signal candidates are observed with an expected background of 1.5 events. Combined with the result of a similar analysis conducted by NA62 on a smaller data set recorded in 2016, the collaboration now reports an upper limit of 1 . 78 × 10 − 10 for the $$ {K}^{+}\to {\pi}^{+}\nu \overline{\nu} $$ K + → π + ν ν ¯ branching ratio at 90% CL. This, together with the corresponding 68% CL measurement of ( $$ {0.48}_{-0.48}^{+0.72} $$ 0.48 − 0.48 + 0.72 ) × 10 − 10 , are currently the most precise results worldwide, and are able to constrain some New Physics models that predict large enhancements still allowed by previous measurements. 

   more » « less
4. All galls are divided into three or more parts: recursive enumeration of labeled histories for galled trees

   https://doi.org/10.1186/s13015-023-00224-4  

   Mathur, Shaili; Rosenberg, Noah A. (December 2023, Algorithms for Molecular Biology)

   Abstract Objective In mathematical phylogenetics, a labeled rooted binary tree topology can possess any of a number of labeled histories, each of which represents a possible temporal ordering of its coalescences. Labeled histories appear frequently in calculations that describe the combinatorics of phylogenetic trees. Here, we generalize the concept of labeled histories from rooted phylogenetic trees to rooted phylogenetic networks, specifically for the class of rooted phylogenetic networks known as rooted galled trees . Results Extending a recursive algorithm for enumerating the labeled histories of a labeled tree topology, we present a method to enumerate the labeled histories associated with a labeled rooted galled tree. The method relies on a recursive decomposition by which each gall in a galled tree possesses three or more descendant subtrees. We exhaustively provide the numbers of labeled histories for all small galled trees, finding that each gall reduces the number of labeled histories relative to a specified galled tree that does not contain it. Conclusion The results expand the set of structures for which labeled histories can be enumerated, extending a well-known calculation for phylogenetic trees to a class of phylogenetic networks. 

   more » « less
5. Cost-sharing in Parking Games

   https://doi.org/10.46298/dmtcs.13113  

   Elder, Jennifer; Harris, Pamela E; Kretschmann, Jan; Mori, J_Carlos Martínez (November 2024, Discrete Mathematics & Theoretical Computer Science)

   In this paper, we study the total displacement statistic of parking functionsfrom the perspective of cooperative game theory. We introduce parking games,which are coalitional cost-sharing games in characteristic function formderived from the total displacement statistic. We show that parking games aresupermodular cost-sharing games, indicating that cooperation is difficult(i.e., their core is empty). Next, we study their Shapley value, whichformalizes a notion of fair cost-sharing and amounts to charging each car forits expected marginal displacement under a random arrival order. Our maincontribution is a polynomial-time algorithm to compute the Shapley value ofparking games, in contrast with known hardness results on computing the Shapleyvalue of arbitrary games. The algorithm leverages the permutation-invariance oftotal displacement, combinatorial enumeration, and dynamic programming. Weconclude with open questions around an alternative solution concept forsupermodular cost-sharing games and connections to other areas incombinatorics. 

   more » « less