Search

In a temporal forest each edge has an associated set of time labels that specify the time instants in which the edges are available. A temporal path from vertex $u$ to vertex $v$ in the forest is a selection of a label for each edge in the unique path from $u$ to $v$, assuming it exists, such that the labels selected for any two consecutive edges are non-decreasing. We design linear-size data structures that maintain a temporal forest of rooted trees under addition and deletion of both edge labels and singleton vertices, insertion of root-to-node edges, and removal of edges with no labels. Such data structures can answer temporal reachability, earliest arrival, and latest departure queries. All queries and updates are handled in polylogarithmic worst-case time. Our results can be adapted to deal with latencies. More precisely, all the worst-case time bounds are asymptotically unaffected when latencies are uniform. For arbitrary latencies, the update time becomes amortized in the incremental case where only label additions and edge/singleton insertions are allowed as well as in the decremental case in which only label deletions and edge/singleton removals are allowed. To the best of our knowledge, the only previously known data structure supporting temporal reachability queries is due to Brito, Albertini, Casteigts, and Traven\c{c}olo [Social Network Analysis and Mining, 2021], which can handle general temporal graphs, answers queries in logarithmic time in the worst case, but requires an amortized update time that is quadratic in the number of vertices, up to polylogarithmic factors., Comment: ISAAC 2024

Computational methods both open the frontiers of economic analysis and serve as a bottleneck in what can be achieved. We are the first to study whether Quantum Monte Carlo (QMC) algorithm can improve the runtime of economic applications and challenges in doing so. We provide a detailed introduction to quantum computing and especially the QMC algorithm. Then, we illustrate how to formulate and encode into quantum circuits (a) a bank stress testing model with credit shocks and fire sales, (b) a neoclassical investment model solved with deep learning, and (c) a realistic macro model solved with deep neural networks. We discuss potential computational gains of QMC versus classical computing systems and present a few innovations in benchmarking QMC., Comment: 54 pages (70 with appendix), 15 figures (19 with appendix)

We consider the task of performing Jaccard similarity queries over a large collection of items that are dynamically updated according to a streaming input model. An item here is a subset of a large universe $U$ of elements. A well-studied approach to address this important problem in data mining is to design fast-similarity data sketches. In this paper, we focus on global solutions for this problem, i.e., a single data structure which is able to answer both Similarity Estimation and All-Candidate Pairs queries, while also dynamically managing an arbitrary, online sequence of element insertions and deletions received in input. We introduce and provide an in-depth analysis of a dynamic, buffered version of the well-known $k$-MinHash sketch. This buffered version better manages critical update operations thus significantly reducing the number of times the sketch needs to be rebuilt from scratch using expensive recovery queries. We prove that the buffered $k$-MinHash uses $O(k \log |U|)$ memory words per subset and that its amortized update time per insertion/deletion is $O(k \log |U|)$ with high probability. Moreover, our data structure can return the $k$-MinHash signature of any subset in $O(k)$ time, and this signature is exactly the same signature that would be computed from scratch (and thus the quality of the signature is the same as the one guaranteed by the static $k$-MinHash). Analytical and experimental comparisons with the other, state-of-the-art global solutions for this problem given in [Bury et al.,WSDM'18] show that the buffered $k$-MinHash turns out to be competitive in a wide and relevant range of the online input parameters.

A spanner is a sparse subgraph of a given graph $G$ which preserves distances, measured w.r.t.\ some distance metric, up to a multiplicative stretch factor. This paper addresses the problem of constructing graph spanners w.r.t.\ the group Steiner metric, which generalizes the recently introduced beer distance metric. In such a metric we are given a collection of groups of required vertices, and we measure the distance between two vertices as the length of the shortest path between them that traverses at least one required vertex from each group. We discuss the relation between group Steiner spanners and classic spanners and we show that they exhibit strong ties with sourcewise spanners w.r.t.\ the shortest path metric. Nevertheless, group Steiner spanners capture several interesting scenarios that are not encompassed by existing spanners. This happens, e.g., for the singleton case, in which each group consists of a single required vertex, thus modeling the setting in which routes need to traverse certain points of interests (in any order). We provide several constructions of group Steiner spanners for both the all-pairs and single-source case, which exhibit various size-stretch trade-offs. Notably, we provide spanners with almost-optimal trade-offs for the singleton case. Moreover, some of our spanners also yield novel trade-offs for classical sourcewise spanners. Finally, we also investigate the query times that can be achieved when our spanners are turned into group Steiner distance oracles with the same size, stretch, and building time.

Research on settling dynamics of snow particles, considering their complex morphologies and real atmospheric conditions, remains scarce despite extensive simulations and laboratory studies. Our study bridges the gap through a comprehensive field investigation into the three-dimensional (3D) snow settling dynamics under weak atmospheric turbulence, enabled by a 3D particle tracking velocimetry (PTV) system to record > a million trajectories, coupled with a snow particle analyzer for simultaneous aerodynamic property characterization of four distinct snow types (aggregates, graupels, dendrites, needles). Our findings indicate that while the terminal velocity predicted by the aerodynamic model aligns well with PTV-measured settling velocity for graupels, significant discrepancies arise for non-spherical particles, particularly dendrites, which exhibit higher drag coefficients than predicted. Qualitative observations of 3D settling trajectories highlight pronounced meandering in aggregates and dendrites, in contrast to the subtler meandering observed in needles and graupels, attributable to their smaller frontal areas. This meandering in aggregates and dendrites occurs at lower frequencies compared to that of graupels. Further quantification of trajectory acceleration and curvature suggests that the meandering frequencies in aggregates and dendrites are smaller than that of morphology-induced vortex shedding of disks, likely due to their rotational inertia, and those of graupels align with the small-scale atmospheric turbulence. Moreover, our analysis of vertical acceleration along trajectories elucidates that the orientation changes in dendrites and aggregates enhance their settling velocity. Such insights into settling dynamics refine models of snow settling velocity under weak atmospheric turbulence, with broader implications for more accurately predicting ground snow accumulation., Comment: 32 pages, 15 figures

The statistical properties of Uniform Momentum Zones (UMZs) are extracted from laboratory and field measurements in rough wall turbulent boundary layers to formulate a set of stochastic models for the simulation of instantaneous velocity profiles. A spatio-temporally resolved velocity dataset, covering a field of view of $8 \times 9$ m$^2$, was obtained in the atmospheric surface layer using super-large-scale particle image velocimetry (SLPIV), as part of the Grand-scale Atmospheric Imaging Apparatus (GAIA). Wind tunnel data from a previous study are included for comparison \citep{heisel2020mixing}. The probability density function of UMZ attributes such as their thickness, modal velocity, and averaged vertical velocity are built at varying elevations and modeled using log-normal and Gaussian distributions. Inverse transform sampling of the distributions is used to generate synthetic step-like velocity profiles that are spatially and temporally uncorrelated. Results show that in the wide range of wall-normal distances and $Re_\tau$ up to $ \sim O(10^6)$ investigated here, shear velocity scaling is manifested in the velocity jump across shear interfaces between adjacent UMZs, and attached eddy behavior is observed in the linear proportionality between UMZ thickness and their wall normal location. These very same characteristics are recovered in the generated instantaneous profiles, using both a fully stochastic and a data-driven hybrid stochastic models, which address, in different ways, the coupling between modal velocities and UMZ thickness. Our method provides a stochastic approach for generating an ensemble of instantaneous velocity profiles, consistent with the structural organization of UMZs, where the ensemble reproduces the logarithmic mean velocity profile and recovers significant portions of the Reynolds stresses and thus of the streamwise and vertical velocity variability.

In the \emph{$k$-Diameter-Optimally Augmenting Tree Problem} we are given a tree $T$ of $n$ vertices as input. The tree is embedded in an unknown \emph{metric} space and we have unlimited access to an oracle that, given two distinct vertices $u$ and $v$ of $T$, can answer queries reporting the cost of the edge $(u,v)$ in constant time. We want to augment $T$ with $k$ shortcuts in order to minimize the diameter of the resulting graph. For $k=1$, $O(n \log n)$ time algorithms are known both for paths [Wang, CG 2018] and trees [Bil\`o, TCS 2022]. In this paper we investigate the case of multiple shortcuts. We show that no algorithm that performs $o(n^2)$ queries can provide a better than $10/9$-approximate solution for trees for $k\geq 3$. For any constant $\varepsilon > 0$, we instead design a linear-time $(1+\varepsilon)$-approximation algorithm for paths and $k = o(\sqrt{\log n})$, thus establishing a dichotomy between paths and trees for $k\geq 3$. We achieve the claimed running time by designing an ad-hoc data structure, which also serves as a key component to provide a linear-time $4$-approximation algorithm for trees, and to compute the diameter of graphs with $n + k - 1$ edges in time $O(n k \log n)$ even for non-metric graphs. Our data structure and the latter result are of independent interest., Comment: 22 pages, 6 figures, WADS 2023

A particle tracking velocimetry apparatus is presented that is capable of measuring three-dimensional particle trajectories across large volumes, of the order of several meters, during natural snowfall events. Field experiments, aimed at understanding snow settling kinematics in atmospheric flows, were conducted during the 2021/2022 winter season using this apparatus, from which we show preliminary results. An overview of the methodology, wherein we use a UAV-based calibration method, is provided, and analysis is conducted of a select dataset to demonstrate the capabilities of the system for studying inertial particle dynamics in atmospheric flows. A modular camera array is used, designed specifically for handling the challenges of field deployment during snowfall. This imaging system is calibrated using synchronized imaging of a UAV-carried target to enable measurements centered 10 m above the ground within approximately a 4 m x 4 m x 6 m volume. Using the measured Lagrangian particle tracks we present data concerning 3D trajectory curvature and acceleration statistics, as well as clustering behavior using Voronoi analysis. The limitations, as well as potential future developments, of such a system are discussed in the context of applications with other inertial particles.

The detailed characterization of snow particles is critical for understanding the snow settling behavior and modeling the ground snow accumulation for various applications such as prevention of avalanches and snowmelt-caused floods, etc. In this study, we present a snow particle analyzer for simultaneous measurements of various properties of fresh falling snow, including their concentration, size, shape, type, and density. The analyzer consists of a digital inline holography module for imaging falling snow particles in a sample volume of 88 cm3 and a high-precision scale to measure the weight of the same particles in a synchronized fashion. The holographic images are processed in real-time using a machine learning model and post-processing to determine snow particle concentration, size, shape, and type. Such information is used to obtain the estimated volume, which is subsequently correlated with the weight of snow particles to estimate their density. The performance of the analyzer is assessed using monodispersed spherical glass beads and irregular salt crystals with known density, which shows <5% density measurement errors. In addition, the analyzer was tested in a number of field deployments under different snow and wind conditions. The system is able to achieve measurements of various snow properties at single particle resolution and statistical robustness. The analyzer was also deployed for four hours of operation during a snow event with changing snow and wind conditions, demonstrating its ability for long-term and real-time monitoring of the time-varying snow properties in the field., Comment: 29 pages, 10 figures

Circuit design for quantum machine learning remains a formidable challenge. Inspired by the applications of tensor networks across different fields and their novel presence in the classical machine learning context, one proposed method to design variational circuits is to base the circuit architecture on tensor networks. Here, we comprehensively describe tensor-network quantum circuits and how to implement them in simulations. This includes leveraging circuit cutting, a technique used to evaluate circuits with more qubits than those available on current quantum devices. We then illustrate the computational requirements and possible applications by simulating various tensor-network quantum circuits with PennyLane, an open-source python library for differential programming of quantum computers. Finally, we demonstrate how to apply these circuits to increasingly complex image processing tasks, completing this overview of a flexible method to design circuits that can be applied to industrially-relevant machine learning tasks.

A temporal graph is an undirected graph $G=(V,E)$ along with a function that assigns a time-label to each edge in $E$. A path in $G$ with non-decreasing time-labels is called temporal path and the distance from $u$ to $v$ is the minimum length (i.e., the number of edges) of a temporal path from $u$ to $v$. A temporal $\alpha$-spanner of $G$ is a (temporal) subgraph $H$ that preserves the distances between any pair of vertices in $V$, up to a multiplicative stretch factor of $\alpha$. The size of $H$ is the number of its edges. In this work we study the size-stretch trade-offs of temporal spanners. We show that temporal cliques always admit a temporal $(2k-1)-$spanner with $\tilde{O}(kn^{1+\frac{1}{k}})$ edges, where $k>1$ is an integer parameter of choice. Choosing $k=\lfloor\log n\rfloor$, we obtain a temporal $O(\log n)$-spanner with $\tilde{O}(n)$ edges that has almost the same size (up to logarithmic factors) as the temporal spanner in [Casteigts et al., JCSS 2021] which only preserves temporal connectivity. We then consider general temporal graphs. Since $\Omega(n^2)$ edges might be needed by any connectivity-preserving temporal subgraph [Axiotis et al., ICALP'16], we focus on approximating distances from a single source. We show that $\tilde{O}(n/\log(1+\varepsilon))$ edges suffice to obtain a stretch of $(1+\varepsilon)$, for any small $\varepsilon>0$. This result is essentially tight since there are temporal graphs for which any temporal subgraph preserving exact distances from a single-source must use $\Omega(n^2)$ edges. We extend our analysis to prove an upper bound of $\tilde{O}(n^2/\beta)$ on the size of any temporal $\beta$-additive spanner, which is tight up to polylogarithmic factors. Finally, we investigate how the lifetime of $G$, i.e., the number of its distinct time-labels, affects the trade-off between the size and the stretch of a temporal spanner., Comment: 25 pages, 9 figures

The domain generalization problem has been widely investigated in deep learning for non-contrast imaging over the last years, but it received limited attention for contrast-enhanced imaging. However, there are marked differences in contrast imaging protocols across clinical centers, in particular in the time between contrast injection and image acquisition, while access to multi-center contrast-enhanced image data is limited compared to available datasets for non-contrast imaging. This calls for new tools for generalizing single-domain, single-center deep learning models across new unseen domains and clinical centers in contrast-enhanced imaging. In this paper, we present an exhaustive evaluation of deep learning techniques to achieve generalizability to unseen clinical centers for contrast-enhanced image segmentation. To this end, several techniques are investigated, optimized and systematically evaluated, including data augmentation, domain mixing, transfer learning and domain adaptation. To demonstrate the potential of domain generalization for contrast-enhanced imaging, the methods are evaluated for ventricular segmentation in contrast-enhanced cardiac magnetic resonance imaging (MRI). The results are obtained based on a multi-center cardiac contrast-enhanced MRI dataset acquired in four hospitals located in three countries (France, Spain and China). They show that the combination of data augmentation and transfer learning can lead to single-center models that generalize well to new clinical centers not included during training. Single-domain neural networks enriched with suitable generalization procedures can reach and even surpass the performance of multi-center, multi-vendor models in contrast-enhanced imaging, hence eliminating the need for comprehensive multi-center datasets to train generalizable models.

We study the problem of designing a \emph{resilient} data structure maintaining a tree under the Faulty-RAM model [Finocchi and Italiano, STOC'04] in which up to $\delta$ memory words can be corrupted by an adversary. Our data structure stores a rooted dynamic tree that can be updated via the addition of new leaves, requires linear size, and supports \emph{resilient} (weighted) level ancestor queries, lowest common ancestor queries, and bottleneck vertex queries in $O(\delta)$ worst-case time per operation., Comment: 22 pages, 4 figures, full version of the paper accepted at ISAAC 2021

We present a field study of snow settling dynamics based on simultaneous measurements of the atmospheric flow field and snow particle trajectories. Specifically, a super-large-scale particle image velocimetry (SLPIV) system using natural snow particles as tracers is deployed to quantify the velocity field and identify vortex structures in a 22 m $\times$ 39 m field of view centered 18 m above the ground. Simultaneously, we track individual snow particles in a 3 m $\times$ 5 m sample area within the SLPIV using particle tracking velocimetry (PTV). The results reveal the direct linkage among vortex structures in atmospheric turbulence, the spatial distribution of snow particle concentration, and their settling dynamics. In particular, with snow turbulence interaction at near-critical Stokes number, the settling velocity enhancement of snow particles is multifold, and larger than what has been observed in previous field studies. SLPIV measurements show higher concentration of snow particles preferentially located on the downward side of the vortices identified in the atmospheric flow field. PTV, performed on high resolution images around the reconstructed vortices, confirms the latter trend and provides statistical evidence of the acceleration of snow particles, as they move toward the downward side of vortices. Overall, the simultaneous multi-scale particle imaging presented here enables us to directly quantify the salient features of preferential sweeping, supporting it as an underlying mechanism of snow settling enhancement in the atmospheric surface layer., Comment: 16 pages and 7 figures, to be published in the Journal of Fluid Mechanics

Let $G$ be a directed graph with $n$ vertices, $m$ edges, and non-negative edge costs. Given $G$, a fixed source vertex $s$, and a positive integer $p$, we consider the problem of computing, for each vertex $t\neq s$, $p$ edge-disjoint paths of minimum total cost from $s$ to $t$ in $G$. Suurballe and Tarjan~[Networks, 1984] solved the above problem for $p=2$ by designing a $O(m+n\log n)$ time algorithm which also computes a sparse \emph{single-source $2$-multipath preserver}, i.e., a subgraph containing $2$ edge-disjoint paths of minimum total cost from $s$ to every other vertex of $G$. The case $p \geq 3$ was left as an open problem. We study the general problem ($p\geq 2$) and prove that any graph admits a sparse single-source $p$-multipath preserver with $p(n-1)$ edges. This size is optimal since the in-degree of each non-root vertex $v$ must be at least $p$. Moreover, we design an algorithm that requires $O(pn^2 (p + \log n))$ time to compute both $p$ edge-disjoint paths of minimum total cost from the source to all other vertices and an optimal-size single-source $p$-multipath preserver. The running time of our algorithm outperforms that of a natural approach that solves $n-1$ single-pair instances using the well-known \emph{successive shortest paths} algorithm by a factor of $\Theta(\frac{m}{np})$ and is asymptotically near optimal if $p=O(1)$ and $m=\Theta(n^2)$. Our results extend naturally to the case of $p$ vertex-disjoint paths., Comment: 18 pages, 7 figures