Search

We initiate the study of deterministic distributed graph algorithms with predictions in synchronous message passing systems. The process at each node in the graph is given a prediction, which is some extra information about the problem instance that may be incorrect. The processes may use the predictions to help them solve the problem. The overall goal is to develop algorithms that both work faster when predictions are good and do not work much worse than algorithms without predictions when predictions are bad. Concepts from the more general area of algorithms with predictions, such as error measures, consistency, robustness, and smoothness, are adapted to distributed graph algorithms with predictions. We consider algorithms with predictions for four distributed graph problems, Maximal Independent Set, Maximal Matching, $(\Delta+1)$-Vertex Coloring, and $(2\Delta-1)$-Edge Coloring, where $\Delta$ denotes the degree of the graph. For each, we define an appropriate error measure. We present generic templates that can be used to design deterministic distributed graph algorithms with predictions from existing algorithms without predictions. Using these templates, we develop algorithms with predictions for Maximal Independent Set. Alternative error measures for the Maximal Independent Set problem are also considered. We obtain algorithms with predictions for general graphs and for rooted trees and analyze them using two of these error measures., Comment: 27 pages, 2 figures, 6 algorithms

Deep surveys reveal tidal debris and associated compact stellar systems. Euclid's unique combination of capabilities (spatial resolution, depth, and wide sky coverage) will make it a groundbreaking tool for galactic archaeology in the local Universe, bringing low surface brightness (LSB) science into the era of large-scale astronomical surveys. Euclid's Early Release Observations (ERO) demonstrate this potential with a field of view that includes several galaxies in the Dorado group. In this paper, we aim to derive from this image a mass assembly scenario for its main galaxies: NGC 1549, NGC 1553, and NGC 1546. We detect internal and external diffuse structures, and identify candidate globular clusters (GCs). By analysing the colours and distributions of the diffuse structures and candidate GCs, we can place constraints on the galaxies' mass assembly and merger histories. The results show that feature morphology, surface brightness, colours, and GC density profiles are consistent with galaxies that have undergone different merger scenarios. We classify NGC 1549 as a pure elliptical galaxy that has undergone a major merger. NGC 1553 appears to have recently transitioned from a late-type galaxy to early type, after a series of radial minor to intermediate mergers. NGC 1546 is a rare specimen of galaxy with an undisturbed disk and a prominent diffuse stellar halo, which we infer has been fed by minor mergers and then disturbed by the tidal effect from NGC 1553. Finally, we identify limitations specific to the observing conditions of this ERO, in particular stray light in the visible and persistence in the near-infrared bands. Once these issues are addressed and the extended emission from LSB objects is preserved by the data-processing pipeline, the Euclid Wide Survey will allow studies of the local Universe to be extended to statistical ensembles over a large part of the extragalactic sky., Comment: 25 pages, 20 figures

The instruments at the focus of the Euclid space observatory offer superb, diffraction-limited imaging over an unprecedented (from space) wide field of view of 0.57 deg$^2$. This exquisite image quality has the potential to produce high-precision astrometry for point sources once the undersampling of Euclid's cameras is taken into account by means of accurate, effective point spread function (ePSF) modelling. We present a complex, detailed workflow to simultaneously solve for the geometric distortion (GD) and model the undersampled ePSFs of the Euclid detectors. Our procedure was successfully developed and tested with data from the Early Release Observations (ERO) programme focused on the nearby globular cluster NGC 6397. Our final one-dimensional astrometric precision for a well-measured star just below saturation is 0.7 mas (0.007 pixel) for the Visible Instrument (VIS) and 3 mas (0.01 pixel) for the Near-Infrared Spectrometer and Photometer (NISP). Finally, we present a specific scientific application of this high-precision astrometry: the combination of Euclid and Gaia data to compute proper motions and study the internal kinematics of NGC 6397. Future work, when more data become available, will allow for a better characterisation of the ePSFs and GD corrections that are derived here, along with assessment of their temporal stability, and their dependencies on the spectral energy distribution of the sources as seen through the wide-band filters of Euclid., Comment: 23 pages, 21 figures. Accepted for publication in A&A on October 24, 2024. Astro-photometric catalogs and stacked images will be available at the CDS after the paper will be published

We study simplicity of $C^*$-algebras arising from self-similar groups of $\mathbb{Z}_2$-multispinal type, a generalization of the Grigorchuk case whose simplicity was first proved by L. Clark, R. Exel, E. Pardo, C. Starling, and A. Sims in 2019, and we prove results generalizing theirs. Our first main result is a sufficient condition for simplicity of the Steinberg algebra satisfying conditions modeled on the behavior of the groupoid associated to the first Grigorchuk group. This closely resembles conditions found by B. Steinberg and N. Szak\'acs. As a key ingredient we identify an infinite family of $2-(2q-1,q-1,q/2-1)$-designs, where $q$ is a positive even integer. We then deduce the simplicity of the associated $C^*$-algebra, which is our second main result. Results of similar type were considered by B. Steinberg and N. Szak\'acs in 2021, and later by K. Yoshida, but their methods did not follow the original methods of the five authors.

With the developments in machine learning, there has been a surge in interest and results focused on algorithms utilizing predictions, not least in online algorithms where most new results incorporate the prediction aspect for concrete online problems. While the structural computational hardness of problems with regards to time and space is quite well developed, not much is known about online problems where time and space resources are typically not in focus. Some information-theoretical insights were gained when researchers considered online algorithms with oracle advice, but predictions of uncertain quality is a very different matter. We initiate the development of a complexity theory for online problems with predictions, focusing on binary predictions for minimization problems. Based on the most generic hard online problem type, string guessing, we define a hierarchy of complexity classes and develop notions of reductions, class membership, hardness, and completeness. Our framework contains all the tools one expects to find when working with complexity, and we illustrate our tools by analyzing problems with different characteristics. Our work also implies the same results for classic online problems without predictions.

Extragalactic globular clusters (EGCs) are an abundant and powerful tracer of galaxy dynamics and formation, and their own formation and evolution is also a matter of extensive debate. The compact nature of globular clusters means that they are hard to spatially resolve and thus study outside the Local Group. In this work we have examined how well EGCs will be detectable in images from the Euclid telescope, using both simulated pre-launch images and the first early-release observations of the Fornax galaxy cluster. The Euclid Wide Survey will provide high-spatial resolution VIS imaging in the broad IE band as well as near-infrared photometry (YE, JE, and HE). We estimate that the galaxies within 100 Mpc in the footprint of the Euclid survey host around 830 000 EGCs of which about 350 000 are within the survey's detection limits. For about half of these EGCs, three infrared colours will be available as well. For any galaxy within 50Mpc the brighter half of its GC luminosity function will be detectable by the Euclid Wide Survey. The detectability of EGCs is mainly driven by the residual surface brightness of their host galaxy. We find that an automated machine-learning EGC-classification method based on real Euclid data of the Fornax galaxy cluster provides an efficient method to generate high purity and high completeness GC candidate catalogues. We confirm that EGCs are spatially resolved compared to pure point sources in VIS images of Fornax. Our analysis of both simulated and first on-sky data show that Euclid will increase the number of GCs accessible with high-resolution imaging substantially compared to previous surveys, and will permit the study of GCs in the outskirts of their hosts. Euclid is unique in enabling systematic studies of EGCs in a spatially unbiased and homogeneous manner and is primed to improve our understanding of many understudied aspects of GC astrophysics., Comment: Accepted in A&A

We present an analysis of Euclid observations of a 0.5 deg$^2$ field in the central region of the Fornax galaxy cluster that were acquired during the performance verification phase. With these data, we investigate the potential of Euclid for identifying GCs at 20 Mpc, and validate the search methods using artificial GCs and known GCs within the field from the literature. Our analysis of artificial GCs injected into the data shows that Euclid's data in $I_{\rm E}$ band is 80% complete at about $I_{\rm E} \sim 26.0$ mag ($M_{V\rm } \sim -5.0$ mag), and resolves GCs as small as $r_{\rm h} = 2.5$ pc. In the $I_{\rm E}$ band, we detect more than 95% of the known GCs from previous spectroscopic surveys and GC candidates of the ACS Fornax Cluster Survey, of which more than 80% are resolved. We identify more than 5000 new GC candidates within the field of view down to $I_{\rm E}$ mag, about 1.5 mag fainter than the typical GC luminosity function turn-over magnitude, and investigate their spatial distribution within the intracluster field. We then focus on the GC candidates around dwarf galaxies and investigate their numbers, stacked luminosity distribution and stacked radial distribution. While the overall GC properties are consistent with those in the literature, an interesting over-representation of relatively bright candidates is found within a small number of relatively GC-rich dwarf galaxies. Our work confirms the capabilities of Euclid data in detecting GCs and separating them from foreground and background contaminants at a distance of 20 Mpc, particularly for low-GC count systems such as dwarf galaxies., Comment: Paper submitted as part of the A&A special issue `Euclid on Sky', which contains Euclid key reference papers and first results from the Euclid Early Release Observations

Euclid is poised to make significant advances in the study of nearby galaxies in the local Universe. Here we present a first look at 6 galaxies observed for the Nearby Galaxy Showcase as part of the Euclid Early Release Observations acquired between August and November, 2023. These targets, 3 dwarf galaxies (HolmbergII, IC10, NGC6822) and 3 spirals (IC342, NGC2403, NGC6744), range in distance from about 0.5 Mpc to 8.8 Mpc. Our assessment of the surface brightness depths in the stacked Euclid images confirms previous estimates in 100 arcsec^2 regions of 1sigma=30.5 mag/arcsec^2 for VIS, but slightly deeper than previous estimates for NISP with 1sigma=29.2-29.4 mag/arcsec^2. By combining Euclid HE, YE, and IE into RGB images, we illustrate the large field-of-view covered by a single Reference Observing Sequence, together with exquisite detail on parsec scales in these nearby galaxies. Radial surface brightness and color profiles demonstrate galaxy colors in agreement with stellar population synthesis models. Standard stellar photometry selection techniques find approximately 1.3 million stars across the 6 galaxy fields. Euclid's resolved stellar photometry allows us to constrain the star-formation histories of these galaxies, by disentangling the distributions of young stars, as well as asymptotic giant branch and red giant branch stellar populations. We finally examine 2 galaxies individually for surrounding satellite systems. Our analysis of the ensemble of dwarf satellites around NGC6744 reveals a new galaxy, EDwC1, a nucleated dwarf spheroidal at the end of a spiral arm. Our new census of the globular clusters around NGC2403 yields 9 new star-cluster candidates, 8 of which with colors indicative of evolved stellar populations. In summary, our investigation of the 6 Showcase galaxies demonstrates that Euclid is a powerful probe of the anatomy of nearby galaxies [abridged]., Comment: 36 pages; 20 figures in main text; 4 Appendices. Submitted to A&A, as part of the A&A special issue `Euclid on Sky', which contains Euclid key reference papers and first results from the Euclid Early Release Observations

As part of the Euclid Early Release Observations (ERO) programme, we analyse deep, wide-field imaging from the VIS and NISP instruments of two Milky Way globular clusters (GCs), namely NGC 6254 (M10) and NGC 6397, to look for observational evidence of their dynamical interaction with the Milky Way. We search for such an interaction in the form of structural and morphological features in the clusters' outermost regions, which are suggestive of the development of tidal tails on scales larger than those sampled by the ERO programme. Our multi-band photometric analysis results in deep and well-behaved colour-magnitude diagrams that, in turn, enable an accurate membership selection. The surface brightness profiles built from these samples of member stars are the deepest ever obtained for these two Milky Way GCs, reaching down to $\sim30.0$ mag~arcsec$^{-2}$, which is about $1.5$ mag arcsec$^{-2}$ below the current limit. The investigation of the two-dimensional density map of NGC 6254 reveals an elongated morphology of the cluster peripheries in the direction and with the amplitude predicted by $N$-body simulations of the cluster's dynamical evolution, at high statistical significance. We interpret this as strong evidence for the first detection of tidally induced morphological distortion around this cluster. The density map of NGC 6397 reveals a slightly elliptical morphology, in agreement with previous studies, which requires further investigation on larger scales to be properly interpreted. This ERO project thus demonstrates the power of Euclid in studying the outer regions of GCs at an unprecedented level of detail, thanks to the combination of large field of view, high spatial resolution, and depth enabled by the telescope. Our results highlight the future Euclid survey as the ideal data set to investigate GC tidal tails and stellar streams., Comment: 15 pages, 18 figures. Paper accepted as part of the A&A special issue `Euclid on Sky', which contains Euclid key reference papers and first results from the Euclid Early Release Observations

The Euclid ERO showcase Euclid's capabilities in advance of its main mission, targeting 17 astronomical objects, from galaxy clusters, nearby galaxies, globular clusters, to star-forming regions. A total of 24 hours observing time was allocated in the early months of operation, engaging the scientific community through an early public data release. We describe the development of the ERO pipeline to create visually compelling images while simultaneously meeting the scientific demands within months of launch, leveraging a pragmatic, data-driven development strategy. The pipeline's key requirements are to preserve the image quality and to provide flux calibration and photometry for compact and extended sources. The pipeline's five pillars are: removal of instrumental signatures; astrometric calibration; photometric calibration; image stacking; and the production of science-ready catalogues for both the VIS and NISP instruments. We report a PSF with a full width at half maximum of 0.16" in the optical and 0.49" in the three NIR bands. Our VIS mean absolute flux calibration is accurate to about 1%, and 10% for NISP due to a limited calibration set; both instruments have considerable colour terms. The median depth is 25.3 and 23.2 AB mag with a SNR of 10 for galaxies, and 27.1 and 24.5 AB mag at an SNR of 5 for point sources for VIS and NISP, respectively. Euclid's ability to observe diffuse emission is exceptional due to its extended PSF nearly matching a pure diffraction halo, the best ever achieved by a wide-field, high-resolution imaging telescope. Euclid offers unparalleled capabilities for exploring the LSB Universe across all scales, also opening a new observational window in the NIR. Median surface-brightness levels of 29.9 and 28.3 AB mag per square arcsec are achieved for VIS and NISP, respectively, for detecting a 10 arcsec x 10 arcsec extended feature at the 1 sigma level., Comment: Submitted to A&A, 44 pages, 36 figures - Part of the A&A special issue `Euclid on Sky', which contains Euclid key reference papers and first results from the Euclid Early Release Observations

The current standard model of cosmology successfully describes a variety of measurements, but the nature of its main ingredients, dark matter and dark energy, remains unknown. Euclid is a medium-class mission in the Cosmic Vision 2015-2025 programme of the European Space Agency (ESA) that will provide high-resolution optical imaging, as well as near-infrared imaging and spectroscopy, over about 14,000 deg^2 of extragalactic sky. In addition to accurate weak lensing and clustering measurements that probe structure formation over half of the age of the Universe, its primary probes for cosmology, these exquisite data will enable a wide range of science. This paper provides a high-level overview of the mission, summarising the survey characteristics, the various data-processing steps, and data products. We also highlight the main science objectives and expected performance., Comment: Accepted for publication in the A&A special issue`Euclid on Sky'

The chemical composition of globular clusters (GCs) across the Local Group provides information on chemical abundance trends. The host galaxy, Sextans A, is a low-surface-brightness dwarf irregular galaxy located on the edge of the Local Group.We derive the dynamical mass of the GC together with the mass-to-light ratio and the abundances of the ${\alpha}$ (Mg, Ca, Ti, Si), Fe-peak (Fe, Cr, Mn, Sc, Ni), and heavy elements (Ba, Cu, Zn, Eu). Abundance ratios were determined from the analysis of an optical integrated-light spectrum of Sextans A GC-1, obtained with UVES on the VLT. We apply non-local thermodynamic equilibrium (NLTE) corrections to Mg, Ca, Ti, Fe, and Ni. The GC appears to be younger and more metal-poor than the majority of the GCs of the Milky Way, with an age of 8.6$\pm$2.7 Gyr and $\text{[Fe/H]}=-2.14\pm0.04$ dex. The calculated dynamical mass is $(5.18 \pm1.62) \times 10^5 M_{\odot}$, which results in an atypically high value of the mass-to-light ratio, 4.35$\pm$1.40 M$_{\odot}$/L$_{V \odot}$. Sextans A GC-1 has varying $\alpha$ elements - the Mg abundance is extremely low ($\text{[Mg/Fe]}=-0.79\pm0.29$), Ca and Ti are solar-scaled or mildly enhanced, and Si is enhanced. This makes the mean $\alpha$ abundance (excluding Mg) to be enhanced. The Fe-peak elements are consistent with scaled-solar or slightly enhanced abundances. Ba and Cu have sub-solar abundance ratios, while Zn and Eu are consistent with their upper limits being solar-scaled and enhanced. The composition of Sextans A GC-1 resembles the overall pattern and behaviour of GCs in the Local Group. The anomalous values are the mass-to-light ratio and the depleted abundance of Mg. There is no definite explanation for such an extreme abundance value. Variations in the initial mass function or the presence of an intermediate-mass black hole might explain the high mass-to-light ratio value., Comment: 14 pages, 8 figures

In online interval scheduling, the input is an online sequence of intervals, and the goal is to accept a maximum number of non-overlapping intervals. In the more general disjoint path allocation problem, the input is a sequence of requests, each involving a pair of vertices of a known graph, and the goal is to accept a maximum number of requests forming edge-disjoint paths between accepted pairs. These problems have been studied under extreme settings without information about the input or with error-free advice. We study an intermediate setting with a potentially erroneous prediction that specifies the set of intervals/requests forming the input sequence. For both problems, we provide tight upper and lower bounds on the competitive ratios of online algorithms as a function of the prediction error. For disjoint path allocation, our results rule out the possibility of obtaining a better competitive ratio than that of a simple algorithm that fully trusts predictions, whereas, for interval scheduling, we develop a superior algorithm. We also present asymptotically tight trade-offs between consistency (competitive ratio with error-free predictions) and robustness (competitive ratio with adversarial predictions) of interval scheduling algorithms. Finally, we provide experimental results on real-world scheduling workloads that confirm our theoretical analysis.

We consider the minimum spanning tree problem with predictions, using the weight-arrival model, i.e., the graph is given, together with predictions for the weights of all edges. Then the actual weights arrive one at a time and an irrevocable decision must be made regarding whether or not the edge should be included into the spanning tree. In order to assess the quality of our algorithms, we define an appropriate error measure and analyze the performance of the algorithms as a function of the error. We prove that, according to competitive analysis, the simplest algorithm, Follow-the-Predictions, is optimal. However, intuitively, one should be able to do better, and we present a greedy variant of Follow-the-Predictions. In analyzing that algorithm, we believe we present the first random order analysis of a non-trivial online algorithm with predictions, by which we obtain an algorithmic separation. This may be useful for distinguishing between algorithms for other problems when Follow-the-Predictions is optimal according to competitive analysis.

Quotable signature schemes are digital signature schemes with the additional property that from the signature for a message, any party can extract signatures for (allowable) quotes from the message, without knowing the secret key or interacting with the signer of the original message. Crucially, the extracted signatures are still signed with the original secret key. We define a notion of security for quotable signature schemes and construct a concrete example of a quotable signature scheme, using Merkle trees and classical digital signature schemes. The scheme is shown to be secure, with respect to the aforementioned notion of security. Additionally, we prove bounds on the complexity of the constructed scheme and provide algorithms for signing, quoting, and verifying. Finally, concrete use cases of quotable signatures are considered, using them to combat misinformation by bolstering authentic content on social media. We consider both how quotable signatures can be used, and why using them could help mitigate the effects of fake news., Comment: 25 pages, 7 figures

In this paper we construct odd finitely summable spectral triples based on length functions of bounded doubling on noncommutative solenoids. Our spectral triples induce a Leibniz Lip-norm on the state spaces of the noncommutative solenoids, giving them the structure of Leibniz quantum compact metric spaces. By applying methods of R. Floricel and A. Ghorbanpour, we also show that our odd spectral triples on noncommutative solenoids can be considered as direct limits of spectral triples on rotation algebras. In the final section we prove a noncommutative Wiener's lemma and show that our odd spectral triples can be defined to have an associated smooth dense subalgebra which is stable under the holomorphic functional calculus, thus answering a question of B. Long and W. Wu. The construction of the smooth subalgebra also extends to the case of nilpotent discrete groups.

WEAVE, the new wide-field, massively multiplexed spectroscopic survey facility for the William Herschel Telescope, will see first light in late 2022. WEAVE comprises a new 2-degree field-of-view prime-focus corrector system, a nearly 1000-multiplex fibre positioner, 20 individually deployable 'mini' integral field units (IFUs), and a single large IFU. These fibre systems feed a dual-beam spectrograph covering the wavelength range 366$-$959\,nm at $R\sim5000$, or two shorter ranges at $R\sim20\,000$. After summarising the design and implementation of WEAVE and its data systems, we present the organisation, science drivers and design of a five- to seven-year programme of eight individual surveys to: (i) study our Galaxy's origins by completing Gaia's phase-space information, providing metallicities to its limiting magnitude for $\sim$3 million stars and detailed abundances for $\sim1.5$ million brighter field and open-cluster stars; (ii) survey $\sim0.4$ million Galactic-plane OBA stars, young stellar objects and nearby gas to understand the evolution of young stars and their environments; (iii) perform an extensive spectral survey of white dwarfs; (iv) survey $\sim400$ neutral-hydrogen-selected galaxies with the IFUs; (v) study properties and kinematics of stellar populations and ionised gas in $z<0.5$ cluster galaxies; (vi) survey stellar populations and kinematics in $\sim25\,000$ field galaxies at $0.3\lesssim z \lesssim 0.7$; (vii) study the cosmic evolution of accretion and star formation using $>1$ million spectra of LOFAR-selected radio sources; (viii) trace structures using intergalactic/circumgalactic gas at $z>2$. Finally, we describe the WEAVE Operational Rehearsals using the WEAVE Simulator., Comment: 41 pages, 27 figures, accepted for publication by MNRAS; updated version including information on individual grants in a revised Acknowledgements section, corrections to the affiliation list, and an updated references list

We prove a version of the result in the title that makes use of maximal coactions in the context of discrete groups. Earlier Gauge-Invariant Uniqueness theorems for $C^*$-algebras associated to $P$-graphs and similar $C^*$-algebras exploited a property of coactions known as normality. In the present paper, the view point is that maximal coactions provide a more natural starting point to state and prove such uniqueness theorems. A byproduct of our approach consists of an abstract characterization of co-universal representations for a Fell bundle over a discrete group., Comment: 11 pages

Young star clusters enable us to study the effects of stellar rotation on an ensemble of stars of the same age and across a wide range in stellar mass and are therefore ideal targets for understanding the consequences of rotation on stellar evolution. We combine MUSE spectroscopy with HST photometry to measure the projected rotational velocities (Vsini) of 2,184 stars along the split main sequence and on the main sequence turn-off (MSTO) of the 100 Myr-old massive (10^5 M_sun) star cluster NGC 1850 in the Large Magellanic Cloud. At fixed magnitude, we observe a clear correlation between Vsini and colour, in the sense that fast rotators appear redder. The average Vsini values for stars on the blue and red branches of the split main sequence are ~100 km/s and ~200 km/s, respectively. The values correspond to about 25-30% and 50-60% of the critical rotation velocity and imply that rotation rates comparable to those observed in field stars of similar masses can explain the split main sequence. Our spectroscopic sample contains a rich population of ~200 fast rotating Be stars. The presence of shell features suggests that 23% of them are observed through their decretion disks, corresponding to a disk opening angle of 15 degrees. These shell stars can significantly alter the shape of the MSTO, hence care should be taken when interpreting this photometric feature. Overall, our findings impact our understanding of the evolution of young massive clusters and provide new observational constraints for testing stellar evolutionary models., Comment: Published in MNRAS; 16 pages, 11 figures; data available via https://cdsarc.cds.unistra.fr/viz-bin/cat/J/MNRAS/518/1505#/article

The classical globular clusters found in all galaxy types have half-light radii of $r_{\rm h} \sim$ 2-4 pc, which have been tied to formation in the dense cores of giant molecular clouds. Some old star clusters have larger sizes, and it is unclear if these represent a fundamentally different mode of low-density star cluster formation. We report the discovery of a rare, young "faint fuzzy" star cluster, NGC 247-SC1, on the outskirts of the low-mass spiral galaxy NGC 247 in the nearby Sculptor group, and measure its radial velocity using Keck spectroscopy. We use Hubble Space Telescope imaging to measure the cluster half-light radius of $r_{\rm h} \simeq 12$ pc and a luminosity of $L_V \simeq 4\times10^5 \mathrm{L}_\odot$. We produce a colour-magnitude diagram of cluster stars and compare to theoretical isochrones, finding an age of $\simeq$ 300 Myr, a metallicity of [$Z$/H] $\sim -0.6$ and an inferred mass of $M_\star \simeq 9\times10^4 \mathrm{M}_\odot$. The narrow width of blue-loop star magnitudes implies an age spread of $\lesssim$ 50 Myr, while no old red-giant branch stars are found, so SC1 is consistent with hosting a single stellar population, modulo several unexplained bright "red straggler" stars. SC1 appears to be surrounded by tidal debris, at the end of a $\sim$ 2 kpc long stellar filament that also hosts two low-mass, low-density clusters of a similar age. We explore a link between the formation of these unusual clusters and an external perturbation of their host galaxy, illuminating a possible channel by which some clusters are born with large sizes., Comment: 19 pages, 10 figures, Mon. Not. R. Astron. Soc., in press

Paging is a prototypical problem in the area of online algorithms. It has also played a central role in the development of learning-augmented algorithms -- a recent line of research that aims to ameliorate the shortcomings of classical worst-case analysis by giving algorithms access to predictions. Such predictions can typically be generated using a machine learning approach, but they are inherently imperfect. Previous work on learning-augmented paging has investigated predictions on (i) when the current page will be requested again (reoccurrence predictions), (ii) the current state of the cache in an optimal algorithm (state predictions), (iii) all requests until the current page gets requested again, and (iv) the relative order in which pages are requested. We study learning-augmented paging from the new perspective of requiring the least possible amount of predicted information. More specifically, the predictions obtained alongside each page request are limited to one bit only. We consider two natural such setups: (i) discard predictions, in which the predicted bit denotes whether or not it is ``safe'' to evict this page, and (ii) phase predictions, where the bit denotes whether the current page will be requested in the next phase (for an appropriate partitioning of the input into phases). We develop algorithms for each of the two setups that satisfy all three desirable properties of learning-augmented algorithms -- that is, they are consistent, robust and smooth -- despite being limited to a one-bit prediction per request. We also present lower bounds establishing that our algorithms are essentially best possible.

We present a detailed chemical abundance analysis of the young massive cluster (YMC) NGC 1569-B. The host galaxy, NGC~1569, is a dwarf irregular starburst galaxy at a distance of 3.36$\pm$0.20 Mpc. We determined the abundance ratios from the analysis of an optical integrated-light spectrum of NGC 1569-B, obtained with the HIRES echelle spectrograph on the Keck I telescope. We considered different red-to-blue supergiant ratios, namely: the ratio obtained from a theoretical isochrone, the ratio obtained from a resolved colour-magnitude diagram of the YMC, and the ratio that minimises the $\chi^2$ when comparing our model spectra with the observations. We adopted the latter ratio for our resulting chemical abundances. The derived iron abundance is sub-solar with [Fe/H] = $-0.74\pm0.05$. In relation to the scaled solar composition, we find enhanced $\alpha$-element abundances, $\text{[/Fe]}=+0.25\pm$0.11, with a particularly high Ti abundance of +0.49$\pm$0.05. Other super-solar elements include $\text{[Cr/Fe]}=+0.50\pm$0.11, $\text{[Sc/Fe]}=+0.78\pm$0.20, and $\text{[Ba/Fe]}=+1.28\pm$0.14, while other Fe-peak elements are close to scaled solar abundances: ($\text{[Mn/Fe]}=-0.22\pm$0.12 and $\text{[Ni/Fe]}=+0.13\pm$0.11). The composition of NGC 1569-B resembles the stellar populations of the YMC NGC 1705-1, located in a blue compact dwarf galaxy. The two YMCs agree with regard to $\alpha$-elements and the majority of the Fe-peak elements, except for Sc and Ba, which are extremely super-solar in NGC~1569-B -- and higher than in any YMC studied so far. The blue part of the optical spectrum of a young population is still a very challenging wavelength region to analyse using IL spectroscopic studies. This is due to the uncertain contribution to the light from blue supergiant stars, which can be difficult to disentangle from turn-off stars, even when resolved photometry is available., Comment: 18 pages, 9 figures. Accepted for publication in A&A

We generalise recent results of Afsar, Larsen and Neshveyev for product systems over quasi-lattice orders by showing that the equilibrium states of quasi-free dynamics on the Nica-Toeplitz $C^*$-algebras of product systems over right LCM monoids must satisfy a positivity condition encoded in a system of inequalities satisfied by their restrictions to the coefficient algebra. We prove that the reduction of this positivity condition to a finite subset of inequalities is valid for a wider class of monoids that properly includes finite-type Artin monoids, answering a question left open in their work. Our main technical tool is a combinatorially generated tree modelled on a recent construction developed by Boyu Li for dilations of contractive representations. We also obtain a reduction of the positivity condition to inequalities arising from a certain minimal subset that may not be finite but has the advantage of holding for all Noetherian right LCM monoids, and we present an example, arising from a finite-type Artin monoid, that exhibits a gap in its inverse temperature space., Comment: Version with a correction to Corollary 6.3 and some minor changes

Choreographies are global descriptions of interactions among concurrent components, most notably used in the settings of verification and synthesis of correct-by-construction software. They require a top-down approach: programmers first write choreographies, and then use them to verify or synthesize their programs. However, most software does not come with choreographies yet, which prevents their application. To attack this problem, previous work investigated choreography extraction, which automatically constructs a choreography that describes the behaviour of a given set of programs or protocol specifications. We propose a new extraction methodology that improves on the state of the art: we can deal with programs that are equipped with state and internal computation and time complexity is dramatically better. We also implement this theory and show that, in spite of its theoretical exponential complexity, it is usable in practice. We discuss the data structures needed for an efficient implementation, introduce some optimisations, and perform a systematic practical evaluation., Comment: arXiv admin note: text overlap with arXiv:1910.11741

A variant of the online knapsack problem is considered in the settings of trusted and untrusted predictions. In Unit Profit Knapsack, the items have unit profit, and it is easy to find an optimal solution offline: Pack as many of the smallest items as possible into the knapsack. For Online Unit Profit Knapsack, the competitive ratio is unbounded. In contrast, previous work on online algorithms with untrusted predictions generally studied problems where an online algorithm with a constant competitive ratio is known. The prediction, possibly obtained from a machine learning source, that our algorithm uses is the average size of those smallest items that fit in the knapsack. For the prediction error in this hard online problem, we use the ratio $r=\frac{a}{\hat{a}}$ where $a$ is the actual value for this average size and $\hat{a}$ is the prediction. The algorithm presented achieves a competitive ratio of $\frac{1}{2r}$ for $r\geq 1$ and $\frac{r}{2}$ for $r\leq 1$. Using an adversary technique, we show that this is optimal in some sense, giving a trade-off in the competitive ratio attainable for different values of $r$. Note that the result for accurate advice, $r=1$, is only $\frac{1}{2}$, but we show that no algorithm knowing the value $a$ can achieve a competitive ratio better than $\frac{e-1}{e}\approx 0.6321$ and present an algorithm with a matching upper bound. We also show that this latter algorithm attains a competitive ratio of $r\frac{e-1}{e}$ for $r \leq 1$ and $\frac{e-r}{e}$ for $1 \leq r < e$, and no algorithm can be better for both $r<1$ and $1\leq r

This report is the result of a joint discussion between the Rubin and Euclid scientific communities. The work presented in this report was focused on designing and recommending an initial set of Derived Data products (DDPs) that could realize the science goals enabled by joint processing. All interested Rubin and Euclid data rights holders were invited to contribute via an online discussion forum and a series of virtual meetings. Strong interest in enhancing science with joint DDPs emerged from across a wide range of astrophysical domains: Solar System, the Galaxy, the Local Volume, from the nearby to the primaeval Universe, and cosmology., Comment: Report of the Rubin-Euclid Derived Data Products Working Group, 78 pages, 11 figures

We present detailed abundance measurements for 45 globular clusters (GCs) in galaxies in (and, in one case, beyond) the Local Group. The measurements are based on new high-resolution integrated-light spectra of GCs in NGC 185, NGC 205, M31, M33, and NGC 2403, combined with reanalysis of previous observations of GCs in the Fornax dSph, WLM, NGC 147, NGC 6822, and the Milky Way. The GCs cover the range -2.8 < [Fe/H] < -0.1 and we determined abundances for Fe, Na, Mg, Si, Ca, Sc, Ti, Cr, Mn, Ni, Cu, Zn, Zr, Ba, and Eu. Corrections for non local thermodynamic equilibrium effects are included for Na, Mg, Ca, Ti, Mn, Fe, Ni, and Ba. For several of the galaxies, our measurements provide the first quantitative constraints on the detailed composition of their metal-poor stellar populations. Overall, the GCs in different galaxies exhibit remarkably uniform abundance patterns of the alpha-, iron-peak, and neutron-capture elements, with a dispersion of less than 0.1 dex in [alpha/Fe] for the full sample. There is a hint that GCs in dwarf galaxies are slightly less alpha-enhanced (by about 0.04 dex on average) than those in larger galaxies. One GC in M33 (HM33-B) resembles the most metal-rich GCs in the Fornax dSph (Fornax 4) and NGC 6822 (SC7) by having alpha-element abundances closer to scaled-solar values, possibly hinting at an accretion origin. We find that the alpha-element abundances strongly correlate with those of Na, Sc, Ni, and Zn. Several GCs with [Fe/H]<-1.5 are deficient in Mg compared to other alpha-elements. We find no GCs with strongly enhanced r-process abundances as reported for metal-poor stars in some ultra-faint dwarfs and the Magellanic Clouds. The similarity of the abundance patterns for metal-poor GCs in different environments points to similar early enrichment histories and only allow for minor variations in the initial mass function., Comment: 34 pages + 6 appendices. Accepted for publication in Astronomy & Astrophysics

We define $k$-dimensional digraphs and initiate a study of their spectral theory. The $k$-dimensional digraphs can be viewed as generating graphs for small categories called $k$-graphs. Guided by geometric insight, we obtain several new series of $k$-graphs using cube complexes covered by Cartesian products of trees, for $k \geq 2$. These $k$-graphs can not be presented as virtual products, and constitute novel models of such small categories. The constructions yield rank-$k$ Cuntz-Krieger algebras for all $k\geq 2$. We introduce Ramanujan $k$-graphs satisfying optimal spectral gap property, and show explicitly how to construct the underlying $k$-digraphs., Comment: 33 pages, many figures. This revised version of the paper features a new title and several changes. Most notably the old Proposition 3.3 is now Theorem 3.1 and has a new proof, and the old Theorem 3.4 is now stated in the more general form of Theorem 3.3. The old Proposition 4.7 is now Theorem 4.7 and is slightly revised. The introduction has been revised accordingly

We recently found the globular cluster (GC) EXT8 in M31 to have an extremely low metallicity of [Fe/H]=-2.91+/-0.04 using high-resolution spectroscopy. Here we present a colour-magnitude diagram (CMD) for EXT8, obtained with the Wide Field Camera 3 on board the Hubble Space Telescope. Compared with the CMDs of metal-poor Galactic GCs, we find that the upper red giant branch (RGB) of EXT8 is about 0.03 mag bluer in F606W-F814W and slightly steeper, as expected from the low spectroscopic metallicity. The observed colour spread on the upper RGB is consistent with being caused entirely by the measurement uncertainties, and we place an upper limit of sigma(F606W-F814W)=0.015 mag on any intrinsic colour spread. The corresponding metallicity spread can be up to sigma([Fe/H])=0.2 dex or >0.7 dex, depending on the isochrone library adopted. The horizontal branch (HB) is located mostly on the blue side of the instability strip and has a tail extending to at least M(F606W)=+3, as in the Galactic GC M15. We identify two candidate RR Lyrae variables and several UV-luminous post-HB/post AGB star candidates, including one very bright (M(F300X)=-3.2) source near the centre of EXT8. The surface brightness of EXT8 out to a radius of 25 arcsec is well fitted by a Wilson-type profile with an ellipticity of epsilon=0.20, a semi-major axis core radius of 0.25", and a central surface brightness of 15.2 mag per square arcsec in the F606W band, with no evidence of extra-tidal structure. Overall, EXT8 has properties consistent with it being a "normal", but very metal-poor GC, and its combination of relatively high mass and very low metallicity thus remains challenging to explain in the context of GC formation theories operating within the hierarchical galaxy assembly paradigm., Comment: Accepted for publication in Astronomy & Astrophysics

Globular clusters (GCs) are dense, gravitationally bound systems of thousands to millions of stars. They are preferentially associated with the oldest components of galaxies, and measurements of their composition can therefore provide insight into the build-up of the chemical elements in galaxies in the early Universe. We report a massive GC in the Andromeda Galaxy (M31) that is extremely depleted in heavy elements. Its iron abundance is about 800 times lower than that of the Sun, and about three times lower than in the most iron-poor GCs previously known. It is also strongly depleted in magnesium. These measurements challenge the notion of a metallicity floor for GCs and theoretical expectations that massive GCs could not have formed at such low metallicities., Comment: Accepted for publication in Science. For supplementary materials, see under ancillary files

We present the Hubble imaging Probe of Extreme Environments and Clusters (HiPEEC) survey. We fit HST NUV to NIR broadband and H$\alpha$ fluxes, to derive star cluster ages, masses, extinctions and determine the star formation rate (SFR) of 6 merging galaxies. These systems are excellent laboratories to trace cluster formation under extreme gas physical conditions, rare in the local universe, but typical for star-forming galaxies at cosmic noon. We detect clusters with ages of 1-500 Myr and masses that exceed $10^7$ M$_\odot$. The recent cluster formation history and their distribution within the host galaxies suggest that systems like NGC34, NGC1614, NGC4194 are close to their final coalescing phase, while NGC3256, NGC3690, NGC6052 are at an earlier/intermediate stage. A Bayesian analysis of the cluster mass function in the age interval 1-100 Myr provides strong evidence in 4 of the 6 galaxies that an exponentially truncated power law better describes the observed mass distributions. For two galaxies, the fits are inconclusive due to low number statistics. We determine power-law slopes $\beta \sim-1.5$ to $-2.0$, and truncation masses, M$_c$, between $10^6$ and a few times $10^7$ M$_\odot$, among the highest values reported in the literature. Advanced mergers have higher M$_c$ than early/intermediate merger stage galaxies, suggesting rapid changes in the dense gas conditions during the merger. We compare the total stellar mass in clusters to the SFR of the galaxy, finding that these systems are among the most efficient environments to form star clusters in the local universe., Comment: Accepted for publication in MNRAS; data and catalogues will be released at this URL http://dx.doi.org/10.17909/t9-cn0b-ht83

The spectroscopic and photometric signals of the star-to-star abundance variations found in globular clusters seem to be correlated with global parameters like the cluster's metallicity, mass and age. Understanding this behaviour could bring us closer to the origin of these intriguing abundance spreads. In this work we use deep HST photometry to look for evidence of abundance variations in the main sequence of a young massive cluster NGC 419 ($\sim10^5$ M$_{\odot}$, $\sim1.4$ Gyr). Unlike previous studies, here we focus on stars in the same mass range found in old globulars ($\sim0.75-1$ M$_{\odot}$), where light elements variations are detected. We find no evidence for N abundance variations among these stars in the $Un-B$ and $U-B$ CMD of NGC 419. This is at odds with the N-variations found in old globulars like 47 Tuc, NGC 6352 and NGC 6637 with similar metallicity to NGC 419. Although the signature of the abundance variations characteristic of old globulars appears to be significantly smaller or absent in this young cluster, we cannot conclude if this effect is mainly driven by its age or its mass., Comment: 9 pages, 8 figures, accepted for publication in MNRAS

Recent work has shown that the properties of multiple populations within massive stellar clusters (i.e., in the extent of their abundance variations as well as the fraction of stars that show the anomalous chemistry) depend on the mass as well as the age of the host cluster. Such correlations are largely unexpected in current models for the formation of multiple populations and hence provide essential insight into their origin. Here we extend or previous study into the presence or absence of multiple populations using integrated light spectroscopy of the $\sim600$~Myr, massive ($\sim10^7 - 10^8$~\msun) clusters, W3 and W30, in the galactic merger remnant, NGC 7252. Due to the extreme mass of both clusters, the expectation is that they should host rather extreme abundance spreads, manifested through, e.g., high mean [Na/Fe] abundances. However, we do not find evidence for a strong [Na/Fe] enhancement, with the observations being consistent with the solar value. This suggests that age is playing a key role, or alternatively that multiple populations only manifest below a certain stellar mass, as the integrated light at all ages above $\sim100$~Myr is dominated by stars near or above the main sequence turn-off., Comment: 7 pages, 7 figures, accepted for publication in MNRAS

Recent studies have revealed that the Multiple Populations (MPs) phenomenon does not occur only in ancient and massive Galactic globular clusters (GCs), but it is also observed in external galaxies, where GCs sample a wide age range with respect to the Milky Way. However, for a long time, it was unclear whether we were looking at the same phenomenon in different environments or not. The first evidence that the MPs phenomenon is the same regardless of cluster age and host galaxy came out recently when an intermediate-age cluster from the Small Magellanic Cloud, Lindsay 1, and a Galactic GC have been directly compared. By complementing those data with new images from the Hubble Space Telescope (HST), we extend the comparison to two clusters of different ages: NGC 2121 ($\sim$2.5Gyr) and NGC 1783 ($\sim$1.5Gyr), from the Large Magellanic Cloud. We find a clear correlation between the RGB width in the pseudo-colour $C_{F275W,F343N,F438W}$ and the age of the cluster itself, with the older cluster having larger $\sigma(C_{F275W,F343N,F438W})^{RGB}$ and vice-versa. Unfortunately, the $\sigma$ values cannot be directly linked to the N-abundance variations within the clusters before properly taking account the effect of the first dredge-up. Such HST data also allow us to explore whether multiple star-formation episodes occurred within NGC 2121. The two populations are indistinguishable, with an age difference of only 6$\pm$12 Myr and an initial Helium spread of 0.02 or lower. This confirms our previous results, putting serious constraints on any model proposed to explain the origin of the chemical anomalies in GCs., Comment: 12 pages, 7 figures, 1 table. Accepted for publication in MNRAS

Graph products of groups were introduced by Green in her thesis. They have an operator algebraic counterpart introduced and explored by Fima and the first-named author. In this paper we prove Khintchine type inequalities for general C$^{\ast}$-algebraic graph products which generalize results by Ricard and Xu on free products of C$^{\ast}$-algebras. We apply these inequalities in the context of (right-angled) Hecke C$^{\ast}$-algebras, which are deformations of the group algebra of Coxeter groups. For these we deduce a Haagerup inequality. We further use this to study the simplicity and trace uniqueness of (right-angled) Hecke C$^{\ast}$-algebras. Lastly we characterize exactness and nuclearity of general Hecke C$^{\ast}$-algebras., Comment: version accepted for J. Functional Analysis

The priority model was introduced to capture "greedy-like" algorithms. Motivated by the success of advice complexity in the area of online algorithms, the fixed priority model was extended to include advice, and a reduction-based framework was developed for proving lower bounds on the amount of advice required to achieve certain approximation ratios in this rather powerful model. To capture most of the algorithms that are considered greedy-like, the even stronger model of adaptive priority algorithms is needed. We extend the adaptive priority model to include advice. We modify the reduction-based framework from the fixed priority case to work with the more powerful adaptive priority algorithms, simplifying the proof of correctness and strengthening all previous lower bounds by a factor of two in the process. We also present a purely combinatorial adaptive priority algorithm with advice for Minimum Vertex Cover on triangle-free graphs of maximum degree three. Our algorithm achieves optimality and uses at most 7n/22 bits of advice. No adaptive priority algorithm without advice can achieve optimality without advice, and we prove that an online algorithm with advice needs more than 7n/22 bits of advice to reach optimality. We show connections between exact algorithms and priority algorithms with advice. The branching in branch-and-reduce algorithms can be seen as trying all possible advice strings, and all priority algorithms with advice that achieve optimality define corresponding exact algorithms, priority exact algorithms. Lower bounds on advice-based adaptive algorithms imply lower bounds on running times of exact algorithms designed in this way.

The discovery of star-to-star abundance variations (a.k.a. multiple populations - MPs) within globular clusters (GCs), which are generally not found in the field or in lower mass open clusters, has led to a search for the unique property of GCs that allow them to host this phenomenon. Recent studies have shown that MPs are not limited to the ancient GCs but are also found in massive clusters with ages down to (at least) 2 Gyr. This finding is important for understanding the physics of the MP phenomenon, as these young clusters can provide much stronger constraints (e.g. on potential age spreads within the clusters) than older ones. However, a direct comparison between ancient GCs and intermediate clusters has not yet been possible due to the different filters adopted in their studies. Here we present new HST UV photometry of the 7.5 Gyr, massive SMC cluster, Lindsay 1, in order to compare its pseudo colour-colour diagram to that of Galactic GCs. We find that they are almost identical and conclude that the MPs phenomenon is the same, regardless of cluster age and host galaxy., Comment: 5 pages, 4 figures. Accepted for publication in MNRAS Letters

The presence of star-to-star light-element abundance variations (a.k.a. multiple populations, MPs) appears to be ubiquitous within old and massive clusters in the Milky Way and all studied nearby galaxies. Most previous studies have focussed on resolved images or spectroscopy of individual stars, although there has been significant effort in the past few years to look for multiple population signatures in integrated light spectroscopy. If proven feasible, integrated light studies offer a potential way to vastly open parameter space, as clusters out to tens of Mpc can be studied. We use the NaD lines in the integrated spectra of two clusters with similar ages ($2-3$ Gyr) but very different masses, NGC 1978 ($\sim3\times10^5$ Msun) in the LMC and G114 ($1.7\times10^7$ Msun) in NGC 1316. For NGC 1978, our findings agree with resolved studies of individual stars which did not find evidence for Na spreads. However, for G114, we find clear evidence for the presence of multiple populations. The fact that the same anomalous abundance patterns are found in both the intermediate age and ancient GCs lends further support to the notion that young massive clusters are effectively the same as the ancient globular clusters, only separated in age., Comment: MNRAS letters, in press (5 pages + appendix)