@article{15164, abstract = {Primary implant stability, which refers to the stability of the implant during the initial healing period is a crucial factor in determining the long-term success of the implant and lays the foundation for secondary implant stability achieved through osseointegration. Factors affecting primary stability include implant design, surgical technique, and patient-specific factors like bone quality and morphology. In vivo, the cyclic nature of anatomical loading puts osteosynthesis locking screws under dynamic loads, which can lead to the formation of micro cracks and defects that slowly degrade the mechanical connection between the bone and screw, thus compromising the initial stability and secondary stability of the implant. Monotonic quasi-static loading used for testing the holding capacity of implanted screws is not well suited to capture this behavior since it cannot capture the progressive deterioration of peri‑implant bone at small displacements. In order to address this issue, this study aims to determine a critical point of loss of primary implant stability in osteosynthesis locking screws under cyclic overloading by investigating the evolution of damage, dissipated energy, and permanent deformation. A custom-made test setup was used to test implanted 2.5 mm locking screws under cyclic overloading test. For each loading cycle, maximum forces and displacement were recorded as well as initial and final cycle displacements and used to calculate damage and energy dissipation evolution. The results of this study demonstrate that for axial, shear, and mixed loading significant damage and energy dissipation can be observed at approximately 20 % of the failure force. Additionally, at this load level, permanent deformations on the screw-bone interface were found to be in the range of 50 to 150 mm which promotes osseointegration and secondary implant stability. This research can assist surgeons in making informed preoperative decisions by providing a better understanding of the critical point of loss of primary implant stability, thus improving the long-term success of the implant and overall patient satisfaction.}, author = {Silva-Henao, Juan D. and Schober, Sophie and Pahr, Dieter H. and Reisinger, Andreas G.}, issn = {1873-4030}, journal = {Medical Engineering and Physics}, publisher = {Elsevier}, title = {{Critical loss of primary implant stability in osteosynthesis locking screws under cyclic overloading}}, doi = {10.1016/j.medengphy.2024.104143}, volume = {126}, year = {2024}, } @article{15167, abstract = {We perform a diagrammatic analysis of the energy of a mobile impurity immersed in a strongly interacting two-component Fermi gas to second order in the impurity-bath interaction. These corrections demonstrate divergent behavior in the limit of large impurity momentum. We show the fundamental processes responsible for these logarithmically divergent terms. We study the problem in the general case without any assumptions regarding the fermion-fermion interactions in the bath. We show that the divergent term can be summed up to all orders in the Fermi-Fermi interaction and that the resulting expression is equivalent to the one obtained in the few-body calculation. Finally, we provide a perturbative calculation to the second order in the Fermi-Fermi interaction, and we show the diagrams responsible for these terms.}, author = {Al Hyder, Ragheed and Chevy, F. and Leyronas, X.}, issn = {2469-9934}, journal = {Physical Review A}, number = {3}, publisher = {American Physical Society}, title = {{Exploring beyond-mean-field logarithmic divergences in Fermi-polaron energy}}, doi = {10.1103/PhysRevA.109.033315}, volume = {109}, year = {2024}, } @article{15163, abstract = {For some k∈Z≥0∪{∞}, we call a linear forest k-bounded if each of its components has at most k edges. We will say a (k,ℓ)-bounded linear forest decomposition of a graph G is a partition of E(G) into the edge sets of two linear forests Fk,Fℓ where Fk is k-bounded and Fℓ is ℓ-bounded. We show that the problem of deciding whether a given graph has such a decomposition is NP-complete if both k and ℓ are at least 2, NP-complete if k≥9 and ℓ=1, and is in P for (k,ℓ)=(2,1). Before this, the only known NP-complete cases were the (2,2) and (3,3) cases. Our hardness result answers a question of Bermond et al. from 1984. We also show that planar graphs of girth at least nine decompose into a linear forest and a matching, which in particular is stronger than 3-edge-colouring such graphs.}, author = {Campbell, Rutger and Hörsch, Florian and Moore, Benjamin}, issn = {0012-365X}, journal = {Discrete Mathematics}, number = {6}, publisher = {Elsevier}, title = {{Decompositions into two linear forests of bounded lengths}}, doi = {10.1016/j.disc.2024.113962}, volume = {347}, year = {2024}, } @article{15180, abstract = {Characterizing the prevalence and properties of faint active galactic nuclei (AGNs) in the early Universe is key for understanding the formation of supermassive black holes (SMBHs) and determining their role in cosmic reionization. We perform a spectroscopic search for broad Hα emitters at z ≈ 4–6 using deep JWST/NIRCam imaging and wide field slitless spectroscopy from the EIGER and FRESCO surveys. We identify 20 Hα lines at z = 4.2–5.5 that have broad components with line widths from ∼1200–3700 km s−1, contributing ∼30%–90% of the total line flux. We interpret these broad components as being powered by accretion onto SMBHs with implied masses ∼107–8M⊙. In the UV luminosity range MUV,AGN+host = −21 to −18, we measure number densities of ≈10−5 cMpc−3. This is an order of magnitude higher than expected from extrapolating quasar UV luminosity functions (LFs). Yet, such AGN are found in only <1% of star-forming galaxies at z ∼ 5. The number density discrepancy is much lower when compared to the broad Hα LF. The SMBH mass function agrees with large cosmological simulations. In two objects, we detect complex Hα profiles that we tentatively interpret as caused by absorption signatures from dense gas fueling SMBH growth and outflows. We may be witnessing early AGN feedback that will clear dust-free pathways through which more massive blue quasars are seen. We uncover a strong correlation between reddening and the fraction of total galaxy luminosity arising from faint AGN. This implies that early SMBH growth is highly obscured and that faint AGN are only minor contributors to cosmic reionization.}, author = {Matthee, Jorryt J and Naidu, Rohan P. and Brammer, Gabriel and Chisholm, John and Eilers, Anna-Christina and Goulding, Andy and Greene, Jenny and Kashino, Daichi and Labbe, Ivo and Lilly, Simon J. and Mackenzie, Ruari and Oesch, Pascal A. and Weibel, Andrea and Wuyts, Stijn and Xiao, Mengyuan and Bordoloi, Rongmon and Bouwens, Rychard and van Dokkum, Pieter and Illingworth, Garth and Kramarenko, Ivan and Maseda, Michael V. and Mason, Charlotte and Meyer, Romain A. and Nelson, Erica J. and Reddy, Naveen A. and Shivaei, Irene and Simcoe, Robert A. and Yue, Minghao}, issn = {1538-4357}, journal = {The Astrophysical Journal}, keywords = {Space and Planetary Science, Astronomy and Astrophysics}, number = {2}, publisher = {American Astronomical Society}, title = {{Little Red Dots: An abundant population of faint active galactic nuclei at z ∼ 5 revealed by the EIGER and FRESCO JWST surveys}}, doi = {10.3847/1538-4357/ad2345}, volume = {963}, year = {2024}, } @article{15179, abstract = {The fungal bioluminescence pathway can be reconstituted in other organisms allowing luminescence imaging without exogenously supplied substrate. The pathway starts from hispidin biosynthesis—a step catalyzed by a large fungal polyketide synthase that requires a posttranslational modification for activity. Here, we report identification of alternative compact hispidin synthases encoded by a phylogenetically diverse group of plants. A hybrid bioluminescence pathway that combines plant and fungal genes is more compact, not dependent on availability of machinery for posttranslational modifications, and confers autonomous bioluminescence in yeast, mammalian, and plant hosts. The compact size of plant hispidin synthases enables additional modes of delivery of autoluminescence, such as delivery with viral vectors.}, author = {Palkina, Kseniia A. and Karataeva, Tatiana A. and Perfilov, Maxim M. and Fakhranurova, Liliia I. and Markina, Nadezhda M. and Gonzalez Somermeyer, Louisa and Garcia-Perez, Elena and Vazquez-Vilar, Marta and Rodriguez-Rodriguez, Marta and Vazquez-Vilriales, Victor and Shakhova, Ekaterina S. and Mitiouchkina, Tatiana and Belozerova, Olga A. and Kovalchuk, Sergey I. and Alekberova, Anna and Malyshevskaia, Alena K. and Bugaeva, Evgenia N. and Guglya, Elena B. and Balakireva, Anastasia and Sytov, Nikita and Bezlikhotnova, Anastasia and Boldyreva, Daria I. and Babenko, Vladislav V. and Kondrashov, Fyodor and Choob, Vladimir V. and Orzaez, Diego and Yampolsky, Ilia V. and Mishin, Alexander S. and Sarkisyan, Karen S.}, issn = {2375-2548}, journal = {Science Advances}, number = {10}, publisher = {American Association for the Advancement of Science}, title = {{A hybrid pathway for self-sustained luminescence}}, doi = {10.1126/sciadv.adk1992}, volume = {10}, year = {2024}, } @article{15186, abstract = {The elimination of rain evaporation in the planetary boundary layer (PBL) has been found to lead to convective self‐aggregation (CSA) even without radiative feedback, but the precise mechanisms underlying this phenomenon remain unclear. We conducted cloud‐resolving simulations with two domain sizes and progressively reduced rain evaporation in the PBL. Surprisingly, CSA only occurred when rain evaporation was almost completely removed. The additional convective heating resulting from the reduction of evaporative cooling in the moist patch was found to be the trigger, thereafter a dry subsidence intrusion into the PBL in the dry patch takes over and sets CSA in motion. Temperature and moisture anomalies oppose each other in their buoyancy effects, hence explaining the need for almost total rain evaporation removal. We also found radiative cooling and not cold pools to be the leading cause for the comparative ease of CSA to take place in the larger domain.}, author = {Hwong, Yi-Ling and Muller, Caroline J}, issn = {1944-8007}, journal = {Geophysical Research Letters}, keywords = {General Earth and Planetary Sciences, Geophysics}, number = {6}, publisher = {American Geophysical Union}, title = {{The unreasonable efficiency of total rain evaporation removal in triggering convective self‐aggregation}}, doi = {10.1029/2023gl106523}, volume = {51}, year = {2024}, } @article{15181, abstract = {We demonstrate the failure of the adiabatic Born-Oppenheimer approximation to describe the ground state of a quantum impurity within an ultracold Fermi gas despite substantial mass differences between the bath and impurity species. Increasing repulsion leads to the appearance of nonadiabatic couplings between the fast bath and slow impurity degrees of freedom, which reduce the parity symmetry of the latter according to the pseudo Jahn-Teller effect. The presence of this mechanism is associated to a conical intersection involving the impurity position and the inverse of the interaction strength, which acts as a synthetic dimension. We elucidate the presence of these effects via a detailed ground-state analysis involving the comparison of ab initio fully correlated simulations with effective models. Our study suggests ultracold atomic ensembles as potent emulators of complex molecular phenomena.}, author = {Becker, A. and Koutentakis, Georgios and Schmelcher, P.}, issn = {2643-1564}, journal = {Physical Review Research}, number = {1}, publisher = {American Physical Society}, title = {{Synthetic dimension-induced pseudo Jahn-Teller effect in one-dimensional confined fermions}}, doi = {10.1103/physrevresearch.6.013257}, volume = {6}, year = {2024}, } @article{15182, abstract = {Thermoelectric materials convert heat into electricity, with a broad range of applications near room temperature (RT). However, the library of RT high-performance materials is limited. Traditional high-temperature synthetic methods constrain the range of materials achievable, hindering the ability to surpass crystal structure limitations and engineer defects. Here, a solution-based synthetic approach is introduced, enabling RT synthesis of powders and exploration of densification at lower temperatures to influence the material's microstructure. The approach is exemplified by Ag2Se, an n-type alternative to bismuth telluride. It is demonstrated that the concentration of Ag interstitials, grain boundaries, and dislocations are directly correlated to the sintering temperature, and achieve a figure of merit of 1.1 from RT to 100 °C after optimization. Moreover, insights into and resolve Ag2Se's challenges are provided, including stoichiometry issues leading to irreproducible performances. This work highlights the potential of RT solution synthesis in expanding the repertoire of high-performance thermoelectric materials for practical applications.}, author = {Kleinhanns, Tobias and Milillo, Francesco and Calcabrini, Mariano and Fiedler, Christine and Horta, Sharona and Balazs, Daniel and Strumolo, Marissa J. and Hasler, Roger and Llorca, Jordi and Tkadletz, Michael and Brutchey, Richard L. and Ibáñez, Maria}, issn = {1614-6840}, journal = {Advanced Energy Materials}, publisher = {Wiley}, title = {{A route to high thermoelectric performance: Solution‐based control of microstructure and composition in Ag2Se}}, doi = {10.1002/aenm.202400408}, year = {2024}, } @article{15165, abstract = {Current knowledge suggests a drought Indian monsoon (perhaps a severe one) when the El Nino Southern Oscillation and Pacific Decadal Oscillation each exhibit positive phases (a joint positive phase). For the monsoons, which are exceptions in this regard, we found northeast India often gets excess pre-monsoon rainfall. Further investigation reveals that this excess pre-monsoon rainfall is produced by the interaction of the large-scale circulation associated with the joint phase with the mountains in northeast India. We posit that a warmer troposphere, a consequence of excess rainfall over northeast India, drives a stronger monsoon circulation and enhances monsoon rainfall over central India. Hence, we argue that pre-monsoon rainfall over northeast India can be used for seasonal monsoon rainfall prediction over central India. Most importantly, its predictive value is at its peak when the Pacific Ocean exhibits a joint positive phase and the threat of extreme drought monsoon looms over India.}, author = {Goswami, Bidyut B}, issn = {1944-8007}, journal = {Geophysical Research Letters}, number = {5}, publisher = {Wiley}, title = {{A pre-monsoon signal of false alarms of Indian monsoon droughts}}, doi = {10.1029/2023GL106569}, volume = {51}, year = {2024}, } @article{15146, abstract = {The extracellular matrix (ECM) serves as a scaffold for cells and plays an essential role in regulating numerous cellular processes, including cell migration and proliferation. Due to limitations in specimen preparation for conventional room-temperature electron microscopy, we lack structural knowledge on how ECM components are secreted, remodeled, and interact with surrounding cells. We have developed a 3D-ECM platform compatible with sample thinning by cryo-focused ion beam milling, the lift-out extraction procedure, and cryo-electron tomography. Our workflow implements cell-derived matrices (CDMs) grown on EM grids, resulting in a versatile tool closely mimicking ECM environments. This allows us to visualize ECM for the first time in its hydrated, native context. Our data reveal an intricate network of extracellular fibers, their positioning relative to matrix-secreting cells, and previously unresolved structural entities. Our workflow and results add to the structural atlas of the ECM, providing novel insights into its secretion and assembly.}, author = {Zens, Bettina and Fäßler, Florian and Hansen, Jesse and Hauschild, Robert and Datler, Julia and Hodirnau, Victor-Valentin and Zheden, Vanessa and Alanko, Jonna H and Sixt, Michael K and Schur, Florian KM}, issn = {1540-8140}, journal = {Journal of Cell Biology}, number = {6}, publisher = {Rockefeller University Press}, title = {{Lift-out cryo-FIBSEM and cryo-ET reveal the ultrastructural landscape of extracellular matrix}}, doi = {10.1083/jcb.202309125}, volume = {223}, year = {2024}, } @article{14931, abstract = {We prove an upper bound on the ground state energy of the dilute spin-polarized Fermi gas capturing the leading correction to the kinetic energy resulting from repulsive interactions. One of the main ingredients in the proof is a rigorous implementation of the fermionic cluster expansion of Gaudin et al. (1971) [15].}, author = {Lauritsen, Asbjørn Bækgaard and Seiringer, Robert}, issn = {1096--0783}, journal = {Journal of Functional Analysis}, number = {7}, publisher = {Elsevier}, title = {{Ground state energy of the dilute spin-polarized Fermi gas: Upper bound via cluster expansion}}, doi = {10.1016/j.jfa.2024.110320}, volume = {286}, year = {2024}, } @inbook{12428, abstract = {The mammary gland consists of a bilayered epithelial structure with an extensively branched morphology. The majority of this epithelial tree is laid down during puberty, during which actively proliferating terminal end buds repeatedly elongate and bifurcate to form the basic structure of the ductal tree. Mammary ducts consist of a basal and luminal cell layer with a multitude of identified sub-lineages within both layers. The understanding of how these different cell lineages are cooperatively driving branching morphogenesis is a problem of crossing multiple scales, as this requires information on the macroscopic branched structure of the gland, as well as data on single-cell dynamics driving the morphogenic program. Here we describe a method to combine genetic lineage tracing with whole-gland branching analysis. Quantitative data on the global organ structure can be used to derive a model for mammary gland branching morphogenesis and provide a backbone on which the dynamics of individual cell lineages can be simulated and compared to lineage-tracing approaches. Eventually, these quantitative models and experiments allow to understand the couplings between the macroscopic shape of the mammary gland and the underlying single-cell dynamics driving branching morphogenesis.}, author = {Hannezo, Edouard B and Scheele, Colinda L.G.J.}, booktitle = {Cell Migration in Three Dimensions}, editor = {Margadant, Coert}, isbn = {9781071628867}, issn = {1940-6029}, pages = {183--205}, publisher = {Springer Nature}, title = {{A Guide Toward Multi-scale and Quantitative Branching Analysis in the Mammary Gland}}, doi = {10.1007/978-1-0716-2887-4_12}, volume = {2608}, year = {2023}, } @article{12534, abstract = {Brownian motion of a mobile impurity in a bath is affected by spin-orbit coupling (SOC). Here, we discuss a Caldeira-Leggett-type model that can be used to propose and interpret quantum simulators of this problem in cold Bose gases. First, we derive a master equation that describes the model and explore it in a one-dimensional (1D) setting. To validate the standard assumptions needed for our derivation, we analyze available experimental data without SOC; as a byproduct, this analysis suggests that the quench dynamics of the impurity is beyond the 1D Bose-polaron approach at temperatures currently accessible in a cold-atom laboratory—motion of the impurity is mainly driven by dissipation. For systems with SOC, we demonstrate that 1D spin-orbit coupling can be gauged out even in the presence of dissipation—the information about SOC is incorporated in the initial conditions. Observables sensitive to this information (such as spin densities) can be used to study formation of steady spin polarization domains during quench dynamics.}, author = {Ghazaryan, Areg and Cappellaro, Alberto and Lemeshko, Mikhail and Volosniev, Artem}, issn = {2643-1564}, journal = {Physical Review Research}, number = {1}, publisher = {American Physical Society}, title = {{Dissipative dynamics of an impurity with spin-orbit coupling}}, doi = {10.1103/physrevresearch.5.013029}, volume = {5}, year = {2023}, } @article{12158, abstract = {Post-translational histone modifications modulate chromatin activity to affect gene expression. How chromatin states underlie lineage choice in single cells is relatively unexplored. We develop sort-assisted single-cell chromatin immunocleavage (sortChIC) and map active (H3K4me1 and H3K4me3) and repressive (H3K27me3 and H3K9me3) histone modifications in the mouse bone marrow. During differentiation, hematopoietic stem and progenitor cells (HSPCs) acquire active chromatin states mediated by cell-type-specifying transcription factors, which are unique for each lineage. By contrast, most alterations in repressive marks during differentiation occur independent of the final cell type. Chromatin trajectory analysis shows that lineage choice at the chromatin level occurs at the progenitor stage. Joint profiling of H3K4me1 and H3K9me3 demonstrates that cell types within the myeloid lineage have distinct active chromatin but share similar myeloid-specific heterochromatin states. This implies a hierarchical regulation of chromatin during hematopoiesis: heterochromatin dynamics distinguish differentiation trajectories and lineages, while euchromatin dynamics reflect cell types within lineages.}, author = {Zeller, Peter and Yeung, Jake and Viñas Gaza, Helena and de Barbanson, Buys Anton and Bhardwaj, Vivek and Florescu, Maria and van der Linden, Reinier and van Oudenaarden, Alexander}, issn = {1546-1718}, journal = {Nature Genetics}, keywords = {Genetics}, pages = {333--345}, publisher = {Springer Nature}, title = {{Single-cell sortChIC identifies hierarchical chromatin dynamics during hematopoiesis}}, doi = {10.1038/s41588-022-01260-3}, volume = {55}, 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}, } @inproceedings{12735, abstract = {Asynchronous programming has gained significant popularity over the last decade: support for this programming pattern is available in many popular languages via libraries and native language implementations, typically in the form of coroutines or the async/await construct. Instead of programming via shared memory, this concept assumes implicit synchronization through message passing. The key data structure enabling such communication is the rendezvous channel. Roughly, a rendezvous channel is a blocking queue of size zero, so both send(e) and receive() operations wait for each other, performing a rendezvous when they meet. To optimize the message passing pattern, channels are usually equipped with a fixed-size buffer, so sends do not suspend and put elements into the buffer until its capacity is exceeded. This primitive is known as a buffered channel. This paper presents a fast and scalable algorithm for both rendezvous and buffered channels. Similarly to modern queues, our solution is based on an infinite array with two positional counters for send(e) and receive() operations, leveraging the unconditional Fetch-And-Add instruction to update them. Yet, the algorithm requires non-trivial modifications of this classic pattern, in order to support the full channel semantics, such as buffering and cancellation of waiting requests. We compare the performance of our solution to that of the Kotlin implementation, as well as against other academic proposals, showing up to 9.8× speedup. To showcase its expressiveness and performance, we also integrated the proposed algorithm into the standard Kotlin Coroutines library, replacing the previous channel implementations.}, author = {Koval, Nikita and Alistarh, Dan-Adrian and Elizarov, Roman}, booktitle = {Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming}, isbn = {9798400700156}, location = {Montreal, QC, Canada}, pages = {107--118}, publisher = {Association for Computing Machinery}, title = {{Fast and scalable channels in Kotlin Coroutines}}, doi = {10.1145/3572848.3577481}, year = {2023}, } @misc{12736, abstract = {Although a wide variety of handcrafted concurrent data structures have been proposed, there is considerable interest in universal approaches (Universal Constructions or UCs) for building concurrent data structures. UCs (semi-)automatically convert a sequential data structure into a concurrent one. The simplest approach uses locks [3, 6] that protect a sequential data structure and allow only one process to access it at a time. However, the resulting data structure is blocking. Most work on UCs instead focuses on obtaining non-blocking progress guarantees such as obstruction-freedom, lock-freedom or wait-freedom. Many non-blocking UCs have appeared. Key examples include the seminal wait-free UC [2] by Herlihy, a NUMA-aware UC [10] by Yi et al., and an efficient UC for large objects [1] by Fatourou et al.}, author = {Aksenov, Vitaly and Brown, Trevor A and Fedorov, Alexander and Kokorin, Ilya}, booktitle = {Proceedings of the ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming}, isbn = {9798400700156}, location = {Montreal, QB, Canada}, pages = {438--440}, publisher = {Association for Computing Machinery}, title = {{Unexpected scaling in path copying trees}}, doi = {10.1145/3572848.3577512}, year = {2023}, } @inproceedings{12760, abstract = {Dynamic programming (DP) is one of the fundamental paradigms in algorithm design. However, many DP algorithms have to fill in large DP tables, represented by two-dimensional arrays, which causes at least quadratic running times and space usages. This has led to the development of improved algorithms for special cases when the DPs satisfy additional properties like, e.g., the Monge property or total monotonicity. In this paper, we consider a new condition which assumes (among some other technical assumptions) that the rows of the DP table are monotone. Under this assumption, we introduce a novel data structure for computing (1 + ϵ)-approximate DP solutions in near-linear time and space in the static setting, and with polylogarithmic update times when the DP entries change dynamically. To the best of our knowledge, our new condition is incomparable to previous conditions and is the first which allows to derive dynamic algorithms based on existing DPs. Instead of using two-dimensional arrays to store the DP tables, we store the rows of the DP tables using monotone piecewise constant functions. This allows us to store length-n DP table rows with entries in [0, W] using only polylog(n, W) bits, and to perform operations, such as (min, +)-convolution or rounding, on these functions in polylogarithmic time. We further present several applications of our data structure. For bicriteria versions of k-balanced graph partitioning and simultaneous source location, we obtain the first dynamic algorithms with subpolynomial update times, as well as the first static algorithms using only near-linear time and space. Additionally, we obtain the currently fastest algorithm for fully dynamic knapsack.}, author = {Henzinger, Monika H and Neumann, Stefan and Räcke, Harald and Schmid, Stefan}, booktitle = {40th International Symposium on Theoretical Aspects of Computer Science}, isbn = {9783959772662}, issn = {1868-8969}, location = {Hamburg, Germany}, publisher = {Schloss Dagstuhl - Leibniz-Zentrum für Informatik}, title = {{Dynamic maintenance of monotone dynamic programs and applications}}, doi = {10.4230/LIPIcs.STACS.2023.36}, volume = {254}, year = {2023}, } @phdthesis{12716, abstract = {The process of detecting and evaluating sensory information to guide behaviour is termed perceptual decision-making (PDM), and is critical for the ability of an organism to interact with its external world. Individuals with autism, a neurodevelopmental condition primarily characterised by social and communication difficulties, frequently exhibit altered sensory processing and PDM difficulties are widely reported. Recent technological advancements have pushed forward our understanding of the genetic changes accompanying this condition, however our understanding of how these mutations affect the function of specific neuronal circuits and bring about the corresponding behavioural changes remains limited. Here, we use an innate PDM task, the looming avoidance response (LAR) paradigm, to identify a convergent behavioural abnormality across three molecularly distinct genetic mouse models of autism (Cul3, Setd5 and Ptchd1). Although mutant mice can rapidly detect threatening visual stimuli, their responses are consistently delayed, requiring longer to initiate an appropriate response than their wild-type siblings. Mutant animals show abnormal adaptation in both their stimulus- evoked escape responses and exploratory dynamics following repeated stimulus presentations. Similarly delayed behavioural responses are observed in wild-type animals when faced with more ambiguous threats, suggesting the mutant phenotype could arise from a dysfunction in the flexible control of this PDM process. Our knowledge of the core neuronal circuitry mediating the LAR facilitated a detailed dissection of the neuronal mechanisms underlying the behavioural impairment. In vivo extracellular recording revealed that visual responses were unaffected within a key brain region for the rapid processing of visual threats, the superior colliculus (SC), indicating that the behavioural delay was unlikely to originate from sensory impairments. Delayed behavioural responses were recapitulated in the Setd5 model following optogenetic stimulation of the excitatory output neurons of the SC, which are known to mediate escape initiation through the activation of cells in the underlying dorsal periaqueductal grey (dPAG). In vitro patch-clamp recordings of dPAG cells uncovered a stark hypoexcitability phenotype in two out of the three genetic models investigated (Setd5 and Ptchd1), that in Setd5, is mediated by the misregulation of voltage-gated potassium channels. Overall, our results show that the ability to use visual information to drive efficient escape responses is impaired in three diverse genetic mouse models of autism and that, in one of the models studied, this behavioural delay likely originates from differences in the intrinsic excitability of a key subcortical node, the dPAG. Furthermore, this work showcases the use of an innate behavioural paradigm to mechanistically dissect PDM processes in autism.}, author = {Burnett, Laura}, issn = {2663-337X}, pages = {178}, publisher = {Institute of Science and Technology Austria}, title = {{To flee, or not to flee? Using innate defensive behaviours to investigate rapid perceptual decision-making through subcortical circuits in mouse models of autism}}, doi = {10.15479/at:ista:12716}, year = {2023}, } @inproceedings{12854, abstract = {The main idea behind BUBAAK is to run multiple program analyses in parallel and use runtime monitoring and enforcement to observe and control their progress in real time. The analyses send information about (un)explored states of the program and discovered invariants to a monitor. The monitor processes the received data and can force an analysis to stop the search of certain program parts (which have already been analyzed by other analyses), or to make it utilize a program invariant found by another analysis. At SV-COMP 2023, the implementation of data exchange between the monitor and the analyses was not yet completed, which is why BUBAAK only ran several analyses in parallel, without any coordination. Still, BUBAAK won the meta-category FalsificationOverall and placed very well in several other (sub)-categories of the competition.}, author = {Chalupa, Marek and Henzinger, Thomas A}, booktitle = {Tools and Algorithms for the Construction and Analysis of Systems}, isbn = {9783031308192}, issn = {1611-3349}, location = {Paris, France}, pages = {535--540}, publisher = {Springer Nature}, title = {{Bubaak: Runtime monitoring of program verifiers}}, doi = {10.1007/978-3-031-30820-8_32}, volume = {13994}, year = {2023}, }