Search for: All records

As one of the most primitive operators in graph algorithms, such as the triangle counting, maximal clique enumeration, and subgraph listing, a set intersection operator returns common vertices between any two given sets of vertices in data graphs. It is therefore very important to accelerate the set intersection, which will benefit a bunch of tasks that take it as a built-in block. Existing works on the set intersection usually followed the merge intersection or galloping-search framework, and most optimization research focused on how to leverage the SIMD hardware instructions. In this paper, we propose a novel multi-level set intersection framework, namely hierarchical set partitioning and join (HERO), by using our well-designed set intersection bitmap tree (SIB-tree) index, which is independent of SIMD instructions and completely orthogonal to the merge intersection framework. We recursively decompose the set intersection task into small-sized subtasks and solve each subtask using bitmap and boolean AND operations. To sufficiently achieve the acceleration brought by our proposed intersection approach, we formulate a graph reordering problem, prove its NP-hardness, and then develop a heuristic algorithm to tackle this problem. Extensive experiments on real-world graphs have been conducted to confirm the efficiency and effectiveness of our HERO approach. The speedup over classic merge intersection achieves up to 188x and 176x for triangle counting and maximal clique enumeration, respectively. 

Numerous applications in machine learning and data analytics can be formulated as equilibrium computation over Riemannian manifolds. Despite the extensive investigation of their Euclidean counterparts, the performance of Riemannian gradient-based algorithms remain opaque and poorly understood. We revisit the original scheme of Riemannian gradient descent (RGD) and analyze it under a geodesic monotonicity assumption, which includes the well-studied geodesically convex-concave min-max optimization problem as a special case. Our main contribution is to show that, despite the phenomenon of distance distortion, the RGD scheme, with a step size that is agnostic to the manifold's curvature, achieves a curvature-independent and linear last-iterate convergence rate in the geodesically strongly monotone setting. To the best of our knowledge, the possibility of curvature-independent rates and/or last-iterate convergence in the Riemannian setting has not been considered before. 

Aims.We investigate the photometric characteristics of a sample of intermediate-luminosity red transients (ILRTs), a class of elusive objects with peak luminosity between that of classical novae and standard supernovae. Our goal is to provide a stepping stone in the path to reveal the physical origin of such events, thanks to the analysis of the datasets collected. Methods.We present the multi-wavelength photometric follow-up of four ILRTs, namely NGC 300 2008OT-1, AT 2019abn, AT 2019ahd, and AT 2019udc. Through the analysis and modelling of their spectral energy distribution and bolometric light curves, we inferred the physical parameters associated with these transients. Results.All four objects display a single-peaked light curve which ends in a linear decline in magnitudes at late phases. A flux excess with respect to a single blackbody emission is detected in the infrared domain for three objects in our sample, a few months after maximum. This feature, commonly found in ILRTs, is interpreted as a sign of dust formation. Mid-infrared monitoring of NGC 300 2008OT-1 761 days after maximum allowed us to infer the presence of ∼10⁻³–10⁻⁵M_⊙of dust, depending on the chemical composition and the grain size adopted. The late-time decline of the bolometric light curves of the considered ILRTs is shallower than expected for⁵⁶Ni decay, hence requiring an additional powering mechanism. James Webb Space Telescope observations of AT 2019abn prove that the object has faded below its progenitor luminosity in the mid-infrared domain, five years after its peak. Together with the disappearance of NGC 300 2008OT-1 in Spitzer images seven years after its discovery, this supports the terminal explosion scenario for ILRTs. With a simple semi-analytical model we tried to reproduce the observed bolometric light curves in the context of a few solar masses ejected at few 10³km s⁻¹and enshrouded in an optically thick circumstellar medium. 

Aims.We investigate the spectroscopic characteristics of intermediate-luminosity Red Transients (ILRTs), a class of elusive objects with peak luminosity between that of classical novae and standard supernovae. Our goal is to provide a stepping stone in the path to unveiling the physical origin of these events based on the analysis of the collected datasets. Methods.We present the extensive optical and near-infrared (NIR) spectroscopic monitoring of four ILRTs, namely NGC 300 2008OT-1, AT 2019abn, AT 2019ahd and AT 2019udc. First we focus on the evolution of the most prominent spectral features observed in the low-resolution spectra. We then present a more detailed description of the high-resolution spectrum collected for NGC 300 2008OT-1 with the Very Large Telescope equipped with UVES. Finally, we describe our analysis of late-time spectra of NGC 300 2008OT-1 and AT 2019ahd through comparisons with both synthetic and observed spectra. Results.Balmer and Ca lines dominate the optical spectra, revealing the presence of slowly moving circumstellar medium (CSM) around the objects. The line luminosity of Hα, Hβ, and Ca IINIR triplet presents a double peaked evolution with time, possibly indicative of interaction between fast ejecta and the slow CSM. The high-resolution spectrum of NGC 300 2008OT-1 reveals a complex circumstellar environment, with the transient being surrounded by a slow (∼30 km s⁻¹) progenitor wind. At late epochs, optical spectra of NGC 300 2008OT-1 and AT 2019ahd show broad (∼2500 km s⁻¹) emission features at ∼6170 Å and ∼7000 Å which are unprecedented for ILRTs. We find that these lines originate most likely from the blending of several narrow lines, possibly of iron-peak elements. 

Abstract The plate tectonic cycle produces chemically distinct mid-ocean ridge basalts and arc volcanics, with the latter enriched in elements such as Ba, Rb, Th, Sr and Pb and depleted in Nb owing to the water-rich flux from the subducted slab. Basalts from back-arc basins, with intermediate compositions, show that such a slab flux can be transported behind the volcanic front of the arc and incorporated into mantle flow. Hence it is puzzling why melts of subduction-modified mantle have rarely been recognized in mid-ocean ridge basalts. Here we report the first mid-ocean ridge basalt samples with distinct arc signatures, akin to back-arc basin basalts, from the Arctic Gakkel Ridge. A new high precision dataset for 576 Gakkel samples suggests a pervasive subduction influence in this region. This influence can also be identified in Atlantic and Indian mid-ocean ridge basalts but is nearly absent in Pacific mid-ocean ridge basalts. Such a hemispheric-scale upper mantle heterogeneity reflects subduction modification of the asthenospheric mantle which is incorporated into mantle flow, and whose geographical distribution is controlled dominantly by a “subduction shield” that has surrounded the Pacific Ocean for 180 Myr. Simple modeling suggests that a slab flux equivalent to ~13% of the output at arcs is incorporated into the convecting upper mantle. 

We study gains from trade in multi-dimensional two-sided markets. Specifically, we focus on a setting with n heterogeneous items, where each item is owned by a different seller i, and there is a constrained-additive buyer with feasibility constraint ℱ. Multi-dimensional settings in one-sided markets, e.g. where a seller owns multiple heterogeneous items but also is the mechanism designer, are well-understood. In addition, single-dimensional settings in two-sided markets, e.g. where a buyer and seller each seek or own a single item, are also well-understood. Multi-dimensional two-sided markets, however, encapsulate the major challenges of both lines of work: optimizing the sale of heterogeneous items, ensuring incentive-compatibility among both sides of the market, and enforcing budget balance. We present, to the best of our knowledge, the first worst-case approximation guarantee for gains from trade in a multi-dimensional two-sided market. Our first result provides an O(log(1/r))-approximation to the first-best gains from trade for a broad class of downward-closed feasibility constraints (such as matroid, matching, knapsack, or the intersection of these). Here r is the minimum probability over all items that a buyer's value for the item exceeds the seller's cost. Our second result removes the dependence on r and provides an unconditional O(log n)-approximation to the second-best gains from trade. We extend both results for a general constrained-additive buyer, losing another O(log n)-factor en-route. The first result is achieved using a fixed posted price mechanism, and the analysis involves a novel application of the prophet inequality or a new concentration inequality. Our second result follows from a stitching lemma that allows us to upper bound the second-best gains from trade by the first-best gains from trade from the “likely to trade” items (items with trade probability at least 1/n) and the optimal profit from selling the “unlikely to trade” items. We can obtain an O(log n)-approximation to the first term by invoking our O(log(1/r))-approximation on the “likely to trade” items. We introduce a generalization of the fixed posted price mechanism—seller adjusted posted price—to obtain an O(log n)-approximation to the optimal profit for the “unlikely to trade” items. Unlike fixed posted price mechanisms, not all seller adjusted posted price mechanisms are incentive compatible and budget balanced. We develop a new argument based on “allocation coupling” to show the seller adjusted posted price mechanism used in our approximation is indeed budget balanced and incentive-compatible. 

ABSTRACT Photometric and spectroscopic data for two Low Luminosity Type IIP Supernovae (LL SNe IIP) 2020cxd and 2021aai are presented. SN 2020cxd was discovered 2 d after explosion at an absolute magnitude of Mr  = −14.02 ± 0.21 mag, subsequently settling on a plateau which lasts for ∼120 d. Through the luminosity of the late light curve tail, we infer a synthesized 56Ni mass of (1.8 ± 0.5) × 10−3 M⊙. During the early evolutionary phases, optical spectra show a blue continuum ($$T\, \gt $$8000 K) with broad Balmer lines displaying a P Cygni profile, while at later phases, Ca ii, Fe ii, Sc ii, and Ba ii lines dominate the spectra. Hydrodynamical modelling of the observables yields $$R\, \simeq$$ 575 R⊙ for the progenitor star, with Mej  = 7.5 M⊙ and $$E\, \simeq$$ 0.097 foe emitted during the explosion. This low-energy event originating from a low-mass progenitor star is compatible with both the explosion of a red supergiant (RSG) star and with an Electron Capture Supernova arising from a super asymptotic giant branch star. SN 2021aai reaches a maximum luminosity of Mr  = −16.57 ± 0.23 mag (correcting for AV = 1.92 mag), at the end of its remarkably long plateau (∼140 d). The estimated 56Ni mass is (1.4 ± 0.5) × 10−2 M⊙. The expansion velocities are compatible with those of other LL SNe IIP (few 103 km s−1). The physical parameters obtained through hydrodynamical modelling are $$R\, \simeq$$ 575 R⊙, Mej = 15.5 M⊙, and E = 0.4 foe. SN 2021aai is therefore interpreted as the explosion of an RSG, with properties that bridge the class of LL SNe IIP with standard SN IIP events.