Oblivious RAM (ORAM), first introduced in the ground-breaking work of Goldreich and Ostrovsky (STOC ’87 and J. ACM ’96) is a technique for provably obfuscating programs’ access patterns, such that the access patterns leak no information about the programs’ secret inputs. To compile a general program to an oblivious counterpart, it is well-known that Ω (log N ) amortized blowup in memory accesses is necessary, where N is the size of the logical memory. This was shown in Goldreich and Ostrovksy’s original ORAM work for statistical security and in a somewhat restricted model (the so-called balls-and-bins model), and recently by Larsen and Nielsen (CRYPTO ’18) for computational security. A long-standing open question is whether there exists an optimal ORAM construction that matches the aforementioned logarithmic lower bounds (without making large memory word assumptions, and assuming a constant number of CPU registers). In this article, we resolve this problem and present the first secure ORAM with O (log N ) amortized blowup, assuming one-way functions. Our result is inspired by and non-trivially improves on the recent beautiful work of Patel et al. (FOCS ’18) who gave a construction with O (log N ⋅ log log N ) amortized blowup, assuming one-way functions. One of our building blocks of independent interest is a linear-time deterministic oblivious algorithm for tight compaction: Given an array of n elements where some elements are marked, we permute the elements in the array so that all marked elements end up in the front of the array. Our O ( n ) algorithm improves the previously best-known deterministic or randomized algorithms whose running time is O ( n ⋅ log n ) or O ( n ⋅ log log n ), respectively.

Abstract. We study the complexity of local graph-centrality estimation, with the goal of approximating the centrality score of a given target node while exploring only a sublinear number of nodes/arcs of the graph and performing a sublinear number of elementary operations. We develop a technique, which we apply to PageRank and Heat Kernel, for constructing a low-variance score estimator through a local exploration of the graph. We obtain an algorithm that, given any node in any graph of [Formula: see text] nodes and [Formula: see text] arcs, with probability [Formula: see text] computes a multiplicative [Formula: see text]-approximation of its score by examining only [Formula: see text] nodes/arcs, where [Formula: see text] is the maximum outdegree of the graph and [Formula: see text] and [Formula: see text] factors are omitted for readability. A similar bound holds for computational cost. We also prove a lower bound of [Formula: see text] for both query complexity and computational complexity. Moreover, in the jump-and-crawl graph-access model, our technique yields a [Formula: see text]-queries algorithm; we show that this algorithm is optimal up to a logarithmic factor—in fact, sublogarithmic in the case of PageRank. These are the first algorithms with sublinear worst-case bounds for general directed graphs and any choice of the target node.

We present a simple proof that no randomized online matching algorithm for the line can be \((\sqrt {\log _2(n+1)}/15)\) -competitive against an oblivious adversary for any n = 2 i - 1 : i ∈ ℕ. This is the first super-constant lower bound for the problem, and disproves as a corollary a recent conjecture on the topology-parametrized competitiveness achievable on generic spaces.

An oblivious RAM (ORAM), introduced by Goldreich and Ostrovsky (STOC '87 and J. ACM '96), is a technique for hiding RAM's access pattern. That is, for every input the distribution of the observed locations accessed by the machine is essentially independent of the machine's secret inputs. Recent progress culminated in a work of Asharov et al. (EUROCRYPT '20), obtaining an ORAM with (amortized) logarithmic overhead in total work, which is known to be optimal. Oblivious Parallel RAM (OPRAM) is a natural extension of ORAM to the (more realistic) parallel setting where several processors make concurrent accesses to a shared memory. It is known that any OPRAM must incur logarithmic work overhead (in the balls and bins model). Despite the significant recent advances for constructing ORAM, there is still a significant gap for OPRAM: all existing OPRAM schemes incur a poly-logarithmic overhead either in total work or in depth. Our main result closes the aforementioned gap and provides an optimal OPRAM. Specifically, assuming one-way functions, we show that any Parallel RAM with memory capacity N can be obliviously simulated in space O(N), incurring only O(log N) blowup in (amortized) total work as well as in depth. Our transformation supports all PRAMs in the CRCW (concurrent read, concurrent write) mode and the resulting simulation is in the CRCW mode as well.

The classical paging problem can be described as follows: given a cache that can hold up to k pages (or blocks) and a sequence of requests to pages, how should we manage the cache so as to maximize performance-or, in other words, complete the sequence as quickly as possible. Whereas this sequential paging problem has been well understood for decades, the parallel version, where the cache is shared among p processors each issuing its own sequence of page requests, has been much more resistant. In this problem we are given p request sequences R1, R2, . . . , Rp , each of which accesses a disjoint set of pages, and we ask the question: how should the paging algorithm manage the cache to optimize the completion time of all sequences (i.e., the makespan). As for the classical sequential problem, the goal is to design an online paging algorithm that achieves an optimal competitive ratio, using O(1) resource augmentation.

In the parallel paging problem, there are p processors that share a cache of size k. The goal is to partition the cache among the processors over time in order to minimize their average completion time. For this long-standing open problem, we give tight upper and lower bounds of Θ(logp) on the competitive ratio with O(1) resource augmentation. A key idea in both our algorithms and lower bounds is to relate the problem of parallel paging to the seemingly unrelated problem of green paging. In green paging, there is an energy-optimized processor that can temporarily turn off one or more of its cache banks (thereby reducing power consumption), so that the cache size varies between a maximum size k and a minimum size k/p. The goal is to minimize the total energy consumed by the computation, which is proportional to the integral of the cache size over time. We show that any efficient solution to green paging can be converted into an efficient solution to parallel paging, and that any lower bound for green paging can be converted into a lower bound for parallel paging, in both cases in a black-box fashion. We then show that, with O(1) resource augmentation, the optimal competitive ratio for deterministic online green paging is Θ(log p), which, in turn, implies the same bounds for deterministic online parallel paging.

We study two fundamental variants of the classic paging problem: green paging and parallel paging. In green paging one can choose the exact memory capacity in use at any given instant, between a maximum of k and a minimum of k/p pages; the goal is to minimize the integral of this number over the time required to complete a computation (note that running at lower capacity is not necessarily better, since might disproportionately increase the total completion time). In parallel paging, a memory of k pages is shared between p processors, each carrying out a separate computation; the goal is to minimize the respective completion times.

Approximating the stationary probability of a state in a Markov chain through Markov chain Monte Carlo techniques is, in general, inefficient. Standard random walk approaches require \(\tilde {O}(\tau /\pi (v))\) operations to approximate the probability π ( v ) of a state v in a chain with mixing time τ , and even the best available techniques still have complexity \(\tilde {O}(\tau ^{1.5}/\pi (v)^{0.5})\) ; and since these complexities depend inversely on π ( v ), they can grow beyond any bound in the size of the chain or in its mixing time. In this paper we show that, for time-reversible Markov chains, there exists a simple randomized approximation algorithm that breaks this “small- π ( v ) barrier”.

We study a generalization of the classic paging problem that allows the amount of available memory to vary over time - capturing a fundamental property of many modern computing realities, from cloud computing to multi-core and energy-optimized processors. It turns out that good performance in the "classic" case provides no performance guarantees when memory capacity fluctuates: roughly speaking, moving from static to dynamic capacity can mean the difference between optimality within a factor 2 in space and time, and suboptimality by an arbitrarily large factor. More precisely, adopting the competitive analysis framework, we show that some online paging algorithms, despite having an optimal (h,k)-competitive ratio when capacity remains constant, are not (3,k)-competitive for any arbitrarily large k in the presence of minimal capacity fluctuations. In this light it is surprising that several classic paging algorithms perform remarkably well even if memory capacity changes adversarially - in fact, even without taking those changes into explicit account! In particular, we prove that LFD still achieves the minimum number of faults, and that several classic online algorithms such as LRU have a "dynamic" (h,k)-competitive ratio that is the best one can achieve without knowledge of future page requests, even if one had perfect knowledge of future capacity fluctuations. Thus, with careful management, knowing/predicting future memory resources appears far less crucial to performance than knowing/predicting future data accesses. We characterize the optimal "dynamic" (h,k)-competitive ratio exactly, and show it has a somewhat complex expression that is almost but not quite equal to the "classic" ratio k/(k-h+1), thus proving a strict if minuscule separation between online paging performance achievable in the presence or absence of capacity fluctuations.

We study the complexity of local graph centrality estimation, with the goal of approximating the centrality score of a given target node while exploring only a sublinear number of nodes/arcs of the graph and performing a sublinear number of elementary operations. We develop a technique, that we apply to the PageRank and Heat Kernel centralities, for building a low-variance score estimator through a local exploration of the graph. We obtain an algorithm that, given any node in any graph of m arcs, with probability (1-δ) computes a multiplicative (1±ε)-approximation of its score by examining only Õ(min(m2/3Δ1/3d-2/3, m4/5d-3/5)) nodes/arcs, where Δ and d are respectively the maximum and average outdegree of the graph (omitting for readability poly(ε-1) and polylog(δ-1) factors). A similar bound holds for computational cost. We also prove a lower bound of Ω(min (m1/2Δ1/2d-1/2, m2/3d-1/3)) for both query complexity and computational complexity. Moreover, our technique yields a Õ(n2/3)-queries algorithm for an n-node graph in the access model of [Brautbar et al., 2010], widely used in social network mining; we show this algorithm is optimal up to a sublogarithmic factor. These are the first algorithms yielding worst-case sublinear bounds for general directed graphs and any choice of the target node.

Can one compute the PageRank score of a single, arbitrary node in a graph, exploring only a vanishing fraction of the graph? We provide a positive answer to this extensively researched open question. We develop the first algorithm that, for any n -node graph, returns a multiplicative $(1\pmε)$-approximation of the score of any given node with probability $(1-δ)$, using at most $O\big(n^2/3 łn(n)^1/3 łn(1/δ)^2/3 ε^-2/3 \big) = \tildeO (n^2/3 )$ queries which return either a node chosen uniformly at random, or the list of neighbours of a given node. Alternatively, we show that the same guarantees can be attained by fetching at most $O\big( E^4/5 d^-3/5 łn(n)^1/5 łn(1/δ)^3/5 ε^-6/5 \big) = \tildeO (E^4/5 )$ arcs, where E is the total number of arcs in the graph and d is its average degree.

A few troublemakers often spoil online environments for everyone else. An extremely disruptive type of abuser is the troll, whose malicious activities are relatively non-obvious, and thus difficult to detect and contain -- particularly by automated systems. A growing corpus of qualitative research focuses on trolling, and differentiates it from other forms of abuse; however, its findings are not directly actionable into automated systems. On the other hand, quantitative research uses definitions of "troll" that mostly fail to capture what moderators and users consider trolling. We address this gap by giving a quantitative analysis of posts, conversations, and users, specifically sanctioned for trolling in an online forum. Although trolls (unlike most other abusers) hardly stand out in a conversation e.g. in terms of vocabulary, textit{how} they interact, rather than textit{what} they contribute, provides cues of their malicious intent.

We investigate community structure and interaction dynamics in online discussion forums through the lens of quotes, examining four forums of different size, language, and topic. Quote usage appears to have an important role in aiding intra-thread navigation, uncovers a hidden social structure in communities otherwise lacking all explicit signals (from friends and followers to reputations) of today's online social networks, and can be used to fingerprint and characterize both individual users and entire communities.

This work studies delay and throughput achievable in delay-tolerant networks with ballistic mobility -- informally, when the average distance a node travels before changing direction does not become vanishingly small as the number of nodes in the deployment area grows. Ballistic mobility is a simple condition satisfied by a large number of well-studied mobility models, including the i.i.d. model, the random waypoint model, the uniform mobility model and Levy walks with exponent less than 1. Our contribution is twofold. First, we show that, under some very mild and natural hypotheses satisfied by all models in the literature, ballistic mobility is strictly necessary to achieve simultaneously, as the number of nodes grows, a) per-node throughput that does not become vanishingly small and b) communication delay that does not become infinitely large. Any network whose nodes exhibit a more "local" mobility pattern (e.g. Levy walks with exponent greater than 1, or Brownian motion) must sacrifice either a) or b), regardless of the communication scheme adopted -- even with network coding.

We study a generalization of the classic paging problem where memory capacity can vary over time - a property of many modern computing realities, from cloud computing to multi-core and energy-optimized processors. We show that good performance in the "classic" case provides no performance guarantees when memory capacity fluctuates: roughly speaking, moving from static to dynamic capacity can mean the difference between optimality within a factor 2 in space, time and energy, and suboptimality by an arbitrarily large factor. Surprisingly, several classic paging algorithms still perform remarkably well, maintaining that factor 2 optimality even if faced with adversarial capacity fluctuations - without taking those fluctuations into explicit account!

This article explores the fundamental question of how many iterations the celebrated HITS algorithm requires on a general graph to converge in score and, perhaps more importantly, in rank (i.e. to “get right” the order of the nodes). We prove upper and almost matching lower bounds. We also extend our results to weighted graphs.

The combination of the high-performance psort sorting library and of a carefully tuned desktop-class cluster allowed us to improve the previous record on the Datamation sort benchmark by over an order of magnitude, sorting a million 100 byte records from disk to disk in a few dozen milliseconds. Of the many implementation and configuration choices we faced, the most crucial were judicious data placement and access patterns on disk, adoption of UDP sockets instead of MPI, careful pruning of virtually all system daemons, and rejection of ``on demand'' frequency scaling.

This work argues that, in the face of growing thermal constraints, under an increasing number of scenarios the most effective tiled processor design is one that can support efficient flashcrowding: in a nutshell, placing on a chip far more computational power than it can sustain for extended periods of time, and concentrating computation into a few transient hotspots.

To what extent can one "prune" the links in a wireless network while retaining (almost) the same connectivity achieved when each node is connected to all nodes within its communication radius? In a nutshell, if each node explores a portion of its neighborhood sufficient to reach ≈ log(1/ε) other nodes in expectation, w.h.p. all but a fraction ε of the network joins the same connected component. Each node can then "locally" choose to maintain (at most) 4 links, and the network still retains w.h.p. essentially the same level of connectivity.

How many iterations does the (ever more) popular HITS algorithm require to converge in score and, perhaps more importantly, in rank (i.e. to get the nodes of a graph "in the right order")? After pinning down the elusive notion of convergence in rank we provide the first non-trivial bounds on the convergence of HITS. A "worst case" example, requiring a number of iterations superexponential in the size of the target graph to achieve even "mild" convergence, suggests the need for greater caution in the experimental evaluation of the algorithm - as recent results of poor performance (e.g. vs. SALSA) might be due to insufficient iterations, rather than to an intrinsic deficiency of HITS. An almost matching upper bound shows that, as long as one employs exponential acceleration e.g. through a "squaring trick", a polynomial running time (practical in many application domains) always provides strong convergence guarantees.

We prove that, in general, the lazy adversary conjecture fails. Moreover, it fails in a very strong sense: an adversary which is even "slightly lazy" can perform arbitrarily worse than one which is not.