Search

The problem of identifying the best answer among a collection of items having real-valued distribution is well-understood. Despite its practical relevance for many applications, fewer works have studied its extension when multiple and potentially conflicting metrics are available to assess an item's quality. Pareto set identification (PSI) aims to identify the set of answers whose means are not uniformly worse than another. This paper studies PSI in the transductive linear setting with potentially correlated objectives. Building on posterior sampling in both the stopping and the sampling rules, we propose the PSIPS algorithm that deals simultaneously with structure and correlation without paying the computational cost of existing oracle-based algorithms. Both from a frequentist and Bayesian perspective, PSIPS is asymptotically optimal. We demonstrate its good empirical performance in real-world and synthetic instances.

We study the fixed-confidence best-arm identification problem in unimodal bandits, in which the means of the arms increase with the index of the arm up to their maximum, then decrease. We derive two lower bounds on the stopping time of any algorithm. The instance-dependent lower bound suggests that due to the unimodal structure, only three arms contribute to the leading confidence-dependent cost. However, a worst-case lower bound shows that a linear dependence on the number of arms is unavoidable in the confidence-independent cost. We propose modifications of Track-and-Stop and a Top Two algorithm that leverage the unimodal structure. Both versions of Track-and-Stop are asymptotically optimal for one-parameter exponential families. The Top Two algorithm is asymptotically near-optimal for Gaussian distributions and we prove a non-asymptotic guarantee matching the worse-case lower bound. The algorithms can be implemented efficiently and we demonstrate their competitive empirical performance.

Very-high-energy (0.1-100 TeV) gamma-ray emission was observed in HAWC data from the lobes of the microquasar SS 433, making them the first set of astrophysical jets that were resolved at TeV energies. In this work, we update the analysis of SS 433 using 2,565 days of data from the High Altitude Water Cherenkov (HAWC) observatory. Our analysis reports the detection of a point-like source in the east lobe at a significance of $6.6\,\sigma$ and in the west lobe at a significance of $8.2\,\sigma$. For each jet lobe, we localize the gamma-ray emission and identify a best-fit position. The locations are close to the X-ray emission sites "e1" and "w1" for the east and west lobes, respectively. We analyze the spectral energy distributions and find that the energy spectra of the lobes are consistent with a simple power-law $\text{d}N/\text{d}E\propto E^{\alpha}$ with $\alpha = -2.44^{+0.13+0.04}_{-0.12-0.04}$ and $\alpha = -2.35^{+0.12+0.03}_{-0.11-0.03}$ for the east and west lobes, respectively. The maximum energy of photons from the east and west lobes reaches 56 TeV and 123 TeV, respectively. We compare our observations to various models and conclude that the very-high-energy gamma-ray emission can be produced by a population of electrons that were efficiently accelerated.

To find a shortest path between two nodes $s_0$ and $s_1$ in a given graph, a classical approach is to start a Breadth-First Search (BFS) from $s_0$ and run it until the search discovers $s_1$. Alternatively, one can start two Breadth-First Searches, one from $s_0$ and one from $s_1$, and alternate their layer expansions until they meet. This bidirectional BFS can be balanced by always expanding a layer on the side that has discovered fewer vertices so far. This usually results in significant speedups in real-world networks, and it has been shown that this indeed yields sublinear running time on scale-free graph models such as Chung-Lu graphs and hyperbolic random graphs. We improve this layer-balanced bidirectional BFS approach by using a finer balancing technique. Instead of comparing the size of the two BFS trees after each layer expansion, we perform this comparison after each vertex expansion. This gives rise to two algorithms that run faster than the layer-balanced bidirectional BFS on scale-free networks with power-law exponent $\tau \in (2,3)$. The first one is an approximate shortest-path algorithm that outputs a path of length at most 1 longer than the shortest path in time $n^{(\tau-2)/(\tau-1)+o(1)}$. The second one is an exact shortest-path algorithm running in time $n^{1/2+o(1)}$. These runtime bounds hold with high probability when $s_0$ and $s_1$ are chosen uniformly at random among the $n$ vertices of the graph. We also develop an edge-balanced bidirectional BFS algorithm that works under adversarial conditions. This approximate shortest-path algorithm runs in time $n^{1/2+o(1)}$ with high probability when the adversary is allowed to choose $s_0$ and $s_1$ based on their (expected) degree. We complement our theoretical results with experiments on Chung-Lu graphs, Geometric Inhomogeneous Random Graphs, and real-world networks., Comment: 46 pages

Microquasars are laboratories for the study of jets of relativistic particles produced by accretion onto a spinning black hole. Microquasars are near enough to allow detailed imaging of spatial features across the multiwavelength spectrum. The recent extension of the spatial morphology of a microquasar, SS 433, to TeV gamma rays \cite{abeysekara2018very} localizes the acceleration of electrons at shocks in the jet far from the black hole \cite{hess2024ss433}. Here we report TeV gamma-ray emission from another microquasar, V4641~Sgr, which reveals particle acceleration at similar distances from the black hole as SS~433. Additionally, the gamma-ray spectrum of V4641 is among the hardest TeV spectra observed from any known gamma-ray source and is detected up to 200 TeV. Gamma rays are produced by particles, either electrons or hadrons, of higher energies. Because electrons lose energy more quickly the higher their energy, such a spectrum either very strongly constrains the electron production mechanism or points to the acceleration of high-energy hadrons. This observation suggests that large-scale jets from microquasars could be more common than previously expected and that microquasars could be a significant source of Galactic cosmic rays. high energy gamma-rays also provide unique constraints on the acceleration mechanisms of extra-Galactic cosmic rays postulated to be produced by the supermassive black holes and relativistic jets of quasars. The distance to quasars limits imaging studies due to insufficient angular resolution of gamma-rays and due to attenuation of the highest energy gamma-rays by the extragalactic background light.

The advancement of robotic systems has revolutionized numerous industries, yet their operation often demands specialized technical knowledge, limiting accessibility for non-expert users. This paper introduces ROSA (Robot Operating System Agent), an AI-powered agent that bridges the gap between the Robot Operating System (ROS) and natural language interfaces. By leveraging state-of-the-art language models and integrating open-source frameworks, ROSA enables operators to interact with robots using natural language, translating commands into actions and interfacing with ROS through well-defined tools. ROSA's design is modular and extensible, offering seamless integration with both ROS1 and ROS2, along with safety mechanisms like parameter validation and constraint enforcement to ensure secure, reliable operations. While ROSA is originally designed for ROS, it can be extended to work with other robotics middle-wares to maximize compatibility across missions. ROSA enhances human-robot interaction by democratizing access to complex robotic systems, empowering users of all expertise levels with multi-modal capabilities such as speech integration and visual perception. Ethical considerations are thoroughly addressed, guided by foundational principles like Asimov's Three Laws of Robotics, ensuring that AI integration promotes safety, transparency, privacy, and accountability. By making robotic technology more user-friendly and accessible, ROSA not only improves operational efficiency but also sets a new standard for responsible AI use in robotics and potentially future mission operations. This paper introduces ROSA's architecture and showcases initial mock-up operations in JPL's Mars Yard, a laboratory, and a simulation using three different robots. The core ROSA library is available as open-source., Comment: Under review for IEEE Aerospace Conference, 20 pages, 20 figures

Let $f: \mathbb C \to \mathbb C$ be a polynomial map of degree $d \geq 2$. We show that the periodic points of $f$ of period $n$ equidistribute towards the equilibrium measure of $f$ exponentially fast. This quantifies a theorem of Lyubich.

Latest advances in the field of natural language processing (NLP) enable new use cases for different domains, including the medical sector. In particular, transcription can be used to support automation in the nursing documentation process and give nurses more time to interact with the patients. However, different challenges including (a) data privacy, (b) local languages and dialects, and (c) domain-specific vocabulary need to be addressed. In this case study, we investigate the case of home care nursing documentation in Switzerland. We assessed different transcription tools and models, and conducted several experiments with OpenAI Whisper, involving different variations of German (i.e., dialects, foreign accent) and manually curated example texts by a domain expert of home care nursing. Our results indicate that even the used out-of-the-box model performs sufficiently well to be a good starting point for future research in the field.

Some of the most important open problems for linear layouts of graphs ask for the relation between a graph's queue number and its stack number or mixed number. In such, we seek a vertex order and edge partition of $G$ into parts with pairwise non-crossing edges (a stack) or with pairwise non-nesting edges (a queue). Allowing only stacks, only queues, or both, the minimum number of required parts is the graph's stack number $sn(G)$, queue number $qn(G)$, and mixed number $mn(G)$, respectively. Already in 1992, Heath and Rosenberg asked whether $qn(G)$ is bounded in terms of $sn(G)$, that is, whether stacks "can be transformed into" queues. This is equivalent to bipartite $3$-stack graphs having bounded queue number (Dujmovi\'c and Wood, 2005). Recently, Alam et al. asked whether $qn(G)$ is bounded in terms of $mn(G)$, which we show to also be equivalent to the previous questions. We approach the problem from a new angle by considering separated linear layouts of bipartite graphs. In this natural setting all vertices of one part must precede all vertices of the other part. While separated stack and queue numbers coincide, and graphs with bounded separated stack/queue number can be characterized and efficiently recognized, the separated mixed layouts are more challenging. In this work, we thoroughly investigate the relationship between separated and non-separated, mixed and pure linear layouts.

Consider the random $u$-uniform hypergraph (or $u$-graph) process on $n$ vertices, where $n$ is divisible by $r>u\ge 2$. It was recently shown that with high probability, as soon as every vertex is covered by a copy of the complete $u$-graph $K_r$, it also contains a $K_r$-factor (RSA, Vol. 65 II, Sept. 2024). The hitting time result is obtained using a process coupling, which is based on the proof of the corresponding sharp threshold result (RSA, Vol. 61 IV, Dec. 2022). The latter, however, was not only derived for complete $u$-graphs, but for a broader class of so-called nice $u$-graphs. The purpose of this article is to extend the process coupling for complete $u$-graphs to the full scope of the sharp threshold result: nice $u$-graphs. As a byproduct, we obtain the extension of the hitting time result to nice $u$-graphs. Since the relevant combinatorial bounds in the proof for the $K_r$-case cannot be generalized, we introduce new arguments that do not only apply to nice u-graphs, but will be relevant for the broader class of strictly 1-balanced u-graphs. Further, we show how the remainder of the process coupling for the $K_r$-case can be utilized in a black-box manner for any u-graph. These advances pave the way for future generalizations., Comment: 11 pages

While previous years have seen great progress in the 3D reconstruction of humans from monocular videos, few of the state-of-the-art methods are able to handle loose garments that exhibit large non-rigid surface deformations during articulation. This limits the application of such methods to humans that are dressed in standard pants or T-shirts. Our method, ReLoo, overcomes this limitation and reconstructs high-quality 3D models of humans dressed in loose garments from monocular in-the-wild videos. To tackle this problem, we first establish a layered neural human representation that decomposes clothed humans into a neural inner body and outer clothing. On top of the layered neural representation, we further introduce a non-hierarchical virtual bone deformation module for the clothing layer that can freely move, which allows the accurate recovery of non-rigidly deforming loose clothing. A global optimization jointly optimizes the shape, appearance, and deformations of the human body and clothing via multi-layer differentiable volume rendering. To evaluate ReLoo, we record subjects with dynamically deforming garments in a multi-view capture studio. This evaluation, both on existing and our novel dataset, demonstrates ReLoo's clear superiority over prior art on both indoor datasets and in-the-wild videos., Comment: Project page: https://moygcc.github.io/ReLoo/

Many socio-economic systems require positive economic growth rates to function properly. Given uncertainty about future growth rates and increasing evidence that economic growth is a driver of social and environmental crises, these growth dependencies pose serious societal challenges. In recent years, more and more researchers have thus tried to identify growth-dependent systems and develop policies to reduce their growth dependence. However, the concept of 'growth dependence' still lacks a consistent definition and operationalization, which impedes more systematic empirical and theoretical research. This article proposes a simple but powerful framework for defining and operationalizing the concept of 'growth dependence' across socio-economic systems. We provide a general definition consisting of four components that can be specified for different empirical cases: (1) the system under investigation, (2) the unit of measurement of growth, (3) the level of growth and (4) the relevant functions or properties of the system under investigation. According to our general definition, a socio-economic system is growth-dependent if it requires a long-term positive growth rate in terms of a unit of economic measurement to maintain all its functions or properties that are relevant within the chosen normative framework. To illustrate the usefulness of our scheme, we apply it to three areas at the heart of the existing literature on growth dependence: employment, social insurance systems and public finance. These case studies demonstrate that whether or not a system is growth-dependent hinges not only on the empirical properties of the system itself but also on the specification of the concept of growth dependence. Our framework enables coherent, robust and effective definitions and research questions, fostering comparability of findings across different cases and disciplines., Comment: 24 pages, 2 figures, 2 tables

The classical Crossing Lemma by Ajtai et al.~and Leighton from 1982 gave an important lower bound of $c \frac{m^3}{n^2}$ for the number of crossings in any drawing of a given graph of $n$ vertices and $m$ edges. The original value was $c= 1/100$, which then has gradually been improved. Here, the bounds for the density of $k$-planar graphs played a central role. Our new insight is that for $k=2,3$ the $k$-planar graphs have substantially fewer edges if specific local configurations that occur in drawings of $k$-planar graphs of maximum density are forbidden. Therefore, we are able to derive better bounds for the crossing number $\text{cr}(G)$ of a given graph $G$. In particular, we achieve a bound of $\text{cr}(G) \ge \frac{37}{9}m-\frac{155}{9}(n-2)$ for the range of $5n < m \le 6n$, while our second bound $\text{cr}(G) \ge 5m - \frac{203}{9}(n-2)$ is even stronger for larger $m>6n$. For $m > 6.77n$, we finally apply the standard probabilistic proof from the BOOK and obtain an improved constant of $c>1/27.48$ in the Crossing Lemma. Note that the previous constant was $1/29$. Although this improvement is not too impressive, we consider our technique as an important new tool, which might be helpful in various other applications.

We provide the phase diagram of a 2-parameter spin-1 chain that has a symmetry-protected topological (SPT) Haldane phase using computational algorithms along with tensor-network tools. We improve previous results, showing the existence of a new phase and new triple points. New striking features are the triple end of the Haldane phase and the complexity of phases bordering the Haldane phase in proximity allowing moving to nearby non-SPT phases via small perturbations. These characteristics make the system, which appears in Rydberg excitons, e.g. in Cu$_2$O, a prime candidate for applications., Comment: paper (7 pages 10 figures) + appendix (4 pages 4 figures)

We present EgoHDM, an online egocentric-inertial human motion capture (mocap), localization, and dense mapping system. Our system uses 6 inertial measurement units (IMUs) and a commodity head-mounted RGB camera. EgoHDM is the first human mocap system that offers dense scene mapping in near real-time. Further, it is fast and robust to initialize and fully closes the loop between physically plausible map-aware global human motion estimation and mocap-aware 3D scene reconstruction. Our key idea is integrating camera localization and mapping information with inertial human motion capture bidirectionally in our system. To achieve this, we design a tightly coupled mocap-aware dense bundle adjustment and physics-based body pose correction module leveraging a local body-centric elevation map. The latter introduces a novel terrain-aware contact PD controller, which enables characters to physically contact the given local elevation map thereby reducing human floating or penetration. We demonstrate the performance of our system on established synthetic and real-world benchmarks. The results show that our method reduces human localization, camera pose, and mapping accuracy error by 41%, 71%, 46%, respectively, compared to the state of the art. Our qualitative evaluations on newly captured data further demonstrate that EgoHDM can cover challenging scenarios in non-flat terrain including stepping over stairs and outdoor scenes in the wild., Comment: Project Page: https://handiyin.github.io/EgoHDM/

Surveys and experiments in economics involve stateful interactions: participants receive different messages based on earlier answers, choices, and performance, or trade across many rounds with other participants. In the design of Congame, a platform for running such economic studies, we decided to use delimited continuations to manage the common flow of participants through a study. Here we report on the positives of this approach, as well as some challenges of using continuations, such as persisting data across requests, working with dynamic variables, avoiding memory leaks, and the difficulty of debugging continuations.

Identifying single phase, high-entropy systems has been a prominent research focus of materials engineering over the past decade. The considerable effort in computational modeling and experimental verification has yielded several methods and descriptors for predicting if a single phase will form; however, the details surrounding the resulting crystal structure have largely remained a mystery. Here, we present a compelling argument for the role of allotropy in determining the crystal structure of a single-phase, high-entropy alloy. High entropy alloys can contain 5 or more elements and must achieve a configurational entropy greater than 1.5R. This study shows that when these high entropy material conditions are met, the majority crystal structure of the non-allotrope forming element plays a dominant role in crystal structure determination. The theory is demonstrated via several approaches, including analysis of 434 unique known single-phase compositions from the literature, thermodynamic modeling of more than 1,400 compositions, and experimental synthesis of nine specific alloys that test this hypothesis. The results demonstrate allotropy can identify a subset of compositions unlikely to form a single phase and predict the crystal structure with a high degree of accuracy for a wide range of simple (e.g., 5 equiatomic elements) and more complex (e.g., Al0.3B0.6CoCrFeNiCu0.7Si0.1) high entropy alloys. Allotropy provides new insight into the underlying physics governing the resultant crystal structure in materials without a principle element. As high entropy materials continue to be an area of focus for developing materials with unique properties, this study is expected to serve as a significant tool in the screening of materials for specific crystal structures.

We study the impact of forbidding short cycles to the edge density of $k$-planar graphs; a $k$-planar graph is one that can be drawn in the plane with at most $k$ crossings per edge. Specifically, we consider three settings, according to which the forbidden substructures are $3$-cycles, $4$-cycles or both of them (i.e., girth $\ge 5$). For all three settings and all $k\in\{1,2,3\}$, we present lower and upper bounds on the maximum number of edges in any $k$-planar graph on $n$ vertices. Our bounds are of the form $c\,n$, for some explicit constant $c$ that depends on $k$ and on the setting. For general $k \geq 4$ our bounds are of the form $c\sqrt{k}n$, for some explicit constant $c$. These results are obtained by leveraging different techniques, such as the discharging method, the recently introduced density formula for non-planar graphs, and new upper bounds for the crossing number of $2$-- and $3$-planar graphs in combination with corresponding lower bounds based on the Crossing Lemma., Comment: Appears in the Proceedings of the 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

We show that every planar graph has a monotone topological 2-page book embedding where at most (4n-10)/5 (of potentially 3n-6) edges cross the spine, and every edge crosses the spine at most once; such an edge is called a biarc. We can also guarantee that all edges that cross the spine cross it in the same direction (e.g., from bottom to top). For planar 3-trees we can further improve the bound to (3n-9)/4, and for so-called Kleetopes we obtain a bound of at most (n-8)/3 edges that cross the spine. The bound for Kleetopes is tight, even if the drawing is not required to be monotone. A Kleetope is a plane triangulation that is derived from another plane triangulation T by inserting a new vertex v_f into each face f of T and then connecting v_f to the three vertices of f., Comment: Appears in the Proceedings of the 32nd International Symposium on Graph Drawing and Network Visualization (GD 2024)

While there is a widespread belief that artificial general intelligence (AGI) -- or even superhuman AI -- is imminent, complex problems in expert domains are far from being solved. We argue that such problems require human-AI cooperation and that the current state of the art in generative AI is unable to play the role of a reliable partner due to a multitude of shortcomings, including inability to keep track of a complex solution artifact (e.g., a software program), limited support for versatile human preference expression and lack of adapting to human preference in an interactive setting. To address these challenges, we propose HAI-Co2, a novel human-AI co-construction framework. We formalize HAI-Co2 and discuss the difficult open research problems that it faces. Finally, we present a case study of HAI-Co2 and demonstrate its efficacy compared to monolithic generative AI models., Comment: 15 pages main content; 3 pages Appendix; 5 figures

Fully understanding performance is a growing challenge when building next-generation cloud systems. Often these systems build on next-generation hardware, and evaluation in realistic physical testbeds is out of reach. Even when physical testbeds are available, visibility into essential system aspects is a challenge in modern systems where system performance depends on often sub-$\mu s$ interactions between HW and SW components. Existing tools such as performance counters, logging, and distributed tracing provide aggregate or sampled information, but remain insufficient for understanding individual requests in-depth. In this paper, we explore a fundamentally different approach to enable in-depth understanding of cloud system behavior at the software and hardware level, with (almost) arbitrarily fine-grained visibility. Our proposal is to run cloud systems in detailed full-system simulations, configure the simulators to collect detailed events without affecting the system, and finally assemble these events into end-to-end system traces that can be analyzed by existing distributed tracing tools.

We study push-pull rumour spreading in small-world models for social networks where the degrees follow a power-law. In a non-geometric setting Fountoulakis, Panagiotou and Sauerwald have shown that rumours always spread fast (SODA 2012). On the other hand, Janssen and Mehrabian have found that rumours spread slowly in a spatial preferential attachment model (SIDMA 2017). We study the question systematically for the model of geometric inhomogeneous random graphs (GIRGs), which has been found to be a good theoretical and empirical fit for social networks. Our result is two-fold: with classical Euclidean geometry both slow and fast rumour spreading may occur, depending on the exponent of the power law and the prevalence of weak ties in the networks, and we fully characterise the phase boundaries between those two regimes. Depending on the parameters, fast spreading may either mean polylogarithmic time or even doubly logarithmic time. Secondly, we show that rumour spreading is always fast in a non-metric geometry. The considered non-metric geometry allows to model social connections where resemblance of vertices in a single attribute, such as familial kinship, already strongly indicates the presence of an edge. Classical Euclidean Geometry fails to capture such ties. For some regimes in the Euclidean setting, the efficient pathways for spreading rumours differ from previously identified paths. A vertex of degree $d$ can transmit the rumour efficiently to a vertex of larger degree by a chain of length $3$, where one of the two intermediaries has constant degree, and the other has degree $d^{c}$ for some constant $c<1$., Comment: 40 pages

Most complex diseases, including cancer and non-malignant diseases like asthma, have distinct molecular subtypes that require distinct clinical approaches. However, existing computational patient stratification methods have been benchmarked almost exclusively on cancer omics data and only perform well when mutually exclusive subtypes can be characterized by many biomarkers. Here, we contribute with a massive evaluation attempt, quantitatively exploring the power of 22 unsupervised patient stratification methods using both, simulated and real transcriptome data. From this experience, we developed UnPaSt (https://apps.cosy.bio/unpast/) optimizing unsupervised patient stratification, working even with only a limited number of subtype-predictive biomarkers. We evaluated all 23 methods on real-world breast cancer and asthma transcriptomics data. Although many methods reliably detected major breast cancer subtypes, only few identified Th2-high asthma, and UnPaSt significantly outperformed its closest competitors in both test datasets. Essentially, we showed that UnPaSt can detect many biologically insightful and reproducible patterns in omic datasets., Comment: The first two authors listed are joint first authors. The last two authors listed are joint last authors

Providing high quality software and evaluating the software reliability in softwarized networks are crucial for vendors and customers. These networks rely on open source code, which are sensitive to contain high number of bugs. Both, the knowledge about the code of previous releases as well as the bug history of the particular project can be used to evaluate the software reliability of a new software release based on SRGM. In this work a framework to predict the number of the bugs of a new release, as well as other reliability parameters, is proposed. An exemplary implementation of this framework to two particular open source projects, is described in detail. The difference between the prediction accuracy of the two projects is presented. Different alternatives to increase the prediction accuracy are proposed and compared in this paper.

Supernova remnants (SNRs) are believed to be capable of accelerating cosmic rays (CRs) to PeV energies. SNR G106.3+2.7 is a prime PeVatron candidate. It is formed by a head region, where the pulsar J2229+6114 and its boomerang-shaped pulsar wind nebula are located, and a tail region containing SN ejecta. The lack of observed gamma ray emission from the two regions of this SNR has made it difficult to assess which region would be responsible for the PeV CRs. We aim to characterize the very-high-energy (VHE, 0.1-100 TeV) gamma ray emission from SNR G106.3+2.7 by determining the morphology and spectral energy distribution of the region. This is accomplished using 2565 days of data and improved reconstruction algorithms from the HAWC Observatory. We also explore possible gamma ray production mechanisms for different energy ranges. Using a multi-source fitting procedure based on a maximum-likelihood estimation method, we evaluate the complex nature of this region. We determine the morphology, spectrum, and energy range for the source found in the region. Molecular cloud information is also used to create a template and evaluate the HAWC gamma ray spectral properties at ultra-high-energies (UHE, >56 TeV). This will help probe the hadronic nature of the highest-energy emission from the region. We resolve one extended source coincident with all other gamma ray observations of the region. The emission reaches above 100~TeV and its preferred log-parabola shape in the spectrum shows a flux peak in the TeV range. The molecular cloud template fit on the higher energy data reveals that the SNR's energy budget is fully capable of producing a purely hadronic source for UHE gamma rays.

HESS J1809-193 is an unidentified TeV source, first detected by the High Energy Stereoscopic System (H.E.S.S.) Collaboration. The emission originates in a source-rich region that includes several Supernova Remnants (SNR) and Pulsars (PSR) including SNR G11.1+0.1, SNR G11.0-0.0, and the young radio pulsar J1809-1917. Originally classified as a pulsar wind nebula (PWN) candidate, recent studies show the peak of the TeV region overlapping with a system of molecular clouds. This resulted in the revision of the original leptonic scenario to look for alternate hadronic scenarios. Marked as a potential PeVatron candidate, this region has been studied extensively by H.E.S.S. due to its emission extending up-to several tens of TeV. In this work, we use 2398 days of data from the High Altitude Water Cherenkov (HAWC) observatory to carry out a systematic source search for the HESS J1809-193 region. We were able to resolve emission detected as an extended component (modelled as a Symmetric Gaussian with a 1 $\sigma$ radius of 0.21 $^\circ$) with no clear cutoff at high energies and emitting photons up-to 210 TeV. We model the multi-wavelength observations for the region HESS J1809-193 using a time-dependent leptonic model and a lepto-hadronic model. Our model indicates that both scenarios could explain the observed data within the region of HESS J1809-193.

Higher-order properties of functional magnetic resonance imaging (fMRI) induced connectivity have been shown to unravel many exclusive topological and dynamical insights beyond pairwise interactions. Nonetheless, whether these fMRI-induced higher-order properties play a role in disentangling other neuroimaging modalities' insights remains largely unexplored and poorly understood. In this work, by analyzing fMRI data from the Human Connectome Project Young Adult dataset using persistent homology, we discovered that the volume-optimal persistence homological scaffolds of fMRI-based functional connectomes exhibited conservative topological reconfigurations from the resting state to attentional task-positive state. Specifically, while reflecting the extent to which each cortical region contributed to functional cycles following different cognitive demands, these reconfigurations were constrained such that the spatial distribution of cavities in the connectome is relatively conserved. Most importantly, such level of contributions covaried with powers of aperiodic activities mostly within the theta-alpha (4-12 Hz) band measured by magnetoencephalography (MEG). This comprehensive result suggests that fMRI-induced hemodynamics and MEG theta-alpha aperiodic activities are governed by the same functional constraints specific to each cortical morpho-structure. Methodologically, our work paves the way toward an innovative computing paradigm in multimodal neuroimaging topological learning., Comment: The code for our analyses is provided in https://github.com/ngcaonghi/scaffold_noise

We report an observation of ultra-high energy (UHE) gamma rays from the Galactic Center region, using seven years of data collected by the High-Altitude Water Cherenkov (HAWC) Observatory. The HAWC data are best described as a point-like source (HAWC J1746-2856) with a power-law spectrum ($\mathrm{d}N/\mathrm{d}E=\phi(E/26 \,\text{TeV})^{\gamma}$), where $\gamma=-2.88 \pm 0.15_{\text{stat}} - 0.1_{\text{sys}} $ and $\phi=1.5 \times 10^{-15}$ (TeV cm$^{2}$s)$^{-1}$ $\pm\, 0.3_{\text{stat}}\,^{+0.08_{\text{sys}}}_{-0.13_{\text{sys}}}$ extending from 6 to 114 TeV. We find no evidence of a spectral cutoff up to $100$ TeV using HAWC data. Two known point-like gamma-ray sources are spatially coincident with the HAWC gamma-ray excess: Sgr A$^{*}$ (HESS J1745-290) and the Arc (HESS J1746-285). We subtract the known flux contribution of these point sources from the measured flux of HAWC J1746-2856 to exclude their contamination and show that the excess observed by HAWC remains significant ($>$5$\sigma$) with the spectrum extending to $>$100 TeV. Our result supports that these detected UHE gamma rays can originate via hadronic interaction of PeV cosmic-ray protons with the dense ambient gas and confirms the presence of a proton PeVatron at the Galactic Center.

The first TeV gamma-ray source with no lower energy counterparts, TeV J2032+4130, was discovered by HEGRA. It appears in the third HAWC catalog as 3HWC J2031+415 and it is a bright TeV gamma-ray source whose emission has previously been resolved as 2 sources: HAWC J2031+415 and HAWC J2030+409. While HAWC J2030+409 has since been associated with the \emph{Fermi-LAT} Cygnus Cocoon, no such association for HAWC J2031+415 has yet been found. In this work, we investigate the spectrum and energy-dependent morphology of HAWC J2031+415. We associate HAWC J2031+415 with the pulsar PSR J2032+4127 and perform a combined multi-wavelength analysis using radio, X-ray, and $\gamma$-ray emission. We conclude that HAWC J2031+415 and, by extension, TeV J2032+4130 are most probably a pulsar wind nebula (PWN) powered by PSR J2032+4127.

Properly defining a reward signal to efficiently train a reinforcement learning (RL) agent is a challenging task. Designing balanced objective functions from which a desired behavior can emerge requires expert knowledge, especially for complex environments. Learning rewards from human feedback or using large language models (LLMs) to directly provide rewards are promising alternatives, allowing non-experts to specify goals for the agent. However, black-box reward models make it difficult to debug the reward. In this work, we propose Object-Centric Assessment with Language Models (OCALM) to derive inherently interpretable reward functions for RL agents from natural language task descriptions. OCALM uses the extensive world-knowledge of LLMs while leveraging the object-centric nature common to many environments to derive reward functions focused on relational concepts, providing RL agents with the ability to derive policies from task descriptions., Comment: Accepted at the RLBRew Workshop at RLC 2024

A hypergraph $H = (V,E)$ is said to have K\H{o}nig's Property if there is a matching $M\subseteq E$ and $S\subseteq V$ such that $|S \cap e| = 1$ for all $e\in M$, and $S$ is a vertex cover of $H$. Aharoni posed the question whether K\H{o}nig's Property is inheritable from finite subsets of $E$. We provide a negative answer and investigate similar questions for weaker properties., Comment: 8 pages

PolySAT is a word-level decision procedure supporting bit-precise SMT reasoning over polynomial arithmetic with large bit-vector operations. The PolySAT calculus extends conflict-driven clause learning modulo theories with two key components: (i) a bit-vector plugin to the equality graph, and (ii) a theory solver for bit-vector arithmetic with non-linear polynomials. PolySAT implements dedicated procedures to extract bit-vector intervals from polynomial inequalities. For the purpose of conflict analysis and resolution, PolySAT comes with on-demand lemma generation over non-linear bit-vector arithmetic. PolySAT is integrated into the SMT solver Z3 and has potential applications in model checking and smart contract verification where bit-blasting techniques on multipliers/divisions do not scale., Comment: Submitted to FMCAD 2024, https://fmcad.org/FMCAD24/

In bandit best-arm identification, an algorithm is tasked with finding the arm with highest mean reward with a specified accuracy as fast as possible. We study multi-fidelity best-arm identification, in which the algorithm can choose to sample an arm at a lower fidelity (less accurate mean estimate) for a lower cost. Several methods have been proposed for tackling this problem, but their optimality remain elusive, notably due to loose lower bounds on the total cost needed to identify the best arm. Our first contribution is a tight, instance-dependent lower bound on the cost complexity. The study of the optimization problem featured in the lower bound provides new insights to devise computationally efficient algorithms, and leads us to propose a gradient-based approach with asymptotically optimal cost complexity. We demonstrate the benefits of the new algorithm compared to existing methods in experiments. Our theoretical and empirical findings also shed light on an intriguing concept of optimal fidelity for each arm.

Monte-Carlo Tree Search (MCTS) is a widely-used strategy for online planning that combines Monte-Carlo sampling with forward tree search. Its success relies on the Upper Confidence bound for Trees (UCT) algorithm, an extension of the UCB method for multi-arm bandits. However, the theoretical foundation of UCT is incomplete due to an error in the logarithmic bonus term for action selection, leading to the development of Fixed-Depth-MCTS with a polynomial exploration bonus to balance exploration and exploitation~\citep{shah2022journal}. Both UCT and Fixed-Depth-MCTS suffer from biased value estimation: the weighted sum underestimates the optimal value, while the maximum valuation overestimates it~\citep{coulom2006efficient}. The power mean estimator offers a balanced solution, lying between the average and maximum values. Power-UCT~\citep{dam2019generalized} incorporates this estimator for more accurate value estimates but its theoretical analysis remains incomplete. This paper introduces Stochastic-Power-UCT, an MCTS algorithm using the power mean estimator and tailored for stochastic MDPs. We analyze its polynomial convergence in estimating root node values and show that it shares the same convergence rate of $\mathcal{O}(n^{-1/2})$, with $n$ is the number of visited trajectories, as Fixed-Depth-MCTS, with the latter being a special case of the former. Our theoretical results are validated with empirical tests across various stochastic MDP environments., Comment: UAI 2024 conference

We present MultiPly, a novel framework to reconstruct multiple people in 3D from monocular in-the-wild videos. Reconstructing multiple individuals moving and interacting naturally from monocular in-the-wild videos poses a challenging task. Addressing it necessitates precise pixel-level disentanglement of individuals without any prior knowledge about the subjects. Moreover, it requires recovering intricate and complete 3D human shapes from short video sequences, intensifying the level of difficulty. To tackle these challenges, we first define a layered neural representation for the entire scene, composited by individual human and background models. We learn the layered neural representation from videos via our layer-wise differentiable volume rendering. This learning process is further enhanced by our hybrid instance segmentation approach which combines the self-supervised 3D segmentation and the promptable 2D segmentation module, yielding reliable instance segmentation supervision even under close human interaction. A confidence-guided optimization formulation is introduced to optimize the human poses and shape/appearance alternately. We incorporate effective objectives to refine human poses via photometric information and impose physically plausible constraints on human dynamics, leading to temporally consistent 3D reconstructions with high fidelity. The evaluation of our method shows the superiority over prior art on publicly available datasets and in-the-wild videos., Comment: Project page: https://eth-ait.github.io/MultiPly/

Feedback data plays an important role in fine-tuning and evaluating state-of-the-art AI models. Often pairwise text preferences are used: given two texts, human (or AI) annotators select the "better" one. Such feedback data is widely used to align models to human preferences (e.g., reinforcement learning from human feedback), or to rank models according to human preferences (e.g., Chatbot Arena). Despite its wide-spread use, prior work has demonstrated that human-annotated pairwise text preference data often exhibits unintended biases. For example, human annotators have been shown to prefer assertive over truthful texts in certain contexts. Models trained or evaluated on this data may implicitly encode these biases in a manner hard to identify. In this paper, we formulate the interpretation of existing pairwise text preference data as a compression task: the Inverse Constitutional AI (ICAI) problem. In constitutional AI, a set of principles (or constitution) is used to provide feedback and fine-tune AI models. The ICAI problem inverts this process: given a dataset of feedback, we aim to extract a constitution that best enables a large language model (LLM) to reconstruct the original annotations. We propose a corresponding initial ICAI algorithm and validate its generated constitutions quantitatively based on reconstructed annotations. Generated constitutions have many potential use-cases -- they may help identify undesirable biases, scale feedback to unseen data or assist with adapting LLMs to individual user preferences. We demonstrate our approach on a variety of datasets: (a) synthetic feedback datasets with known underlying principles; (b) the AlpacaEval dataset of cross-annotated human feedback; and (c) the crowdsourced Chatbot Arena data set. We release the code for our algorithm and experiments at https://github.com/rdnfn/icai .

The introduction of geometry has proven instrumental in the efforts towards more realistic models for real-world networks. In Geometric Inhomogeneous Random Graphs (GIRGs), Euclidean Geometry induces clustering of the vertices, which is widely observed in networks in the wild. Euclidean Geometry in multiple dimensions however restricts proximity of vertices to those cases where vertices are close in each coordinate. We introduce a large class of GIRG extensions, called BDF-GIRGs, which capture arbitrary hierarchies of the coordinates within the distance function of the vertex feature space. These distance functions have the potential to allow more realistic modeling of the complex formation of social ties in real-world networks, where similarities between people lead to connections. Here, similarity with respect to certain features, such as familial kinship or a shared workplace, suffices for the formation of ties. It is known that - while many key properties of GIRGs, such as log-log average distance and sparsity, are independent of the distance function - the Euclidean metric induces small separators, i.e. sublinear cuts of the unique giant component in GIRGs, whereas no such sublinear separators exist under the component-wise minimum distance. Building on work of Lengler and Todorovi\'{c}, we give a complete classification for the existence of small separators in BDF-GIRGs. We further show that BDF-GIRGs all fulfill a stochastic triangle inequality and thus also exhibit clustering.

We revisit the identification of an $\varepsilon$-optimal policy in average-reward Markov Decision Processes (MDP). In such MDPs, two measures of complexity have appeared in the literature: the diameter, $D$, and the optimal bias span, $H$, which satisfy $H\leq D$. Prior work have studied the complexity of $\varepsilon$-optimal policy identification only when a generative model is available. In this case, it is known that there exists an MDP with $D \simeq H$ for which the sample complexity to output an $\varepsilon$-optimal policy is $\Omega(SAD/\varepsilon^2)$ where $S$ and $A$ are the sizes of the state and action spaces. Recently, an algorithm with a sample complexity of order $SAH/\varepsilon^2$ has been proposed, but it requires the knowledge of $H$. We first show that the sample complexity required to estimate $H$ is not bounded by any function of $S,A$ and $H$, ruling out the possibility to easily make the previous algorithm agnostic to $H$. By relying instead on a diameter estimation procedure, we propose the first algorithm for $(\varepsilon,\delta)$-PAC policy identification that does not need any form of prior knowledge on the MDP. Its sample complexity scales in $SAD/\varepsilon^2$ in the regime of small $\varepsilon$, which is near-optimal. In the online setting, our first contribution is a lower bound which implies that a sample complexity polynomial in $H$ cannot be achieved in this setting. Then, we propose an online algorithm with a sample complexity in $SAD^2/\varepsilon^2$, as well as a novel approach based on a data-dependent stopping rule that we believe is promising to further reduce this bound.

The magnetic dipole and the spectroscopic quadrupole moments of the nuclear ground states in the odd-mass nickel isotopes $^{59-67}$Ni have been determined using collinear laser spectroscopy at the CERN-ISOLDE facility. They are compared to ab initio valence-space in-medium similarity renormalization group (VS-IMSRG) calculations including contributions of two-body currents as well as to shell-model calculations. The two-body-current contributions significantly improve the agreement with experimental data, reducing the mean-square deviation from the experimental moments by a factor of 3 to 5, depending on the employed interaction. For all interactions, the largest contributions are obtained for the $5/2^-$ ($7/2^-$) isotopes $^{65}$Ni ($^{55}$Ni), which is ascribed to the high angular momentum of the $f$ orbitals. Our results demonstrate that the inclusion of two-body-current contributions to the magnetic moment in an isotopic chain of complex nuclei can be handled by the VS-IMSRG and can outperform phenomenological shell-model calculations using effective $g$-factors in the nickel region., Comment: Published in Physics Letters B, 10 pages, 3 figures

The High-Altitude Water Cherenkov (HAWC) Gamma-Ray Observatory located on the side of the Sierra Negra volcano in Mexico, has been fully operational since 2015. The HAWC collaboration has recently significantly improved their extensive-air-shower reconstruction algorithms, which has notably advanced the observatory performance. The energy resolution for primary gamma rays with energies below 1~TeV was improved by including a noise-suppression algorithm. Corrections have also been made to systematic errors in direction fitting related to the detector and shower plane inclinations, $\mathcal{O}(0.1^{\circ})$ biases in highly inclined showers, as well as enhancements to the core reconstruction. The angular resolution for gamma rays approaching the HAWC array from large zenith angles ($> 37^{\circ}$) has improved by a factor of four at the highest energies ($> 70$~TeV) as compared to previous reconstructions. The inclusion of a lateral distribution function fit to the extensive air shower footprint on the array to separate gamma-ray primaries from cosmic-ray ones, based on the resulting $\chi^{2}$ values, improved the background rejection performance at all inclinations. At large zenith angles, the improvement in significance is a factor of four compared to previous HAWC publications. These enhancements have been verified by observing the Crab Nebula, which is an overhead source for the HAWC Observatory. We show that the sensitivity to Crab-like point sources ($E^{-2.63}$) with locations overhead to 30$^{\circ}$ zenith is comparable or less than 10\% of the Crab Nebula's flux between 2 and 50~TeV. Thanks to these improvements, HAWC can now detect more sources, including the Galactic Center.

Galactic PeVatrons are sources that can accelerate cosmic rays to PeV energies. The high-energy cosmic rays are expected to interact with the surrounding ambient material or radiation, resulting in the production of gamma rays and neutrinos. To optimize for the detection of such associated production of gamma rays and neutrinos for a given source morphology and spectrum, a multi-messenger analysis that combines gamma rays and neutrinos is required. In this study, we use the Multi-Mission Maximum Likelihood framework (3ML) with IceCube Maximum Likelihood Analysis software (i3mla) and HAWC Accelerated Likelihood (HAL) to search for a correlation between 22 known gamma-ray sources from the third HAWC gamma-ray catalog and 14 years of IceCube track-like data. No significant neutrino emission from the direction of the HAWC sources was found. We report the best-fit gamma-ray model and 90% CL neutrino flux limit from the 22 sources. From the neutrino flux limit, we conclude that the gamma-ray emission from five of the sources can not be produced purely from hadronic interactions. We report the limit for the fraction of gamma rays produced by hadronic interactions for these five sources.

We prove that the Feynman category encoding Schwarz's variant of modular operads is Koszul. Our proof uses a generalization of the theory of distributive laws to the groupoid colored setting.

Supervising the safe operation of automated vehicles is a key requirement in order to unleash their full potential in future transportation systems. In particular, previous publications have argued that SAE Level 4 vehicles should be aware of their capabilities at runtime to make appropriate behavioral decisions. In this paper, we present a framework that enables the implementation of an online capability monitor. We derive a graphical system model that captures the relationships between the quality of system elements across different architectural views. In an expert-driven approach, we parameterize Bayesian Networks based on this structure using Fuzzy Logic. Using the online monitor, we infer the quality of the system's capabilities based on technical measurements acquired at runtime., Comment: Accepted for 27th IEEE International Conference on Intelligent Transportation Systems

We provide global extensions of previous results about representations of characteristic classes of coherent analytic sheaves and of Baum-Bott residues of holomorphic foliations. We show in the first case that they can be represented by currents with support on the support of the given coherent analytic sheaf, and in the second case, by currents with support on the singular set of the foliation. In previous works, we have constructed such representatives provided global resolutions of the appropriate sheaves existed. In this article, we show that the definition of Chern classes of Green and the associated techniques, which work on arbitrary complex manifolds without any assumption on the existence of global resolutions, may be combined with our previous constructions to yield the desired representatives. We also prove a transgression formula for such representatives, which is new even in the case when global resolutions exist. More precisely, the representatives depend on local resolutions of the sheaf, and on choices of metrics and connections on these bundles, i.e., the currents for two different choices differ by a current of the form $dN$, where $N$ is an explicit current, which in the first case above has support on the support of the given coherent analytic sheaf, and in the second case above has support on the singular set of the foliation., Comment: 27 pages