Memory efficiency and locality have substantial impact on the performance of programs, particularly when operating on large data sets. Thus, memory- or I/O-efficient algorithms have received significant attention both in theory and practice. The widespread deployment of multicore machines, however, brings new challenges. Specifically, since the memory (RAM) is shared across multiple processes, the effective memory-size allocated to each process fluctuates over time. This paper presents techniques for designing and analyzing algorithms in a cache-adaptive setting, where the RAM available to the algorithm changes over time. These techniques make analyzing algorithms in the cache-adaptive model almost as easy as in the external memory, or DAM model. Our techniques enable us to analyze a wide variety of algorithms --- Master-Method-style algorithms, Akra-Bazzi-style algorithms, collections of mutually recursive algorithms, and algorithms, such as FFT, that break problems of size N into subproblems of size Theta(Nc).

Most B-tree articles assume that all N keys have the same size K , that f = B / K keys fit in a disk block, and therefore that the search cost is O (log f + 1 N ) block transfers. When keys have variable size, B-tree operations have no nontrivial performance guarantees, however. This article provides B-tree-like performance guarantees on dictionaries that contain keys of different sizes in a model in which keys must be stored and compared as opaque objects. The resulting atomic-key dictionaries exhibit performance bounds in terms of the average key size and match the bounds when all keys are the same size. Atomic-key dictionaries can be built with minimal modification to the B-tree structure, simply by choosing the pivot keys properly. This article describes both static and dynamic atomic-key dictionaries. In the static case, if there are N keys with average size K , the search cost is O (⌈ K / B ⌉log 1 + ⌈ B / K ⌉ N ) expected transfers. It is not possible to transform these expected bounds into worst-case bounds. The cost to build the tree is O ( NK ) operations and O ( NK/B ) transfers if all keys are presented in sorted order. If not, the cost is the sorting cost. For the dynamic dictionaries, the amortized cost to insert a key κ of arbitrary length at an arbitrary rank is dominated by the cost to search for κ. Specifically, the amortized cost to insert a key κ of arbitrary length and random rank is O (⌈ K / B ⌉log 1 + ⌈ B / K ⌉ N + |κ|/ B ) transfers. A dynamic-programming algorithm is shown for constructing a search tree with minimal expected cost. This article also gives a cache-oblivious static atomic-key B-tree, which achieves the same asymptotic performance as the static B-tree dictionary, mentioned previously. A cache-oblivious data structure or algorithm is not parameterized by the block size B or memory size M in the memory hierarchy; rather, it is universal, working simultaneously for all possible values of B or M . On a machine with block size B , if there are N keys with average size K , search operations costs O (⌈ K / B ⌉log 1 + ⌈ B / K ⌉ N ) block transfers in expectation. This cache-oblivious layout can be built in O ( N log( NK )) processor operations.

Complex contagions describe diffusion of behaviors in a social network in settings where spreading requires influence by two or more neighbors. In a k-complex contagion, a cluster of nodes are initially infected, and additional nodes become infected in the next round if they have at least k already infected neighbors. It has been argued that complex contagions better model behavioral changes such as adoption of new beliefs, fashion trends or expensive technology innovations. This has motivated rigorous understanding of spreading of complex contagions in social networks. Despite simple contagions (k=1) that spread fast in all small world graphs, how complex contagions spread is much less understood. Previous work [11] analyzes complex contagions in Kleinberg's small world model [14] where edges are randomly added according to a spatial distribution (with exponent γ) on top of a two dimensional grid structure. It has been shown in [11] that the speed of complex contagions differs exponentially when γ=0 compared to when γ=2.

We introduce the cache-adaptive model, which generalizes the external-memory model to apply to environments in which the amount of memory available to an algorithm can fluctuate. The cache-adaptive model applies to operating systems, databases, and other systems where the allocation of memory to processes changes over time. We prove that if an optimal cache-oblivious algorithm has a particular recursive structure, then it is also an optimal cache-adaptive algorithm. Cache-oblivious algorithms having this form include Floyd-Warshall all pairs shortest paths, naïve recursive matrix multiplication, matrix transpose, and Gaussian elimination. While the cache-oblivious sorting algorithm Lazy Funnel Sort does not have this recursive structure, we prove that it is nonetheless optimally cache-adaptive. We also establish that if a cache-oblivious algorithm is optimal on “square”” (well-behaved) memory profiles then, given resource augmentation it is optimal on all memory profiles. We give paging algorithms for the case where the cache size changes dynamically. We prove that LRU with 4-memory and 4-speed augmentation is competitive with optimal. Moreover, Belady's algorithm remains optimal even when the cache size changes. Cache-obliviousness is distinct from cache-adaptivity. We exhibit a cache-oblivious algorithm that is not cache-adaptive and a cache-adaptive algorithm for a problem having no optimal cache-oblivious solution.

Diseases, information and rumors could spread fast in social networks exhibiting the small world property. In the diffusion of these 'simple contagions', which can spread through a single contact, a small network diameter and the existence of weak ties in the network play important roles. Recent studies by sociologists [Centola and Macy 2007] have also explored 'complex contagions' in which multiple contacts are required for the spread of contagion. [Centola and Macy 2007] and [Romero et al. 2011] have shown that complex contagions exhibit different diffusion patterns than simple ones. In this paper, we study three small world models and provide rigorous analysis on the diffusion speed of a k-complex contagion, in which a node becomes active only when at least k of its neighbors are active. Diffusion of a complex contagion starts from a constant number of initial active nodes. We provide upper and lower bounds on the number of rounds it takes for the entire network to be activated. Our results show that compared to simple contagions, weak ties are not as effective in spreading complex contagions due to the lack of simultaneous active contacts; and the diffusion speed depends heavily on the the way weak ties are distributed in a network.