Search

We present approximation algorithms for some variants of center-based clustering and related problems in the fully dynamic setting, where the pointset evolves through an arbitrary sequence of insertions and deletions. Specifically, we target the following problems: $k$-center (with and without outliers), matroid-center, and diversity maximization. All algorithms employ a coreset-based strategy and rely on the use of the cover tree data structure, which we crucially augment to maintain, at any time, some additional information enabling the efficient extraction of the solution for the specific problem. For all of the aforementioned problems our algorithms yield $(\alpha+\varepsilon)$-approximations, where $\alpha$ is the best known approximation attainable in polynomial time in the standard off-line setting (except for $k$-center with $z$ outliers where $\alpha = 2$ but we get a $(3+\varepsilon)$-approximation) and $\varepsilon>0$ is a user-provided accuracy parameter. The analysis of the algorithms is performed in terms of the doubling dimension of the underlying metric. Remarkably, and unlike previous works, the data structure and the running times of the insertion and deletion procedures do not depend in any way on the accuracy parameter $\varepsilon$ and, for the two $k$-center variants, on the parameter $k$. For spaces of bounded doubling dimension, the running times are dramatically smaller than those that would be required to compute solutions on the entire pointset from scratch. To the best of our knowledge, ours are the first solutions for the matroid-center and diversity maximization problems in the fully dynamic setting.

Center-based clustering is a pivotal primitive for unsupervised learning and data analysis. A popular variant is undoubtedly the k-means problem, which, given a set $P$ of points from a metric space and a parameter $k

In this paper we present novel streaming algorithms for the k-center and the diameter estimation problems for general metric spaces under the sliding window model. The key idea behind our algorithms is to maintain a small coreset which, at any time, allows to compute a solution to the problem under consideration for the current window, whose quality can be made arbitrarily close to the one of the best solution attainable by running a polynomial-time sequential algorithm on the entire window. Remarkably, the size of our coresets is independent of the window length and can be upper bounded by a function of the target number of centers (for the k-center problem), of the desired accuracy, and of the characteristics of the current window, namely its doubling dimension and aspect ratio. One of the major strengths of our algorithms is that they adapt obliviously to these two latter characteristics. We also provide experimental evidence of the practical viability of the algorithms and their superiority over the current state of the art.

Recent experimental observation of weak ergodicity breaking in Rydberg atom quantum simulators has sparked interest in quantum many-body scars - eigenstates which evade thermalisation at finite energy densities due to novel mechanisms that do not rely on integrability or protection by a global symmetry. A salient feature of some quantum many-body scars is their sub-volume bipartite entanglement entropy. In this work we demonstrate that such exact many-body scars also possess extensive multipartite entanglement structure if they stem from an su(2) spectrum generating algebra. We show this analytically, through scaling of the quantum Fisher information, which is found to be super-extensive for exact scarred eigenstates in contrast to generic thermal states. Furthermore, we numerically study signatures of multipartite entanglement in the PXP model of Rydberg atoms, showing that extensive quantum Fisher information density can be generated dynamically by performing a global quench experiment. Our results identify a rich multipartite correlation structure of scarred states with significant potential as a resource in quantum enhanced metrology., 6+6 pages, 3+5 figures

Given a dataset $V$ of points from some metric space, the popular $k$-center problem requires to identify a subset of $k$ points (centers) in $V$ minimizing the maximum distance of any point of $V$ from its closest center. The \emph{robust} formulation of the problem features a further parameter $z$ and allows up to $z$ points of $V$ (outliers) to be disregarded when computing the maximum distance from the centers. In this paper, we focus on two important constrained variants of the robust $k$-center problem, namely, the Robust Matroid Center (RMC) problem, where the set of returned centers are constrained to be an independent set of a matroid of rank $k$ built on $V$, and the Robust Knapsack Center (RKC) problem, where each element $i\in V$ is given a positive weight $w_i0$, the algorithms return solutions featuring a $(3+\epsilon)$-approximation ratio, which is a mere additive term $\epsilon$ away from the 3-approximations achievable by the best known polynomial-time sequential algorithms for the two problems. Moreover, the algorithms obliviously adapt to the intrinsic complexity of the dataset, captured by its doubling dimension $D$. For wide ranges of the parameters $k,z,\epsilon, D$, we obtain a sequential algorithm with running time linear in $|V|$, and MapReduce/Streaming algorithms with few rounds/passes and substantially sublinear local/working memory., Comment: 16 pages

Diversity maximization is a fundamental problem in web search and data mining. For a given dataset S of n elements, the problem requires to determine a subset of S containing k ≪ n “representatives” which maximize some diversity function expressed in terms of pairwise distances, where distance models dissimilarity. An important variant of the problem prescribes that the solution satisfy an additional orthogonal requirement, which can be specified as a matroid constraint (i.e., a feasible solution must be an independent set of size k of a given matroid). While unconstrained diversity maximization admits efficient coreset-based strategies for several diversity functions, known approaches dealing with the additional matroid constraint apply only to one diversity function (sum of distances), and are based on an expensive, inherently sequential, local search over the entire input dataset. We devise the first coreset-based algorithms for diversity maximization under matroid constraints for various diversity functions, together with efficient sequential, MapReduce, and Streaming implementations. Technically, our algorithms rely on the construction of a small coreset, that is, a subset of S containing a feasible solution which is no more than a factor 1−ɛ away from the optimal solution for S . While our algorithms are fully general, for the partition and transversal matroids, if ɛ is a constant in (0,1) and S has bounded doubling dimension, the coreset size is independent of n and it is small enough to afford the execution of a slow sequential algorithm to extract a final, accurate, solution in reasonable time. Extensive experiments show that our algorithms are accurate, fast, and scalable, and therefore they are capable of dealing with the large input instances typical of the big data scenario.

Investigating many-body localization (MBL) using exact numerical methods is limited by the exponentialgrowth of the Hilbert space. However, localized eigenstates display multifractality and only extend over a vanishing fraction of the Hilbert space. Here, building on this remarkable property, we develop a simple yet efficient decimation scheme to discard the irrelevant parts of the Hilbert space of the random-field Heisenberg chain. This leads to an Hilbert space fragmentation in small clusters, allowing to access larger systems at strong disorder. The MBL transition is quantitatively predicted, together with a geometrical interpretation of MBL multifractality as a shattering of the Hilbert space., Special Issue of the Annals of Physics, Localisation 2020, dedicated to Philip W. Anderson

Center-based clustering is a fundamental primitive for data analysis and becomes very challenging for large datasets. In this paper, we focus on the popular $k$-median and $k$-means variants which, given a set $P$ of points from a metric space and a parameter $k

Center-based clustering is a fundamental primitive for data analysis and becomes very challenging for large datasets. In this paper, we focus on the popular k-center variant which, given a set S of points from some metric space and a parameter k < |S|, requires to identify a subset of k centers in S minimizing the maximum distance of any point of S from its closest center. A more general formulation, introduced to deal with noisy datasets, features a further parameter z and allows up to z points of S (outliers) to be disregarded when computing the maximum distance from the centers. We present coreset-based 2-round MapReduce algorithms for the above two formulations of the problem, and a 1-pass Streaming algorithm for the case with outliers. For any fixed ϵ > 0, the algorithms yield solutions whose approximation ratios are a mere additive term ϵ away from those achievable by the best known polynomial-time sequential algorithms, a result that substantially improves upon the state of the art. Our algorithms are rather simple and adapt to the intrinsic complexity of the dataset, captured by the doubling dimension D of the metric space. Specifically, our analysis shows that the algorithms become very space-efficient for the important case of small (constant) D. These theoretical results are complemented with a set of experiments on real-world and synthetic datasets of up to over a billion points, which show that our algorithms yield better quality solutions over the state of the art while featuring excellent scalability, and that they also lend themselves to sequential implementations much faster than existing ones

We provide a pedagogical review on the calculation of highly excited eigenstates of disordered interacting quantum systems which can undergo a many-body localization (MBL) transition, using shift-invert exact diagonalization. We also provide an example code at https://bitbucket.org/dluitz/sinvert_mbl. Through a detailed analysis of the simulational parameters of the random field Heisenberg spin chain, we provide a practical guide on how to perform efficient computations. We present data for mid-spectrum eigenstates of spin chains of sizes up to L=26L=26. This work is also geared towards readers with interest in efficiency of parallel sparse linear algebra techniques that will find a challenging application in the MBL problem.

We propose a class of mean-field models for the isostatic transition of systems of soft spheres, in which the contact network is modeled as a random graph and each contact is associated to $d$ degrees of freedom. We study such models in the hypostatic, isostatic, and hyperstatic regimes. The density of states is evaluated by both the cavity method and exact diagonalization of the dynamical matrix. We show that the model correctly reproduces the main features of the density of states of real packings and, moreover, it predicts the presence of localized modes near the lower band edge. Finally, the behavior of the density of states $D(\omega)\sim\omega^\alpha$ for $\omega\to 0$ in the hyperstatic regime is studied. We find that the model predicts a nontrivial dependence of $\alpha$ on the details of the coordination distribution., Comment: 15 pages, 14 figures

Center-based clustering is a fundamental primitive for data analysis and becomes very challenging for large datasets. In this paper, we focus on the popular k -center variant which, given a set S of points from some metric space and a parameter k < | S |, requires to identify a subset of k centers in S minimizing the maximum distance of any point of S from its closest center. A more general formulation, introduced to deal with noisy datasets, features a further parameter z and allows up to z points of S (outliers) to be disregarded when computing the maximum distance from the centers. We present coreset-based 2-round MapReduce algorithms for the above two formulations of the problem, and a 1-pass Streaming algorithm for the case with outliers. For any fixed ϵ > 0, the algorithms yield solutions whose approximation ratios are a mere additive term ϵ away from those achievable by the best known polynomial-time sequential algorithms, a result that substantially improves upon the state of the art. Our algorithms are rather simple and adapt to the intrinsic complexity of the dataset, captured by the doubling dimension D of the metric space. Specifically, our analysis shows that the algorithms become very space-efficient for the important case of small (constant) D . These theoretical results are complemented with a set of experiments on real-world and synthetic datasets of up to over a billion points, which show that our algorithms yield better quality solutions over the state of the art while featuring excellent scalability, and that they also lend themselves to sequential implementations much faster than existing ones.

Max-sum diversity is a fundamental primitive for web search and data mining. For a given set S of n elements, it returns a subset of k«l n representatives maximizing the sum of their pairwise distances, where distance models dissimilarity. An important variant of the primitive prescribes that the desired subset of representatives satisfies an additional orthogonal requirement, which can be specified as a matroid constraint (i.e., a feasible solution must be an independent set of size k). While unconstrained max-sum diversity admits efficient coreset-based strategies, the only known approaches dealing with the additional matroid constraint are inherently sequential and are based on an expensive local search over the entire input set. We devise the first coreset constructions for max-sum diversity under various matroid constraints, together with efficient sequential, MapReduce and Streaming implementations. By running the local-search on the coreset rather than on the entire input, we obtain the first practical solutions for large instances. Technically, our coresets are subsets of S containing a feasible solution which is no more than a factor 1-e away from the optimal solution, for any fixed e n. Extensive experiments show that, with respect to full-blown local search, our coreset-based approach yields solutions of comparable quality, with improvements of up to two orders of magnitude in the running time, also for input sets of unknown dimensionality.

The diagonal ensemble is the infinite time average of a quantum state following unitary dynamics. In analogy to the time average of a classical phase space dynamics, it is intimately related to the ergodic properties of the quantum system giving information on the spreading of the initial state in the eigenstates of the Hamiltonian. In this work we apply a concept from quantum information, known as total correlations, to the diagonal ensemble. Forming an upper-bound on the multipartite entanglement, it quantifies the combination of both classical and quantum correlations in a mixed state. We generalize the total correlations of the diagonal ensemble to more general $\alpha$-Renyi entropies and focus on the the cases $\alpha=1$ and $\alpha=2$ with further numerical extensions in mind. Here we show that the total correlations of the diagonal ensemble is a generic indicator of ergodicity breaking, displaying a sub-extensive behaviour when the system is ergodic. We demonstrate this by investigating its scaling in a range of spin chain models focusing not only on the cases of integrability breaking but also emphasize its role in understanding the transition from an ergodic to a many body localized phase in systems with disorder or quasi-periodicity., Comment: v3: several minor improvements

An uncertain graph $\mathcal{G} = (V, E, p : E \rightarrow (0,1])$ can be viewed as a probability space whose outcomes (referred to as \emph{possible worlds}) are subgraphs of $\mathcal{G}$ where any edge $e\in E$ occurs with probability $p(e)$, independently of the other edges. These graphs naturally arise in many application domains where data management systems are required to cope with uncertainty in interrelated data, such as computational biology, social network analysis, network reliability, and privacy enforcement, among the others. For this reason, it is important to devise fundamental querying and mining primitives for uncertain graphs. This paper contributes to this endeavor with the development of novel strategies for clustering uncertain graphs. Specifically, given an uncertain graph $\mathcal{G}$ and an integer $k$, we aim at partitioning its nodes into $k$ clusters, each featuring a distinguished center node, so to maximize the minimum/average connection probability of any node to its cluster's center, in a random possible world. We assess the NP-hardness of maximizing the minimum connection probability, even in the presence of an oracle for the connection probabilities, and develop efficient approximation algorithms for both problems and some useful variants. Unlike previous works in the literature, our algorithms feature provable approximation guarantees and are capable to keep the granularity of the returned clustering under control. Our theoretical findings are complemented with several experiments that compare our algorithms against some relevant competitors, with respect to both running-time and quality of the returned clusterings.

We present a space and time efficient practical parallel algorithm for approximating the diameter of massive weighted undirected graphs on distributed platforms supporting a MapReduce-like abstraction. The core of the algorithm is a weighted graph decomposition strategy generating disjoint clusters of bounded weighted radius. Theoretically, our algorithm uses linear space and yields a polylogarithmic approximation guarantee; moreover, for important practical classes of graphs, it runs in a number of rounds asymptotically smaller than those required by the natural approximation provided by the state-of-the-art $\Delta$-stepping SSSP algorithm, which is its only practical linear-space competitor in the aforementioned computational scenario. We complement our theoretical findings with an extensive experimental analysis on large benchmark graphs, which demonstrates that our algorithm attains substantial improvements on a number of key performance indicators with respect to the aforementioned competitor, while featuring a similar approximation ratio (a small constant less than 1.4, as opposed to the polylogarithmic theoretical bound).

The phenomenon of many-body localization in disordered quantum many-body systems occurs when all transport is suppressed despite the fact that the excitations of the system interact. In this work we report on the numerical simulation of autonomous quantum dynamics for disordered Heisenberg chains when the system is prepared with an initial inhomogeneity in the energy density profile. Using exact diagonalisation and a dynamical code based on Krylov subspaces we are able to simulate dynamics for up to L = 26 spins. We find, surprisingly, the breakdown of energy diffusion even before the many-body localization transition whilst the system is still in the ergodic phase. Moreover, in the ergodic phase we also find a large region in parameter space where the energy dynamics remains diffusive but where spin transport has been previously evidenced to occur only subdiffusively: this is found to be true for initial states composed of infinitely many hydrodynamic modes (square-wave energy profile) or just the single longest mode (sinusoidal profile). This suggestive finding points towards a peculiar ergodic phase where particles are transported slower than energy, reminiscent of the situation in amorphous solids and of the gapped phase of the anisotropic Heisenberg model., 17 pages, 6 figures, Published version

In this paper we analyze the predictions of the forward approximation in some models which exhibit an Anderson (single-body) or many-body localized phase. This approximation, which consists of summing over the amplitudes of only the shortest paths in the locator expansion, is known to overestimate the critical value of the disorder which determines the onset of the localized phase. Nevertheless, the results provided by the approximation become more and more accurate as the local coordination (dimensionality) of the graph, defined by the hopping matrix, is made larger. In this sense, the forward approximation can be regarded as a mean-field theory for the Anderson transition in infinite dimensions. The sum can be efficiently computed using transfer matrix techniques, and the results are compared with the most precise exact diagonalization results available. For the Anderson problem, we find a critical value of the disorder which is $0.9%$ off the most precise available numerical value already in 5 spatial dimensions, while for the many-body localized phase of the Heisenberg model with random fields the critical disorder ${h}_{c}=4.0\ifmmode\pm\else\textpm\fi{}0.3$ is strikingly close to the most recent results obtained by exact diagonalization. In both cases we obtain a critical exponent $\ensuremath{\nu}=1$. In the Anderson case, the latter does not show dependence on the dimensionality, as it is common within mean-field approximations. We discuss the relevance of the correlations between the shortest paths for both the single- and many-body problems, and comment on the connections of our results with the problem of directed polymers in random medium.