8 citations · 11 across the 8 of their papers we have counts for
6 papers · 1 filter
Is competitive online paging an artifact?
Enoch Peserico, Michele Scquizzato
In any real system a newly computed datum begins its existence in the processor rather than in external memory, and thus does not inevitably incur a cold miss. This was captured by…
Matching on the line admits no -competitive algorithm
Enoch Peserico, Michele Scquizzato
We present a simple proof that the competitive ratio of any randomized online matching algorithm for the line is at least for all $n=2^i\!-\!1: i\in\mat…
Deterministic oblivious distribution (and tight compaction) in linear time
Enoch Peserico
In an array of N elements, M positions and M elements are "marked". We show how to permute the elements in the array so that all marked elements end in marked positions, in time O(…
Sublinear algorithms for local graph centrality estimation
Marco Bressan, Enoch Peserico, Luca Pretto
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…
Paging with dynamic memory capacity
Enoch Peserico
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 rea…
The rank convergence of HITS can be slow
Enoch Peserico, Luca Pretto
We prove that HITS, to "get right" h of the top k ranked nodes of an N>=2k node graph, can require h^(Omega(N h/k)) iterations (i.e. a substantial Omega(N h log(h)/k) matrix multip…