@misc{15385,
  abstract     = {Relevant information about the data can be found in the 'Readme_Data.txt' file. 
A previous version of the publication can be found on BioRxiv: https://www.biorxiv.org/content/10.1101/2022.10.11.511691v4
and published in Plos Biology (2024)},
  author       = {Burnett, Laura and Koppensteiner, Peter and Symonova, Olga and Masson, Tomas and Vega Zuniga, Tomas A and Contreras, Ximena and Rülicke, Thomas and Shigemoto, Ryuichi and Novarino, Gaia and Jösch, Maximilian A},
  keywords     = {ASD, periaqueductal gray, perception, behavior, potassium channels},
  publisher    = {Institute of Science and Technology Austria},
  title        = {{Shared behavioural impairments in visual perception and place avoidance across different autism models are driven by periaqueductal grey hypoexcitability in Setd5 haploinsufficient mice}},
  doi          = {10.15479/AT:ISTA:15385},
  year         = {2024},
}

@article{15404,
  abstract     = {We used diverse methods to characterize the role of avian lateral spiriform nucleus (SpL) in basal ganglia motor function. Connectivity analysis showed that SpL receives input from globus pallidus (GP), and the intrapeduncular nucleus (INP) located ventromedial to GP, whose neurons express numerous striatal markers. SpL-projecting GP neurons were large and aspiny, while SpL-projecting INP neurons were medium sized and spiny. Connectivity analysis further showed that SpL receives inputs from subthalamic nucleus (STN) and substantia nigra pars reticulata (SNr), and that the SNr also receives inputs from GP, INP, and STN. Neurochemical analysis showed that SpL neurons express ENK, GAD, and a variety of pallidal neuron markers, and receive GABAergic terminals, some of which also contain DARPP32, consistent with GP pallidal and INP striatal inputs. Connectivity and neurochemical analysis showed that the SpL input to tectum prominently ends on GABAA receptor-enriched tectobulbar neurons. Behavioral studies showed that lesions of SpL impair visuomotor behaviors involving tracking and pecking moving targets. Our results suggest that SpL modulates brainstem-projecting tectobulbar neurons in a manner comparable to the demonstrated influence of GP internus on motor thalamus and of SNr on tectobulbar neurons in mammals. Given published data in amphibians and reptiles, it seems likely the SpL circuit represents a major direct pathway-type circuit by which the basal ganglia exerts its motor influence in nonmammalian tetrapods. The present studies also show that avian striatum is divided into three spatially segregated territories with differing connectivity, a medial striato-nigral territory, a dorsolateral striato-GP territory, and the ventrolateral INP motor territory.},
  author       = {Reiner, Anton and Medina, Loreta and Abellan, Antonio and Deng, Yunping and Toledo, Claudio A.B. and Luksch, Harald and Vega Zuniga, Tomas A and Riley, Nell B. and Hodos, William and Karten, Harvey J.},
  issn         = {1096-9861},
  journal      = {Journal of Comparative Neurology},
  number       = {5},
  publisher    = {Wiley},
  title        = {{Neurochemistry and circuit organization of the lateral spiriform nucleus of birds: A uniquely nonmammalian direct pathway component of the basal ganglia}},
  doi          = {10.1002/cne.25620},
  volume       = {532},
  year         = {2024},
}

@article{15405,
  abstract     = {We report JWST/NIRCam measurements of quasar host galaxy emissions and supermassive black hole (SMBH) masses for six quasars at 5.9 < z < 7.1 in the Emission-line galaxies and Intergalactic Gas in the Epoch of Reionization (EIGER) project. We obtain deep NIRCam imaging in the F115W, F200W, and F356W bands, as well as F356W grism spectroscopy of the quasars. We use bright unsaturated stars to construct models of the point-spread functions (PSFs) and estimate the errors of these PSFs. We then measure or constrain the fluxes and morphology of the quasar host galaxies by fitting the quasar images as a point source plus an exponential disk. We successfully detect the host galaxies of three quasars, which have host-to-quasar-flux ratios of ∼1%–5%. Spectral energy distribution fitting suggests that these quasar host galaxies have stellar masses of M* ≳ 1010M⊙. For quasars with host galaxy nondetections, we estimate the upper limits of their stellar masses. We use the grism spectra to measure the Hβ line profile and the continuum luminosity, then estimate the SMBH masses for the quasars. Our results indicate that the positive relation between SMBH masses and host galaxy stellar masses already exists at redshift z ≳ 6. The quasars in our sample show a high BH-to-stellar-mass ratio of MBH/M* ∼ 0.15, which is about ∼2 dex higher than local relations. We find that selection effects only contribute partially to the high MBH/M* ratios of high-redshift quasars. This result hints at a possible redshift evolution of the MBH–M* relation.},
  author       = {Yue, Minghao and Eilers, Anna Christina and Simcoe, Robert A. and Mackenzie, Ruari and Matthee, Jorryt J and Kashino, Daichi and Bordoloi, Rongmon and Lilly, Simon J. and Naidu, Rohan P.},
  issn         = {1538-4357},
  journal      = {Astrophysical Journal},
  number       = {2},
  publisher    = {IOP Publishing},
  title        = {{EIGER. V. Characterizing the host galaxies of luminous quasars at z ≳ 6}},
  doi          = {10.3847/1538-4357/ad3914},
  volume       = {966},
  year         = {2024},
}

@article{15406,
  abstract     = {We report on dynamic Shubnikov–de Haas (SdH) oscillations that are measured in the optical response, subterahertz transmittance of two-dimensional systems, and reveal two distinct types of oscillation nodes: “universal” nodes at integer ratios of radiation and cyclotron frequencies and “tunable” nodes at positions sensitive to all parameters of the structure. The nodes in both real and imaginary parts of the measured complex transmittance are analyzed using a dynamic version of the static Lifshitz-Kosevich formula. These results demonstrate that the node structure of the dynamic SdH oscillations provides an all-optical access to quantization- and interaction-induced renormalization effects, in addition to parameters one can obtain from the static SdH oscillations.},
  author       = {Savchenko, M. L. and Gospodarič, J. and Shuvaev, A. and Dmitriev, I. A. and Dziom, Vlad and Dobretsova, A. A. and Mikhailov, N. N. and Kvon, Z. D. and Pimenov, A.},
  issn         = {2643-1564},
  journal      = {Physical Review Research},
  number       = {2},
  publisher    = {American Physical Society},
  title        = {{Optical Shubnikov-de Haas oscillations in two-dimensional electron systems}},
  doi          = {10.1103/PhysRevResearch.6.L022027},
  volume       = {6},
  year         = {2024},
}

@article{15407,
  abstract     = {We propose and implement a family of quantum-informed recursive optimization (QIRO) algorithms for combinatorial optimization problems. Our approach leverages quantum resources to obtain information that is used in problem-specific classical reduction steps that recursively simplify the problem. These reduction steps address the limitations of the quantum component (e.g., locality) and ensure solution feasibility in constrained optimization problems. Additionally, we use backtracking techniques to further improve the performance of the algorithm without increasing the requirements on the quantum hardware. We showcase the capabilities of our approach by informing QIRO with correlations from classical simulations of shallow circuits of the quantum approximate optimization algorithm, solving instances of maximum independent set and maximum satisfiability problems with hundreds of variables. We also demonstrate how QIRO can be deployed on a neutral atom quantum processor to find large independent sets of graphs. In summary, our scheme achieves results comparable to classical heuristics even with relatively weak quantum resources. Furthermore, enhancing the quality of these quantum resources improves the performance of the algorithms. Notably, the modular nature of QIRO offers various avenues for modifications, positioning our work as a template for a broader class of hybrid quantum-classical algorithms for combinatorial optimization.},
  author       = {Finžgar, Jernej Rudi and Kerschbaumer, Aron and Schuetz, Martin J.A. and Mendl, Christian B. and Katzgraber, Helmut G.},
  issn         = {2691-3399},
  journal      = {PRX Quantum},
  number       = {2},
  publisher    = {American Physical Society},
  title        = {{Quantum-informed recursive optimization algorithms}},
  doi          = {10.1103/PRXQuantum.5.020327},
  volume       = {5},
  year         = {2024},
}

@article{15408,
  abstract     = {Background: IgE-mediated degranulation of mast cells (MCs) provides rapid protection against environmental hazards, including animal venoms. A fraction of tissue-resident MCs intimately associates with blood vessels. These perivascular MCs were reported to extend projections into the vessel lumen and to be the first MCs to acquire intravenously injected IgE, suggesting that IgE loading of MCs depends on their vascular association.
Objective: We sought to elucidate the molecular basis of the MC–blood vessel interaction and to determine its relevance for IgE-mediated immune responses.
Methods: We selectively inactivated the Itgb1 gene, encoding the β1 chain of integrin adhesion molecules (ITGB1), in MCs by conditional gene targeting in mice. We analyzed skin MCs for blood vessel association, surface IgE density, and capability to bind circulating antibody specific for MC surface molecules, as well as in vivo responses to antigen administered via different routes.
Results: Lack of ITGB1 expression severely compromised MC–blood vessel association. ITGB1-deficient MCs showed normal densities of surface IgE but reduced binding of intravenously injected antibodies. While their capacity to degranulate in response to IgE ligation in vivo was unimpaired, anaphylactic responses to antigen circulating in the vasculature were largely abolished.
Conclusions: ITGB1-mediated association of MCs with blood vessels is key for MC immune surveillance of blood vessel content, but is dispensable for slow steady-state loading of endogenous IgE onto tissue-resident MCs.},
  author       = {Link, Kristina and Muhandes, Lina and Polikarpova, Anastasia and Lämmermann, Tim and Sixt, Michael K and Fässler, Reinhard and Roers, Axel},
  issn         = {1097-6825},
  journal      = {Journal of Allergy and Clinical Immunology},
  number       = {3},
  pages        = {745--753},
  publisher    = {Elsevier},
  title        = {{Integrin β1–mediated mast cell immune-surveillance of blood vessel content}},
  doi          = {10.1016/j.jaci.2024.03.022},
  volume       = {154},
  year         = {2024},
}

@misc{17042,
  abstract     = {Bacterial cell walls are gigadalton-large cross-linked polymers with a wide range of motional amplitudes, including rather rigid as well as highly flexible parts. Magic-angle spinning NMR is a powerful method to obtain atomic-level information about intact cell walls. Here we investigate sensitivity and information content of different homonuclear 13C-13C and heteronuclear H-N, H-C and N-C correlation experiments. We demonstrate that a CPMAS CryoProbe yields ca. 8-fold increased signal-to-noise over a room-temperature probe, or a ca. 3-4-fold larger per-mass sensitivity. The increased sensitivity allowed to obtain high-resolution spectra even on intact bacteria. Moreover, we compare resolution and sensitivity of 1H MAS experiments obtained at 100 kHz vs. 55 kHz. Our study provides useful hints for choosing experiments to extract atomic-level details on cell-wall samples. },
  author       = {Schanda, Paul},
  keywords     = {nuclear magnetic resonance, NMR, cellwall, structural biology, spectroscopy},
  publisher    = {Institute of Science and Technology Austria},
  title        = {{Raw data to "MAS NMR experiments of corynebacterial cell walls: complementary 1H- and CPMAS CryoProbe-enhanced 13C-detected experiments"}},
  doi          = {10.15479/AT:ISTA:17042},
  year         = {2024},
}

@article{17047,
  abstract     = {We provide a dynamical study of a model of multiplicative perturbation of a unitary matrix introduced by Fyodorov. In particular, we identify a flow of deterministic domains that bound the spectrum with high probability, separating the outlier from the typical eigenvalues at all sub-critical timescales. These results are obtained under generic assumptions on U that hold for a variety of unitary random matrix models.},
  author       = {Dubach, Guillaume and Reker, Jana},
  issn         = {2010-3271},
  journal      = {Random Matrices: Theory and Applications},
  number       = {2},
  publisher    = {World Scientific Publishing},
  title        = {{Dynamics of a rank-one multiplicative perturbation of a unitary matrix}},
  doi          = {10.1142/s2010326324500072},
  volume       = {13},
  year         = {2024},
}

@article{17048,
  abstract     = {A key mechanism employed by plants to adapt to salinity stress involves maintaining ion homeostasis via the actions of ion transporters. While the function of cation transporters in maintaining ion homeostasis in plants has been extensively studied, little is known about the roles of their anion counterparts in this process. Here, we describe a mechanism of salt adaptation in plants. We characterized the chloride channel (CLC) gene AtCLCf, whose expression is regulated by WRKY transcription factor under salt stress in Arabidopsis thaliana. Loss-of-function atclcf seedlings show increased sensitivity to salt, whereas AtCLCf overexpression confers enhanced resistance to salt stress. Salt stress induces the translocation of GFP-AtCLCf fusion protein to the plasma membrane (PM). Blocking AtCLCf translocation using the exocytosis inhibitor brefeldin-A or mutating the small GTPase gene AtRABA1b/BEX5 (RAS GENES FROM RAT BRAINA1b homolog) increases salt sensitivity in plants. Electrophysiology and liposome-based assays confirm the Cl−/H+ antiport function of AtCLCf. Therefore, we have uncovered a mechanism of plant adaptation to salt stress involving the NaCl-induced translocation of AtCLCf to the PM, thus facilitating Cl− removal at the roots, and increasing the plant’s salinity tolerance.},
  author       = {Rajappa, Sivamathini and Krishnamurthy, Pannaga and Huang, Hua and Yu, Dejie and Friml, Jiří and Xu, Jian and Kumar, Prakash P.},
  issn         = {2041-1723},
  journal      = {Nature Communications},
  publisher    = {Springer Nature},
  title        = {{The translocation of a chloride channel from the Golgi to the plasma membrane helps plants adapt to salt stress}},
  doi          = {10.1038/s41467-024-48234-z},
  volume       = {15},
  year         = {2024},
}

@article{17050,
  abstract     = {The process of polymer condensation, i.e., the formation of bonds between reactive end groups, is ubiquitous in both industry and biology. Here we study generic systems undergoing polymer condensation in competition with cyclization. Using a generalized Smoluchowski theory, molecular dynamics simulations and experiments with DNA and ATP-consuming T4 ligase, we find that this system displays a transition, from a ring-dominated regime with finite-length chains at infinite time to a linear-polymers-dominated one with chains that keep growing in time. Finally, we show that fluids prepared close to the transition may have widely different compositions and rheology at large condensation times.},
  author       = {Panoukidou, Maria and Weir, Simon and Sorichetti, Valerio and Fosado, Yair Gutierrez and Lenz, Martin and Michieletto, Davide},
  issn         = {2643-1564},
  journal      = {Physical Review Research},
  number       = {2},
  publisher    = {American Physical Society},
  title        = {{Runaway transition in irreversible polymer condensation with cyclization}},
  doi          = {10.1103/PhysRevResearch.6.023189},
  volume       = {6},
  year         = {2024},
}

@inproceedings{17051,
  abstract     = {Memory-hard functions (MHF) are functions whose evaluation provably requires
a lot of memory. While MHFs are an unkeyed primitive, it is natural to consider the
notion of trapdoor MHFs (TMHFs). A TMHF is like an MHF, but when sampling
the public parameters one also samples a trapdoor which allows evaluating the
function much cheaper.
Biryukov and Perrin (Asiacrypt’17) were the first to consider TMHFs and put
forth a candidate TMHF construction called Diodon that is based on the Scrypt
MHF (Percival, BSDCan’09). To allow for a trapdoor, Scrypt’s initial hash chain
is replaced by a sequence of squares in a group of unknown order where the order of
the group is the trapdoor. For a length n sequence of squares and a group of order
N, Diodon’s cumulative memory complexity (CMC) is O(n2log N) without the
trapdoor and O(n log(n) log(N)2) with knowledge of it.
While Scrypt is proven to be optimally memory-hard in the random oracle
model (Alwen et al., Eurocrypt’17), Diodon’s memory-hardness has not been
proven so far. In this work, we fill this gap by rigorously analyzing a specific
instantiation of Diodon. We show that its CMC is lower bounded by Ω( n2log nlog N)
which almost matches the upper bound. Our proof is based Alwen et al.’s lower
bound on Scrypt’s CMC but requires non-trivial modifications due to the algebraic
structure of Diodon. Most importantly, our analysis involves a more elaborate
compression argument and a solvability criterion for certain systems of Diophantine
equations.},
  author       = {Auerbach, Benedikt and Günther, Christoph Ullrich and Pietrzak, Krzysztof Z},
  booktitle    = {43rd Annual International Conference on the Theory and Applications of Cryptographic Techniques},
  isbn         = {9783031587337},
  issn         = {1611-3349},
  location     = {Zurich, Switzerland},
  pages        = {315--344},
  publisher    = {Springer Nature},
  title        = {{Trapdoor memory-hard functions}},
  doi          = {10.1007/978-3-031-58734-4_11},
  volume       = {14653},
  year         = {2024},
}

@article{17054,
  abstract     = {Photoisomerization and photoluminescence are two distinct energy dissipation pathways in light-driven molecular motors. The photoisomerization properties of discrete molecular motors have been well established in solution, but their photoluminescent properties have been rarely reported—especially in aggregates. Here, it is shown that an overcrowded alkene-based molecular motor exhibits distinct dynamic properties in solution and aggregate states, for example, gel and solid states. Despite the poor emissive properties of molecular motors in solution, a bright emission is observed in the aggregate states, including in gel and the crystalline solid. The emission wavelength is highly dependent on the nature of the supramolecular packing and order in the aggregates. As a result, the fluorescent color can be readily tuned reversibly via mechanical grinding and vapor fuming, which provides a new platform for developing multi-stimuli functional materials.},
  author       = {Shan, Yahan and Sheng, Jinyu and Zhang, Qi and Stuart, Marc C.A. and Qu, Da Hui and Feringa, Ben L.},
  issn         = {2692-4560},
  journal      = {Aggregate},
  number       = {5},
  publisher    = {Wiley},
  title        = {{Multi-state photoluminescent properties of an overcrowded alkene-based molecular motor in aggregates}},
  doi          = {10.1002/agt2.584},
  volume       = {5},
  year         = {2024},
}

@article{17089,
  abstract     = {How the coordination of neuronal spiking and brain rhythms between hippocampal subregions supports memory function remains elusive. We studied the interregional coordination of CA3 neuronal spiking with CA1 theta oscillations by recording electrophysiological signals along the proximodistal axis of the hippocampus in rats that were performing a high-memory-demand recognition memory task adapted from humans. We found that CA3 population spiking occurs preferentially at the peak of distal CA1 theta oscillations when memory was tested but only when previously encountered stimuli were presented. In addition, decoding analyses revealed that only population cell firing of proximal CA3 together with that of distal CA1 can predict performance at test in the present non-spatial task. Overall, our work demonstrates an important role for the synchronization of CA3 neuronal activity with CA1 theta oscillations during memory testing.},
  author       = {Ku, Shih Pi and Atucha, Erika and Alavi, Nico and Mulla-Osman, Halla and Kayumova, Rukhshona and Yoshida, Motoharu and Csicsvari, Jozsef L and Sauvage, Magdalena M.},
  issn         = {2211-1247},
  journal      = {Cell Reports},
  number       = {6},
  publisher    = {Elsevier},
  title        = {{Phase locking of hippocampal CA3 neurons to distal CA1 theta oscillations selectively predicts memory performance}},
  doi          = {10.1016/j.celrep.2024.114276},
  volume       = {43},
  year         = {2024},
}

@article{17090,
  abstract     = {Primordial neutral atomic gas, mostly composed of hydrogen, is the raw material for star formation in galaxies. However, there are few direct constraints on the amount of neutral atomic hydrogen (H i) in galaxies at early cosmic times. We analyzed James Webb Space Telescope (JWST) near-infrared spectroscopy of distant galaxies, at redshifts ≳8. From a sample of 12 galaxies, we identified three that show strong damped Lyman-α absorption due to H i in their local surroundings. The galaxies are located at spectroscopic redshifts of 8.8, 10.2, and 11.4, corresponding to 400 to 600 million years after the Big Bang. They have H i column densities ≳1022 cm−2, which is an order of magnitude higher than expected for a fully neutral intergalactic medium, and constitute a gas-rich population of young star-forming galaxies.},
  author       = {Heintz, Kasper E. and Watson, Darach and Brammer, Gabriel and Vejlgaard, Simone and Hutter, Anne and Strait, Victoria B. and Matthee, Jorryt J and Oesch, Pascal A. and Jakobsson, Páll and Tanvir, Nial R. and Laursen, Peter and Naidu, Rohan P. and Mason, Charlotte A. and Killi, Meghana and Jung, Intae and Hsiao, Tiger Yu Yang and Abdurro’Uf, Unknown and Coe, Dan and Haro, Pablo Arrabal and Finkelstein, Steven L. and Toft, Sune},
  issn         = {1095-9203},
  journal      = {Science},
  number       = {6698},
  pages        = {890--894},
  publisher    = {AAAS},
  title        = {{Strong damped Lyman-a absorption in young star-forming galaxies at redshifts 9 to 11}},
  doi          = {10.1126/science.adj0343},
  volume       = {384},
  year         = {2024},
}

@article{17091,
  abstract     = {DNA sequences are connected to genes and functions in the developing and adult brain},
  author       = {Novarino, Gaia and Bock, Christoph},
  issn         = {1095-9203},
  journal      = {Science},
  number       = {6698},
  pages        = {860--861},
  publisher    = {AAAS},
  title        = {{Mapping the brain’s gene-regulatory maze}},
  doi          = {10.1126/science.adp4663},
  volume       = {384},
  year         = {2024},
}

@article{17092,
  abstract     = {Memories are thought to be stored in neural ensembles known as engrams that are specifically reactivated during memory recall. Recent studies have found that memory engrams of two events that happened close in time tend to overlap in the hippocampus and the amygdala, and these overlaps have been shown to support memory linking. It has been hypothesized that engram overlaps arise from the mechanisms that regulate memory allocation itself, involving neural excitability, but the exact process remains unclear. Indeed, most theoretical studies focus on synaptic plasticity and little is known about the role of intrinsic plasticity, which could be mediated by neural excitability and serve as a complementary mechanism for forming memory engrams. Here, we developed a rate-based recurrent neural network that includes both synaptic plasticity and neural excitability. We obtained structural and functional overlap of memory engrams for contexts that are presented close in time, consistent with experimental and computational studies. We then investigated the role of excitability in memory allocation at the network level and unveiled competitive mechanisms driven by inhibition. This work suggests mechanisms underlying the role of intrinsic excitability in memory allocation and linking, and yields predictions regarding the formation and the overlap of memory engrams.},
  author       = {Delamare, Geoffroy and Feitosa Tomé, Douglas and Clopath, Claudia},
  issn         = {1529-2401},
  journal      = {Journal of Neuroscience},
  number       = {21},
  publisher    = {Society for Neuroscience},
  title        = {{Intrinsic neural excitability biases allocation and overlap of memory engrams}},
  doi          = {10.1523/JNEUROSCI.0846-23.2024},
  volume       = {44},
  year         = {2024},
}

@inproceedings{17093,
  abstract     = {Federated Learning (FL) enables large-scale distributed training of machine learning models, while still allowing individual nodes to maintain data locally. However, executing FL at scale comes with inherent practical challenges: 1) heterogeneity of the local node data distributions, 2) heterogeneity of node computational speeds (asynchrony), but also 3) constraints in the amount of communication between the clients and the server. In this work, we present the first variant of the classic federated averaging (FedAvg) algorithm which, at the same time, supports data heterogeneity, partial client asynchrony, and communication compression. Our algorithm comes with a novel, rigorous analysis showing that, in spite of these system relaxations, it can provide similar convergence to FedAvg in interesting parameter regimes. Experimental results in the rigorous LEAF benchmark on setups of up to 300 nodes show that our algorithm ensures fast convergence for standard federated tasks, improving upon prior quantized and asynchronous approaches.},
  author       = {Zakerinia, Hossein and Talaei, Shayan and Nadiradze, Giorgi and Alistarh, Dan-Adrian},
  booktitle    = {Proceedings of the 27th International Conference on Artificial Intelligence and Statistics},
  issn         = {2640-3498},
  location     = {Valencia, Spain},
  pages        = {3448--3456},
  publisher    = {ML Research Press},
  title        = {{Communication-efficient federated learning with data and client heterogeneity}},
  volume       = {238},
  year         = {2024},
}

@inproceedings{17098,
  abstract     = {Turn-based discounted-sum games are two-player zero-sum games played on finite directed graphs. The vertices of the graph are partitioned between player 1 and player 2. Plays are infinite walks on the graph where the next vertex is decided by a player that owns the current vertex. Each edge is assigned an integer weight and the payoff of a play is the discounted-sum of the weights of the play. The goal of player 1 is to maximize the discounted-sum payoff against the adversarial player 2. These games lie in NP ∩ coNP and are among the rare combinatorial problems that belong to this complexity class and the existence of a polynomial-time algorithm is a major open question. Since breaking the general exponential barrier has been a challenging problem, faster parameterized algorithms have been considered. If the discount factor is expressed in unary, then discounted-sum games can be solved in polynomial time. However, if the discount factor is arbitrary (or expressed in binary), but the weights are in unary, none of the existing approaches yield a sub-exponential bound. Our main result is a new analysis technique for a classical algorithm (namely, the strategy iteration algorithm) that present a new runtime bound which is [EQUATION] for game graphs with n vertices and absolute weights of at most W. In particular, our result yields a deterministic sub-exponential bound for games with weights that are constant or represented in unary.},
  author       = {Asadi, Ali and Chatterjee, Krishnendu and Svoboda, Jakub and Saona Urmeneta, Raimundo J},
  booktitle    = {39th Annual ACM/IEEE Symposium on Logic in Computer Science},
  isbn         = {9798400706608},
  issn         = {1043-6871},
  location     = {Tallinn, Estonia},
  publisher    = {Association for Computing Machinery},
  title        = {{Deterministic sub-exponential algorithm for discounted-sum games with unary weights}},
  doi          = {10.1145/3661814.3662080},
  year         = {2024},
}

@inproceedings{17099,
  abstract     = {We study two-player zero-sum concurrent stochastic games with finite state and action space played for an infinite number of steps. In every step, the two players simultaneously and independently choose an action. Given the current state and the chosen actions, the next state is obtained according to a stochastic transition function. An objective is a measurable function on plays (or infinite trajectories) of the game, and the value for an objective is the maximal expectation that the player can guarantee against the adversarial player. We consider: (a) stateful-discounted objectives, which are similar to the classical discounted-sum objectives, but states are associated with different discount factors rather than a single discount factor; and (b) parity objectives, which are a canonical representation for ω-regular objectives. For stateful-discounted objectives, given an ordering of the discount factors, the limit value is the limit of the value of the stateful-discounted objectives, as the discount factors approach zero according to the given order.
The computational problem we consider is the approximation of the value within an arbitrary
additive error. The above problem is known to be in EXPSPACE for the limit value of statefuldiscounted objectives and in PSPACE for parity objectives. The best-known algorithms for both the above problems are at least exponential time, with an exponential dependence on the number of states and actions. Our main results for the value approximation problem for the limit value of stateful-discounted objectives and parity objectives are as follows: (a) we establish TFNP[NP] complexity; and (b) we present algorithms that improve the dependency on the number of actions in the exponent from linear to logarithmic. In particular, if the number of states is constant, our algorithms run in polynomial time.},
  author       = {Asadi, Ali and Chatterjee, Krishnendu and Saona Urmeneta, Raimundo J and Svoboda, Jakub},
  booktitle    = {44th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science},
  isbn         = {9783959773553},
  issn         = {1868-8969},
  location     = {Gujarat, India},
  publisher    = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik},
  title        = {{Concurrent stochastic games with stateful-discounted and parity objectives: Complexity and algorithms}},
  doi          = {10.4230/LIPIcs.FSTTCS.2024.5},
  volume       = {323},
  year         = {2024},
}

@unpublished{17101,
  abstract     = {This paper considers a class of two-player zero-sum games on directed graphs whose vertices are equipped with random payoffs of bounded support known by both players.
Starting from a fixed vertex, players take turns to move a token along the edges of the graph.
On the one hand, for acyclic directed graphs of bounded degree and sub-exponential expansion, we show that the value of the game converges almost surely to a constant at an exponential rate dominated in terms of the expansion.
On the other hand, for the infinite d-ary tree that does not fall into the previous class of graphs, we show convergence at a double-exponential rate in terms of the expansion.},
  author       = {Attia, Luc and Lichev, Lyuben and Mitsche, Dieter and Saona Urmeneta, Raimundo J and Ziliotto, Bruno},
  booktitle    = {arXiv},
  title        = {{Zero-sum random games on directed graphs}},
  doi          = {10.48550/arXiv.2401.16252},
  year         = {2024},
}