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. 

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. 

Abstract New phases of matter emerge at the edge of magnetic instabilities, which can occur in materials with moments that are localized, itinerant or intermediate between these extremes. In local moment systems, such as heavy fermions, the magnetism can be tuned towards a zero-temperature transition at a quantum critical point (QCP) via pressure, chemical doping, and, rarely, magnetic field. By contrast, in itinerant moment systems, QCPs are more rare, and they are induced by pressure or doping; there are no known examples of field induced transitions. This means that no universal behaviour has been established across the whole itinerant-to-local moment range—a substantial gap in our knowledge of quantum criticality. Here we report an itinerant antiferromagnet, Ti₃Cu₄, that can be tuned to a QCP by a small magnetic field. We see signatures of quantum criticality and the associated non-Fermi liquid behaviour in thermodynamic and transport measurements, while band structure calculations point to an orbital-selective, spin density wave ground state, a consequence of the square net structural motif in Ti₃Cu₄. Ti₃Cu₄thus provides a platform for the comparison and generalisation of quantum critical behaviour across the whole spectrum of magnetism.