Search

Quantum circuits with local unitaries have emerged as a rich playground for the exploration of many-body quantum dynamics of discrete-time systems. While the intrinsic locality makes them particularly suited to run on current quantum processors, the task of verification at non-trivial scales is complicated for non-integrable systems. Here, we study a special class of maximally chaotic circuits known as dual unitary circuits -- exhibiting unitarity in both space and time -- that are known to have exact analytical solutions for certain correlation functions. With advances in noise learning and the implementation of novel error mitigation methods, we show that a superconducting quantum processor with 91 qubits is able to accurately simulate these correlators. We then probe dynamics beyond exact verification, by perturbing the circuits away from the dual unitary point, and compare our results to classical approximations with tensor networks. These results cement error-mitigated digital quantum simulation on pre-fault-tolerant quantum processors as a trustworthy platform for the exploration and discovery of novel emergent quantum many-body phases., Comment: 7 + 23 pages, 3 + 17 figures, 0 + 2 tables

We aim to identify the spatial distribution of vegetation and its growth dynamics with the purpose of obtaining a qualitative assessment of vegetation characteristics tied to its condition, productivity and health, and to land degradation. To do so, we compare a statistical model of vegetation growth and land surface imagery derived vegetation indices. Specifically, we analyze a stochastic cellular automata model and data obtained from satellite images, namely using the Normalized Difference Vegetation Index (NDVI) and the Leaf Area Index (LAI). In the experimental data, we look for areas where vegetation is broken into small patches and qualitatively compare it to the percolating, fragmented, and degraded states that appear in the cellular automata model. We model the periodic effect of seasons, finding numerical evidence of a periodic fragmentation and recovery phenomenology if the model parameters are sufficiently close to the model's percolation transition. We qualitatively recognize these effects in real-world vegetation images and consider them a signal of increased environmental stress and vulnerability. Finally, we show an estimation of the environmental stress in land images by considering both the vegetation density and its clusterization., Comment: 17 pages, 18 figures, the published version

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<|P|$, requires to determine a subset $S$ of $k$ centers minimizing the sum of all squared distances of points in $P$ from their closest center. A more general formulation, known as k-means with $z$ outliers, introduced to deal with noisy datasets, features a further parameter $z$ and allows up to $z$ points of $P$ (outliers) to be disregarded when computing the aforementioned sum. We present a distributed coreset-based 3-round approximation algorithm for k-means with $z$ outliers for general metric spaces, using MapReduce as a computational model. Our distributed algorithm requires sublinear local memory per reducer, and yields a solution whose approximation ratio is an additive term $O(\gamma)$ away from the one achievable by the best known sequential (possibly bicriteria) algorithm, where $\gamma$ can be made arbitrarily small. An important feature of our algorithm is that it obliviously adapts to the intrinsic complexity of the dataset, captured by the doubling dimension $D$ of the metric space. To the best of our knowledge, no previous distributed approaches were able to attain similar quality-performance tradeoffs for general metrics.

Metric $k$-center clustering is a fundamental unsupervised learning primitive. Although widely used, this primitive is heavily affected by noise in the data, so that a more sensible variant seeks for the best solution that disregards a given number $z$ of points of the dataset, called outliers. We provide efficient algorithms for this important variant in the streaming model under the sliding window setting, where, at each time step, the dataset to be clustered is the window $W$ of the most recent data items. Our algorithms achieve $O(1)$ approximation and, remarkably, require a working memory linear in $k+z$ and only logarithmic in $|W|$. As a by-product, we show how to estimate the effective diameter of the window $W$, which is a measure of the spread of the window points, disregarding a given fraction of noisy distances. We also provide experimental evidence of the practical viability of our theoretical results.

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., Comment: 6+6 pages, 3+5 figures

Quantum dynamics on quasiperiodic geometries has recently gathered significant attention in ultra-cold atom experiments where non trivial localised phases have been observed. One such quasiperiodic model is the so called Fibonacci model. In this tight-binding model, non-interacting particles are subject to on-site energies generated by a Fibonacci sequence. This is known to induce critical states, with a continuously varying dynamical exponent, leading to anomalous transport. In this work, we investigate whether anomalous diffusion present in the non-interacting system survives in the presence of interactions and establish connections to a possible transition towards a localized phase. We investigate the dynamics of the interacting Fibonacci model by studying real-time spread of density-density correlations at infinite temperature using the dynamical typicality approach. We also corroborate our findings by calculating the participation entropy in configuration space and investigating the expectation value of local observables in the diagonal ensemble., Comment: 12 pages, 10 figures

We numerically study the possibility of many-body localization transition in a disordered quantum dimer model on the honeycomb lattice. By using the peculiar constraints of this model and state-of-the-art exact diagonalization and time evolution methods, we probe both eigenstates and dynamical properties and conclude on the existence of a localization transition, on the available time and length scales (system sizes of up to N=108 sites). We critically discuss these results and their implications., Comment: 26 pages, 16 figures. Revised version

The most widely used internal measure for clustering evaluation is the silhouette coefficient, whose naive computation requires a quadratic number of distance calculations, which is clearly unfeasible for massive datasets. Surprisingly, there are no known general methods to efficiently approximate the silhouette coefficient of a clustering with rigorously provable high accuracy. In this paper, we present the first scalable algorithm to compute such a rigorous approximation for the evaluation of clusterings based on any metric distances. Our algorithm hinges on a Probability Proportional to Size (PPS) sampling scheme, and, for any fixed $\varepsilon, \delta \in (0,1)$, it approximates the silhouette coefficient within a mere additive error $O(\varepsilon)$ with probability $1-\delta$, using a very small number of distance calculations. We also prove that the algorithm can be adapted to obtain rigorous approximations of other internal measures of clustering quality, such as cohesion and separation. Importantly, we provide a distributed implementation of the algorithm using the MapReduce model, which runs in constant rounds and requires only sublinear local space at each worker, which makes our estimation approach applicable to big data scenarios. We perform an extensive experimental evaluation of our silhouette approximation algorithm, comparing its performance to a number of baseline heuristics on real and synthetic datasets. The experiments provide evidence that, unlike other heuristics, our estimation strategy not only provides tight theoretical guarantees but is also able to return highly accurate estimations while running in a fraction of the time required by the exact computation, and that its distributed implementation is highly scalable, thus enabling the computation of internal measures for very large datasets for which the exact computation is prohibitive., Comment: 16 pages, 4 tables, 1 figure

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_i<1$ and the aggregate weight of the returned centers must be at most 1. We devise coreset-based strategies for the two problems which yield efficient sequential, MapReduce, and Streaming algorithms. More specifically, for any fixed $\epsilon>0$, 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\ll n$ "representatives" which minimize 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-\epsilon$ away from the optimal solution for $S$. While our algorithms are fully general, for the partition and transversal matroids, if $\epsilon$ 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.

The characterizing feature of a many-body localized phase is the existence of an extensive set of quasi-local conserved quantities with an exponentially localized support. This structure endows the system with the signature logarithmic in time entanglement growth between spatial partitions. This feature differentiates the phase from Anderson localization, in a non-interacting model. Experimentally measuring the entanglement between large partitions of an interacting many-body system requires highly non-local measurements which are currently beyond the reach of experimental technology. In this work we demonstrate that the defining structure of many-body localization can be detected by the dynamics of a simple quantity from quantum information known as the total correlations which is connected to the local entropies. Central to our finding is the necessity to propagate specific initial states, drawn from the Hamiltonian unbiased basis (HUB). The dynamics of the local entropies and total correlations requires only local measurements in space and therefore is potentially experimentally accessible in a range of platforms., Comment: 4 pages, 5 figures, comments are welcome

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., Comment: 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<|P|$, require to identify a set $S$ of $k$ centers minimizing, respectively, the sum of the distances and of the squared distances of all points in $P$ from their closest centers. Our specific focus is on general metric spaces, for which it is reasonable to require that the centers belong to the input set (i.e., $S \subseteq P$). We present coreset-based 3-round distributed approximation algorithms for the above problems using the MapReduce computational model. The algorithms are rather simple and obliviously adapt to the intrinsic complexity of the dataset, captured by the doubling dimension $D$ of the metric space. Remarkably, the algorithms attain approximation ratios that can be made arbitrarily close to those achievable by the best known polynomial-time sequential approximations, and they are very space efficient for small $D$, requiring local memory sizes substantially sublinear in the input size. To the best of our knowledge, no previous distributed approaches were able to attain similar quality-performance guarantees in general metric spaces.

We study the Anderson model on the Bethe lattice by working directly with propagators at real energies $E$. We introduce a novel criterion for the localization-delocalization transition based on the stability of the population of the propagators, and show that it is consistent with the one obtained through the study of the imaginary part of the self-energy. We present an accurate numerical estimate of the transition point, as well as a concise proof of the asymptotic formula for the critical disorder on lattices of large connectivity, as given in [P.W. Anderson 1958]. We discuss how the forward approximation used in analytic treatments of localization problems fits into this scenario and how one can interpolate between it and the correct asymptotic analysis., Comment: Close to published version

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

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=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.

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 $\epsilon>0$, the algorithms yield solutions whose approximation ratios are a mere additive term $\epsilon$ 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.

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.

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

We study the details of the distribution of the entanglement spectrum (eigenvalues of the reduced density matrix) of a disordered spin chain exhibiting a many-body localization (MBL) transition. In the thermalizing region we identify the evolution under increasing system size of the eigenvalues distribution function, whose thermodynamic limit is close (but possibly different from) the Marchenko-Pastur distribution. From the analysis we extract a correlation length $L_s(h)$ determining the minimum system size to enter the asymptotic region. We find that $L_s(h)$ diverges at the MBL transition. We discuss the nature of the subleading corrections to the entanglement spectrum distribution and to the entanglement entropy., Comment: 15 pages, 6 figures; close to published version

Given a dataset of points in a metric space and an integer $k$, a diversity maximization problem requires determining a subset of $k$ points maximizing some diversity objective measure, e.g., the minimum or the average distance between two points in the subset. Diversity maximization is computationally hard, hence only approximate solutions can be hoped for. Although its applications are mainly in massive data analysis, most of the past research on diversity maximization focused on the sequential setting. In this work we present space and pass/round-efficient diversity maximization algorithms for the Streaming and MapReduce models and analyze their approximation guarantees for the relevant class of metric spaces of bounded doubling dimension. Like other approaches in the literature, our algorithms rely on the determination of high-quality core-sets, i.e., (much) smaller subsets of the input which contain good approximations to the optimal solution for the whole input. For a variety of diversity objective functions, our algorithms attain an $(\alpha+\epsilon)$-approximation ratio, for any constant $\epsilon>0$, where $\alpha$ is the best approximation ratio achieved by a polynomial-time, linear-space sequential algorithm for the same diversity objective. This improves substantially over the approximation ratios attainable in Streaming and MapReduce by state-of-the-art algorithms for general metric spaces. We provide extensive experimental evidence of the effectiveness of our algorithms on both real world and synthetic datasets, scaling up to over a billion points., Comment: Extended version of http://www.vldb.org/pvldb/vol10/p469-ceccarello.pdf, PVLDB Volume 10, No. 5, January 2017

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., Comment: 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-) or many-body localized phase. This approximation, which consists in summing over the amplitudes of only the shortest paths in the locator expansion, is known to over-estimate 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\pm 0.3$ is strikingly close to the most recent results obtained by exact diagonalization. In both cases we obtain a critical exponent $\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.

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).

We investigate what happens if an Anderson localized system is coupled to a small bath, with a discrete spectrum, when the coupling between system and bath is specially chosen so as to never localize the bath. We find that the effect of the bath on localization in the system is a non-monotonic function of the coupling between system and bath. At weak couplings, the bath facilitates transport by allowing the system to 'borrow' energy from the bath. But above a certain coupling the bath produces localization, because of an orthogonality catastrophe, whereby the bath 'dresses' the system and hence suppresses the hopping matrix element. We call this last regime the regime of "Zeno-localization", since the physics of this regime is akin to the quantum Zeno effect, where frequent measurements of the position of a particle impede its motion. We confirm our results by numerical exact diagonalization.

We develop a novel parallel decomposition strategy for unweighted, undirected graphs, based on growing disjoint connected clusters from batches of centers progressively selected from yet uncovered nodes. With respect to similar previous decompositions, our strategy exercises a tighter control on both the number of clusters and their maximum radius. We present two important applications of our parallel graph decomposition: (1) $k$-center clustering approximation; and (2) diameter approximation. In both cases, we obtain algorithms which feature a polylogarithmic approximation factor and are amenable to a distributed implementation that is geared for massive (long-diameter) graphs. The total space needed for the computation is linear in the problem size, and the parallel depth is substantially sublinear in the diameter for graphs with low doubling dimension. To the best of our knowledge, ours are the first parallel approximations for these problems which achieve sub-diameter parallel time, for a relevant class of graphs, using only linear space. Besides the theoretical guarantees, our algorithms allow for a very simple implementation on clustered architectures: we report on extensive experiments which demonstrate their effectiveness and efficiency on large graphs as compared to alternative known approaches., Comment: 14 pages

A framework is proposed for the design and analysis of \emph{network-oblivious algorithms}, namely, algorithms that can run unchanged, yet efficiently, on a variety of machines characterized by different degrees of parallelism and communication capabilities. The framework prescribes that a network-oblivious algorithm be specified on a parallel model of computation where the only parameter is the problem's input size, and then evaluated on a model with two parameters, capturing parallelism granularity and communication latency. It is shown that, for a wide class of network-oblivious algorithms, optimality in the latter model implies optimality in the Decomposable BSP model, which is known to effectively describe a wide and significant class of parallel platforms. The proposed framework can be regarded as an attempt to port the notion of obliviousness, well established in the context of cache hierarchies, to the realm of parallel computation. Its effectiveness is illustrated by providing optimal network-oblivious algorithms for a number of key problems. Some limitations of the oblivious approach are also discussed., Comment: 34 pages

We present space-efficient parallel strategies for two fundamental combinatorial search problems, namely, backtrack search and branch-and-bound, both involving the visit of an $n$-node tree of height $h$ under the assumption that a node can be accessed only through its father or its children. For both problems we propose efficient algorithms that run on a $p$-processor distributed-memory machine. For backtrack search, we give a deterministic algorithm running in $O(n/p+h\log p)$ time, and a Las Vegas algorithm requiring optimal $O(n/p+h)$ time, with high probability. Building on the backtrack search algorithm, we also derive a Las Vegas algorithm for branch-and-bound which runs in $O((n/p+h\log p \log n)h\log^2 n)$ time, with high probability. A remarkable feature of our algorithms is the use of only constant space per processor, which constitutes a significant improvement upon previous algorithms whose space requirements per processor depend on the (possibly huge) tree to be explored., Comment: Extended version of the paper in the Proc. of 38th International Symposium on Mathematical Foundations of Computer Science (MFCS)

This work explores fundamental modeling and algorithmic issues arising in the well-established MapReduce framework. First, we formally specify a computational model for MapReduce which captures the functional flavor of the paradigm by allowing for a flexible use of parallelism. Indeed, the model diverges from a traditional processor-centric view by featuring parameters which embody only global and local memory constraints, thus favoring a more data-centric view. Second, we apply the model to the fundamental computation task of matrix multiplication presenting upper and lower bounds for both dense and sparse matrix multiplication, which highlight interesting tradeoffs between space and round complexity. Finally, building on the matrix multiplication results, we derive further space-round tradeoffs on matrix inversion and matching.

Motivated by the growing interest in mobile systems, we study the dynamics of information dissemination between agents moving independently on a plane. Formally, we consider $k$ mobile agents performing independent random walks on an $n$-node grid. At time $0$, each agent is located at a random node of the grid and one agent has a rumor. The spread of the rumor is governed by a dynamic communication graph process ${G_t(r) | t \geq 0}$, where two agents are connected by an edge in $G_t(r)$ iff their distance at time $t$ is within their transmission radius $r$. Modeling the physical reality that the speed of radio transmission is much faster than the motion of the agents, we assume that the rumor can travel throughout a connected component of $G_t$ before the graph is altered by the motion. We study the broadcast time $T_B$ of the system, which is the time it takes for all agents to know the rumor. We focus on the sparse case (below the percolation point $r_c \approx \sqrt{n/k}$) where, with high probability, no connected component in $G_t$ has more than a logarithmic number of agents and the broadcast time is dominated by the time it takes for many independent random walks to meet each other. Quite surprisingly, we show that for a system below the percolation point the broadcast time does not depend on the relation between the mobility speed and the transmission radius. In fact, we prove that $T_B = \tilde{O}(n / \sqrt{k})$ for any $0 \leq r < r_c$, even when the transmission range is significantly larger than the mobility range in one step, giving a tight characterization up to logarithmic factors. Our result complements a recent result of Peres et al. (SODA 2011) who showed that above the percolation point the broadcast time is polylogarithmic in $k$., Comment: 19 pages; we rewrote Lemma 4, fixing a claim which was not fully justified in the first version of the draft

We study the dynamics of information (or virus) dissemination by $m$ mobile agents performing independent random walks on an $n$-node grid. We formulate our results in terms of two scenarios: broadcasting and gossiping. In the broadcasting scenario, the mobile agents are initially placed uniformly at random among the grid nodes. At time 0, one agent is informed of a rumor and starts a random walk. When an informed agent meets an uninformed agent, the latter becomes informed and starts a new random walk. We study the broadcasting time of the system, that is, the time it takes for all agents to know the rumor. In the gossiping scenario, each agent is given a distinct rumor at time 0 and all agents start random walks. When two agents meet, they share all rumors they are aware of. We study the gossiping time of the system, that is, the time it takes for all agents to know all rumors. We prove that both the broadcasting and the gossiping times are $\tilde\Theta(n/\sqrt{m})$ w.h.p., thus achieving a tight characterization up to logarithmic factors. Previous results for the grid provided bounds which were weaker and only concerned average times. In the context of virus infection, a corollary of our results is that static and dynamically moving agents are infected at about the same speed., Comment: 21 pages, 3 figures --- The results presented in this paper have been extended in: Pettarin et al., Tight Bounds on Information Dissemination in Sparse Mobile Networks, http://arxiv.org/abs/1101.4609

We study the use of sampling for efficiently mining the top-K frequent itemsets of cardinality at most w. To this purpose, we define an approximation to the top-K frequent itemsets to be a family of itemsets which includes (resp., excludes) all very frequent (resp., very infrequent) itemsets, together with an estimate of these itemsets' frequencies with a bounded error. Our first result is an upper bound on the sample size which guarantees that the top-K frequent itemsets mined from a random sample of that size approximate the actual top-K frequent itemsets, with probability larger than a specified value. We show that the upper bound is asymptotically tight when w is constant. Our main algorithmic contribution is a progressive sampling approach, combined with suitable stopping conditions, which on appropriate inputs is able to extract approximate top-K frequent itemsets from samples whose sizes are smaller than the general upper bound. In order to test the stopping conditions, this approach maintains the frequency of all itemsets encountered, which is practical only for small w. However, we show how this problem can be mitigated by using a variation of Bloom filters. A number of experiments conducted on both synthetic and real bench- mark datasets show that using samples substantially smaller than the original dataset (i.e., of size defined by the upper bound or reached through the progressive sampling approach) enable to approximate the actual top-K frequent itemsets with accuracy much higher than what analytically proved., Comment: 16 pages, 2 figures, accepted for presentation at ECML PKDD 2010 and publication in the ECML PKDD 2010 special issue of the Data Mining and Knowledge Discovery journal

As an emerging field, MS-based proteomics still requires software tools for efficiently storing and accessing experimental data. In this work, we focus on the management of LC-MS data, which are typically made available in standard XML-based portable formats. The structures that are currently employed to manage these data can be highly inefficient, especially when dealing with high-throughput profile data. LC-MS datasets are usually accessed through 2D range queries. Optimizing this type of operation could dramatically reduce the complexity of data analysis. We propose a novel data structure for LC-MS datasets, called mzRTree, which embodies a scalable index based on the R-tree data structure. mzRTree can be efficiently created from the XML-based data formats and it is suitable for handling very large datasets. We experimentally show that, on all range queries, mzRTree outperforms other known structures used for LC-MS data, even on those queries these structures are optimized for. Besides, mzRTree is also more space efficient. As a result, mzRTree reduces data analysis computational costs for very large profile datasets., Comment: Paper details: 10 pages, 7 figures, 2 tables. To be published in Journal of Proteomics. Source code available at http://www.dei.unipd.it/mzrtree

As advances in technology allow for the collection, storage, and analysis of vast amounts of data, the task of screening and assessing the significance of discovered patterns is becoming a major challenge in data mining applications. In this work, we address significance in the context of frequent itemset mining. Specifically, we develop a novel methodology to identify a meaningful support threshold s* for a dataset, such that the number of itemsets with support at least s* represents a substantial deviation from what would be expected in a random dataset with the same number of transactions and the same individual item frequencies. These itemsets can then be flagged as statistically significant with a small false discovery rate. We present extensive experimental results to substantiate the effectiveness of our methodology., Comment: A preliminary version of this work was presented in ACM PODS 2009. 20 pages, 0 figures