Search Results for « Soft Heaps »

We investigate binary mixtures of large colloids interacting through soft potentials with small, ideal depletants. We show that softness has a dramatic effect on the resulting colloid-colloid effective potential when the depletant-to-colloid size ratio $q$ is small, with significant consequences on the colloidal phase behaviour. We also provide an exact relation that allows us to obtain the effective pair potential for {\it any} type of colloid-depletant interactions in the case of ideal depletants, without having to rely on complicated and expensive full-mixture simulations. We also show that soft repulsion among depletants further enhances the tendency of colloids to aggregate. Our theoretical and numerical results demonstrate that --- in the limit of small $q$ --- soft mixtures cannot be mapped onto hard systems and hence soft depletion is not a mere extension of the widely used Asakura-Oosawa potential.

A simple variant of a priority queue, called a soft heap , is introduced. The data structure supports the usual operations: insert, delete, meld, and findmin. Its novelty is to beat the logarithmic bound on the complexity of a heap in a comparison-based model. To break this information-theoretic barrier, the entropy of the data structure is reduced by artifically raising the values of certain keys. Given any mixed sequence of n operations, a soft heap with error rate ε (for any 0 < ε ≤ 1/2) ensures that, at any time, at most εn of its items have their keys raised. The amortized complexity of each operation is constant, except for insert, which takes 0 (log 1/ε)time. The soft heap is optimal for any value of ε in a comparison-based model. The data structure is purely pointer-based. No arrays are move items across the data structure not individually, as is customary, but in groups, in a data-structuring equivalent of “car pooling.” Keys must be raised as a result, in order to preserve the heap ordering of the data structure. The soft heap can be used to compute exact or approximate medians and percentiles optimally. It is also useful for approximate sorting and for computing minimum spanning trees of general graphs.

Using a thermodynamical approach, we calculate the deformation of a spherical elastic particle placed on a rigid substrate, under zero external load, and including an ingredient of importance in soft matter: the interfacial tension of the cap. In a first part, we limit the study to small deformation. In contrast with previous works, we obtain an expression for the energy that precisely contains the JKR and Young-Dupré asymptotic regimes, and which establishes a continuous bridge between them. In a second part, we consider the large deformation case, which is relevant for future comparison with numerical simulations and experiments on very soft materials. Using a fruitful analogy with fracture mechanics, we derive the exact energy of the problem and thus obtain the equilibrium state for any given choice of physical parameters.

We use soft heaps to obtain simpler optimal algorithms for selecting the $k$-th smallest item, and the set of~$k$ smallest items, from a heap-ordered tree, from a collection of sorted lists, and from $X+Y$, where $X$ and $Y$ are two unsorted sets. Our results match, and in some ways extend and improve, classical results of Frederickson (1993) and Frederickson and Johnson (1982). In particular, for selecting the $k$-th smallest item, or the set of~$k$ smallest items, from a collection of~$m$ sorted lists we obtain a new optimal "output-sensitive" algorithm that performs only $O(m+\sum_{i=1}^m \log(k_i+1))$ comparisons, where $k_i$ is the number of items of the $i$-th list that belong to the overall set of~$k$ smallest items.

Solids deform and fluids flow, but soft glassy materials, such as emulsions, foams, suspensions, and pastes, exhibit an intricate mix of solid and liquid-like behavior. While much progress has been made to understand their elastic (small strain) and flow (infinite strain) properties, such understanding is lacking for the softening and yielding phenomena that connect these asymptotic regimes. Here we present a comprehensive framework for softening and yielding of soft glassy materials, based on extensive numerical simulations of oscillatory rheological tests, and show that two distinct scenarios unfold depending on the material's packing density. For dense systems, there is a single, pressure-independent strain where the elastic modulus drops and the particle motion becomes diffusive. In contrast, for weakly jammed systems, a two-step process arises: at an intermediate softening strain, the elastic and loss moduli both drop down and then reach a new plateau value, whereas the particle motion becomes diffusive at the distinctly larger yield strain. We show that softening is associated with an extensive number of microscopic contact changes leading to a non-analytic rheological signature. Moreover, the scaling of the softening strain with pressure suggest the existence of a novel pressure scale above which softening and yielding coincide, and we verify the existence of this crossover scale numerically. Our findings thus evidence the existence of two distinct classes of soft glassy materials -- jamming dominated and dense -- and show how these can be distinguished by their rheological fingerprint.

We consider word RAM data structures for maintaining ordered sets of integers whose select and rank operations are allowed to return approximate results, i.e., ranks, or items whose rank, differ by less than Delta from the exact answer, where Delta=Delta(n) is an error parameter. Related to approximate select and rank is approximate (one-dimensional) nearest-neighbor. A special case of approximate select queries are approximate min queries. Data structures that support approximate min operations are known as approximate heaps (priority queues). Related to approximate heaps are soft heaps, which are approximate heaps with a different notion of approximation. We prove the optimality of all the data structures presented, either through matching cell-probe lower bounds, or through equivalences to well studied static problems. For approximate select, rank, and nearest-neighbor operations we get matching cell-probe lower bounds. We prove an equivalence between approximate min operations, i.e., approximate heaps, and the static partitioning problem. Finally, we prove an equivalence between soft heaps and the classical sorting problem, on a smaller number of items. Our results have many interesting and unexpected consequences. It turns out that approximation greatly speeds up some of these operations, while others are almost unaffected. In particular, while select and rank have identical operation times, both in comparison-based and word RAM implementations, an interesting separation emerges between the approximate versions of these operations in the word RAM model. Approximate select is much faster than approximate rank. It also turns out that approximate min is exponentially faster than the more general approximate select. Next, we show that implementing soft heaps is harder than implementing approximate heaps. The relation between them corresponds to the relation between sorting and partitioning. Finally, as an interesting byproduct, we observe that a combination of known techniques yields a deterministic word RAM algorithm for (exactly) sorting n items in O(n log log_w n) time, where w is the word length. Even for the easier problem of finding duplicates, the best previous deterministic bound was O(min{n log log n,n log_w n}). Our new unifying bound is an improvement when w is sufficiently large compared with n.

Effective pair interactions with a soft-repulsive component are a well-known feature of polymer solutions and colloidal suspensions, but they also provide a key to interpret the high-pressure behaviour of simple elements. We have computed the zero-temperature phase diagram of four different model potentials with various degrees of core softness. Among the reviewed crystal structures, there are also a number of non-Bravais lattices, chosen among those observed in real systems. Some of these crystals are indeed found to be stable for the selected potentials. We recognize an apparently universal trend for unbounded potentials, going from high- to low-coordinated crystal phases and back upon increasing the pressure. Conversely, a bounded repulsion may lead to intermittent appearance of compact structures with compression and no eventual settling down in a specific phase. In both cases, the fluid phase repeatedly reenters at intermediate pressures, as suggested by a cell-theory treatment of the solids. These findings are of relevance for soft matter in general, but they also offer fresh insight into the mechanisms subtended to solid polymorphism in elemental substances.

Chazelle [8] introduced the soft heap as a building block for efficient minimum spanning tree algorithms, and recently Kaplan et al. [12] showed how soft heaps can be applied to achieve simpler algorithms for various selection problems. A soft heap trades-off accuracy for efficiency by allowing ∊N of the items in a heap to be corrupted after a total of N insertions, where a corrupted item is an item with artificially increased key and is a fixed error parameter. Chazelle's soft heaps are based on binomial trees and support insertions in amortized time and extract-min operations in amortized O(1) time. In this paper we explore the design space of soft heaps. The main contribution of this paper is an alternative soft heap implementation based on merging sorted sequences, with time bounds matching those of Chazelle's soft heaps. We also discuss a variation of the soft heap by Kaplan et al. [13], where we avoid performing insertions lazily. It is based on ternary trees instead of binary trees and matches the time bounds of Kaplan et al., i.e. amortized O(1) insertions and amortized extract-min. Both our data structures only introduce corruptions after extract-min operations which return the set of items corrupted by the operation.

We use the hyper-netted chain approximation of liquid state theory to analyze the evolution with density of the pair correlation function in a model of soft spheres with harmonic repulsion. As observed in recent experiments on jammed soft particles, theory predicts an `anomalous' (nonmonotonic) evolution of the intensity of the first peak when density is increased at constant temperature. This structural anomaly is a direct consequence of particle softness, and can be explained from purely equilibrium considerations, emphasizing the generality of the phenomenon. This anomaly is also predicted to have a non-trivial, `${\cal S}$-shaped', evolution with temperature, as a result of a competition between three distinct effects, which we describe in detail. Computer simulations support our predictions.

Heaps (priority queues) are among the best-studied data structures in computer science. In this paper, we critically revisit the textbook assumption that in the comparison model at least one of the two standard heap operations of inserting an element and deleting the minimum must take logarithmic time. By decoupling the deletion itself from the act of revealing the identity of the deleted element to the user, we avoid the sorting barrier and obtain a novel trade-off between the complexities of heap operations. This shows that the logarithmic barrier is not inherently the cost of deleting the minimum but rather the information cost of immediately learning which element was deleted. In the special case when the user inspects the heap state only constantly many times, we show that both insertions and deletions can be supported in constant amortized time. As an application, this yields a runtime improvement from $\mathcal{O}(n \log n)$ to the optimal $\mathcal{O}(n)$ for a textbook unit-time scheduling problem. We obtain our results by designing a new data structure, the sync heap, which gains speed by rearranging and compacting its operations until queries force it to synchronize and reveal its state. As a key component, we use the soft heap introduced by Chazelle as part of his minimum spanning tree algorithm. Our data structure is simple, comparison-based, and deterministic, and our results are asymptotically optimal.