10 Search Results for "Peserico, Enoch"

Document
DOI: 10.4230/LIPIcs.ITCS.2026.94
Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion

Authors: Yingxi Li, Ellen Vitercik, and Mingwei Yang

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
In the online metric matching problem, n servers and n requests lie in a metric space. Servers are available upfront, and requests arrive sequentially. An arriving request must be matched immediately and irrevocably to an available server, incurring a cost equal to their distance. The goal is to minimize the total matching cost. We study this problem in [0, 1]^d with the Euclidean metric, when servers are adversarial and requests are independently drawn from distinct distributions that satisfy a mild smoothness condition. Our main result is an O(1)-competitive algorithm for d ≠ 2 that requires no distributional knowledge, relying only on a single sample from each request distribution. To our knowledge, this is the first algorithm to achieve an o(log n) competitive ratio for non-trivial metrics beyond the i.i.d. setting. Our approach bypasses the Ω(log n) barrier introduced by probabilistic metric embeddings: instead of analyzing the embedding distortion and the algorithm separately, we directly bound the cost of the algorithm on the target metric space of a simple deterministic embedding. We then combine this analysis with lower bounds on the offline optimum for Euclidean metrics, derived via majorization arguments, to obtain our guarantees.
Cite as

Yingxi Li, Ellen Vitercik, and Mingwei Yang. Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 94:1-94:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{li_et_al:LIPIcs.ITCS.2026.94,
  author =	{Li, Yingxi and Vitercik, Ellen and Yang, Mingwei},
  title =	{{Smoothed Analysis of Online Metric Matching with a Single Sample: Beyond Metric Distortion}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{94:1--94:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.94},
  URN =		{urn:nbn:de:0030-drops-253815},
  doi =		{10.4230/LIPIcs.ITCS.2026.94},
  annote =	{Keywords: Online algorithm, Metric matching, Competitive analysis, Smoothed analysis}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2026.89
On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time

Authors: Tsz Chiu Kwok, Zhewei Wei, and Mingji Yang

Published in: LIPIcs, Volume 362, 17th Innovations in Theoretical Computer Science Conference (ITCS 2026)

Abstract
We initiate a study of solving a row/column diagonally dominant (RDD/CDD) linear system 𝐌x = b in sublinear time, with the goal of estimating t^{⊤}x^{∗} for a given vector t ∈ ℝⁿ and a specific solution x^{∗}. This setting naturally generalizes the study of sublinear-time solvers for symmetric diagonally dominant (SDD) systems [Andoni-Krauthgamer-Pogrow, ITCS 2019] to the asymmetric case, which has remained underexplored despite extensive work on nearly-linear-time solvers for RDD/CDD systems. Our first contributions are characterizations of the problem’s mathematical structure. We express a solution x^{∗} via a Neumann series, prove its convergence, and upper bound the truncation error on this series through a novel quantity of 𝐌, termed the maximum p-norm gap. This quantity generalizes the spectral gap of symmetric matrices and captures how the structure of 𝐌 governs the problem’s computational difficulty. For systems with bounded maximum p-norm gap, we develop a collection of algorithmic results for locally approximating t^{⊤}x^{∗} under various scenarios and error measures. We derive these results by adapting the techniques of random-walk sampling, local push, and their bidirectional combination, which have proved powerful for special cases of solving RDD/CDD systems, particularly estimating PageRank and effective resistance on graphs. Our general framework yields deeper insights, extended results, and improved complexity bounds for these problems. Notably, our perspective provides a unified understanding of Forward Push and Backward Push, two fundamental approaches for estimating random-walk probabilities on graphs. Our framework also inherits the hardness results for sublinear-time SDD solvers and local PageRank computation, establishing lower bounds on the maximum p-norm gap or the accuracy parameter. We hope that our work opens the door for further study into sublinear solvers, local graph algorithms, and directed spectral graph theory.
Cite as

Tsz Chiu Kwok, Zhewei Wei, and Mingji Yang. On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time. In 17th Innovations in Theoretical Computer Science Conference (ITCS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 362, pp. 89:1-89:25, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{kwok_et_al:LIPIcs.ITCS.2026.89,
  author =	{Kwok, Tsz Chiu and Wei, Zhewei and Yang, Mingji},
  title =	{{On Solving Asymmetric Diagonally Dominant Linear Systems in Sublinear Time}},
  booktitle =	{17th Innovations in Theoretical Computer Science Conference (ITCS 2026)},
  pages =	{89:1--89:25},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-410-9},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{362},
  editor =	{Saraf, Shubhangi},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2026.89},
  URN =		{urn:nbn:de:0030-drops-253768},
  doi =		{10.4230/LIPIcs.ITCS.2026.89},
  annote =	{Keywords: Spectral Graph Theory, Linear Systems, Sublinear Algorithms}
}
Document
DOI: 10.4230/LIPIcs.ITC.2025.6
MetaDORAM: Info-Theoretic Distributed ORAM with Less Communication

Authors: Brett Hemenway Falk, Daniel Noble, and Rafail Ostrovsky

Published in: LIPIcs, Volume 343, 6th Conference on Information-Theoretic Cryptography (ITC 2025)

Abstract
A Distributed Oblivious RAM is a multi-party protocol that securely implements a RAM functionality on secret-shared inputs and outputs. This paper presents two information-theoretically secure DORAMs whose communication costs are asymptotic improvements over the state of the art. Let n be the number of memory locations and let d be the bit-length of each location. The first, MetaDORAM1, is statistically secure, with n^{-ω(1)} leakage. It has amortized O(log_b(n) d + b ω(1) log(n) + log³(n)/log(log(n))) bits of communication per memory access. Here, b ≥ 2 is a free parameter and ω(1) is any super-constant function (in n). The most communication-efficient prior statistically secure DORAM was that of Abraham et al (PKC 2017), which has cost O(log_b(n) d + b ω(1) log_b(n) log²(n)). MetaDORAM1 is a Θ(ω(1) log(log(n)))-factor improvement over the work of Abraham et al whenever d = O(log²(n)). The second protocol, MetaDORAM2, achieves perfect security. It has amortized communication cost O(log_b(n)d + b log(n) + log³(n)/log(log(n))) where, again, b ≥ 2 is a free parameter. The best prior perfectly secure DORAM is that of Chan et al (ASIACRYPT 2018) which has communication cost O(log(n) d + log³(n)). MetaDORAM2 is therefore a Ω(log(log(n)))-factor improvement over the DORAM of Chan et al under any parameter range (by setting b = log(n)) and is a Θ(log(n))-factor improvement for d = Ω(n^ε) for any constant ε > 0 (by setting b = d/log(n)). Our work is the first perfectly secure DORAM with sub-logarithmic communication overhead. MetaDORAM2 comes at the cost of a once-off (for any given n) setup phase which requires exponential (in n) computation. Both DORAMs are in the 3-party setting with security against 1 semi-honest, static corruption. By a trivial transformation, these can be transformed, respectively, into statistically and perfectly secure active 3-server ORAM protocols secure against 1 corrupt server, with the same communication costs. These multi-server ORAM protocols are likewise asymptotic improvements over the state of the art.
Cite as

Brett Hemenway Falk, Daniel Noble, and Rafail Ostrovsky. MetaDORAM: Info-Theoretic Distributed ORAM with Less Communication. In 6th Conference on Information-Theoretic Cryptography (ITC 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 343, pp. 6:1-6:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{falk_et_al:LIPIcs.ITC.2025.6,
  author =	{Falk, Brett Hemenway and Noble, Daniel and Ostrovsky, Rafail},
  title =	{{MetaDORAM: Info-Theoretic Distributed ORAM with Less Communication}},
  booktitle =	{6th Conference on Information-Theoretic Cryptography (ITC 2025)},
  pages =	{6:1--6:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-385-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{343},
  editor =	{Gilboa, Niv},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2025.6},
  URN =		{urn:nbn:de:0030-drops-243560},
  doi =		{10.4230/LIPIcs.ITC.2025.6},
  annote =	{Keywords: ORAM, MPC, DORAM, multi-server ORAM, active ORAM}
}
Document
DOI: 10.4230/LIPIcs.WADS.2025.49
On the I/O Complexity of the Cocke-Younger-Kasami Algorithm and of a Family of Related Dynamic Programming Algorithms

Authors: Lorenzo De Stefani and Vedant Gupta

Published in: LIPIcs, Volume 349, 19th International Symposium on Algorithms and Data Structures (WADS 2025)

Abstract
Asymptotically tight lower bounds are derived for the Input/Output (I/O) complexity of a class of dynamic programming algorithms, including matrix chain multiplication, optimal polygon triangulation, and the construction of optimal binary search trees. Assuming no recomputation of intermediate values, we establish an Ω(n³/(√M B)) I/O lower bound, where n denotes the size of the input and M denotes the size of the available fast memory (cache). When recomputation is allowed, we show that the same bound holds for M < cn, where c is a positive constant. In the case where M ≥ 2n, we show an Ω(n/B) I/O lower bound. We also discuss algorithms for which the number of executed I/O operations matches asymptotically each of the presented lower bounds, which are thus asymptotically tight. Additionally, we refine our general method to obtain a lower bound for the I/O complexity of the Cocke-Younger-Kasami algorithm, where the size of the grammar impacts the I/O complexity. An upper bound with asymptotically matching performance in many cases is also provided.
Cite as

Lorenzo De Stefani and Vedant Gupta. On the I/O Complexity of the Cocke-Younger-Kasami Algorithm and of a Family of Related Dynamic Programming Algorithms. In 19th International Symposium on Algorithms and Data Structures (WADS 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 349, pp. 49:1-49:24, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{destefani_et_al:LIPIcs.WADS.2025.49,
  author =	{De Stefani, Lorenzo and Gupta, Vedant},
  title =	{{On the I/O Complexity of the Cocke-Younger-Kasami Algorithm and of a Family of Related Dynamic Programming Algorithms}},
  booktitle =	{19th International Symposium on Algorithms and Data Structures (WADS 2025)},
  pages =	{49:1--49:24},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-398-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{349},
  editor =	{Morin, Pat and Oh, Eunjin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.WADS.2025.49},
  URN =		{urn:nbn:de:0030-drops-242800},
  doi =		{10.4230/LIPIcs.WADS.2025.49},
  annote =	{Keywords: I/O complexity, Dynamic Programming Algorithms, Lower Bounds, Recomputation, Cocke-Younger-Kasami}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2025.94
A Nearly Optimal Deterministic Algorithm for Online Transportation Problem

Authors: Tsubasa Harada and Toshiya Itoh

Published in: LIPIcs, Volume 334, 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)

Abstract
For the online transportation problem with m server sites, it has long been known that the competitive ratio of any deterministic algorithm is at least 2m-1. Kalyanasundaram and Pruhs conjectured in 1998 that a deterministic (2m-1)-competitive algorithm exists for this problem, a conjecture that has remained open for over two decades. In this paper, we propose a new deterministic algorithm for the online transportation problem and show that it achieves a competitive ratio of at most 8m-5. This is the first O(m)-competitive deterministic algorithm, coming close to the lower bound of 2m-1 within a constant factor.
Cite as

Tsubasa Harada and Toshiya Itoh. A Nearly Optimal Deterministic Algorithm for Online Transportation Problem. In 52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 334, pp. 94:1-94:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{harada_et_al:LIPIcs.ICALP.2025.94,
  author =	{Harada, Tsubasa and Itoh, Toshiya},
  title =	{{A Nearly Optimal Deterministic Algorithm for Online Transportation Problem}},
  booktitle =	{52nd International Colloquium on Automata, Languages, and Programming (ICALP 2025)},
  pages =	{94:1--94:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-372-0},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{334},
  editor =	{Censor-Hillel, Keren and Grandoni, Fabrizio and Ouaknine, Jo\"{e}l and Puppis, Gabriele},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2025.94},
  URN =		{urn:nbn:de:0030-drops-234712},
  doi =		{10.4230/LIPIcs.ICALP.2025.94},
  annote =	{Keywords: Online algorithms, Competitive analysis, Online metric matching, Online weighted matching, Online minimum weight perfect matching, Online transportation problem, Online facility assignment, Greedy algorithm}
}
Document
DOI: 10.4230/LIPIcs.ICDT.2025.25
Optimal Oblivious Algorithms for Multi-Way Joins

Authors: Xiao Hu and Zhiang Wu

Published in: LIPIcs, Volume 328, 28th International Conference on Database Theory (ICDT 2025)

Abstract
In cloud databases, cloud computation over sensitive data uploaded by clients inevitably causes concern about data security and privacy. Even if cryptographic primitives and trusted computing environments are integrated into query processing to safeguard the actual contents of the data, access patterns of algorithms can still leak private information about data. Oblivious RAM (ORAM) and circuits are two generic approaches to address this issue, ensuring that access patterns of algorithms remain oblivious to the data. However, deploying these methods on insecure algorithms, particularly for multi-way join processing, is computationally expensive and inherently challenging. In this paper, we propose a novel sorting-based algorithm for multi-way join processing that operates without relying on ORAM simulations or other security assumptions. Our algorithm is a non-trivial, provably oblivious composition of basic primitives, with time complexity matching the insecure worst-case optimal join algorithm, up to a logarithmic factor. Furthermore, it is cache-agnostic, with cache complexity matching the insecure lower bound, also up to a logarithmic factor. This clean and straightforward approach has the potential to be extended to other security settings and implemented in practical database systems.
Cite as

Xiao Hu and Zhiang Wu. Optimal Oblivious Algorithms for Multi-Way Joins. In 28th International Conference on Database Theory (ICDT 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 328, pp. 25:1-25:19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{hu_et_al:LIPIcs.ICDT.2025.25,
  author =	{Hu, Xiao and Wu, Zhiang},
  title =	{{Optimal Oblivious Algorithms for Multi-Way Joins}},
  booktitle =	{28th International Conference on Database Theory (ICDT 2025)},
  pages =	{25:1--25:19},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-364-5},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{328},
  editor =	{Roy, Sudeepa and Kara, Ahmet},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICDT.2025.25},
  URN =		{urn:nbn:de:0030-drops-229662},
  doi =		{10.4230/LIPIcs.ICDT.2025.25},
  annote =	{Keywords: oblivious algorithms, multi-way joins, worst-case optimality}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.103
Matching on the Line Admits No o(√log n)-Competitive Algorithm

Authors: Enoch Peserico and Michele Scquizzato

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We present a simple proof that the competitive ratio of any randomized online matching algorithm for the line exceeds √{log₂(n +1)}/15 for all n = 2ⁱ-1: i ∈ ℕ, settling a 25-year-old open question.
Cite as

Enoch Peserico and Michele Scquizzato. Matching on the Line Admits No o(√log n)-Competitive Algorithm. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 103:1-103:3, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{peserico_et_al:LIPIcs.ICALP.2021.103,
  author =	{Peserico, Enoch and Scquizzato, Michele},
  title =	{{Matching on the Line Admits No o(√log n)-Competitive Algorithm}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{103:1--103:3},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.103},
  URN =		{urn:nbn:de:0030-drops-141720},
  doi =		{10.4230/LIPIcs.ICALP.2021.103},
  annote =	{Keywords: Metric matching, online algorithms, competitive analysis}
}
Document
DOI: 10.4230/LIPIcs.ITC.2020.11
Oblivious Parallel Tight Compaction

Authors: Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, and Elaine Shi

Published in: LIPIcs, Volume 163, 1st Conference on Information-Theoretic Cryptography (ITC 2020)

Abstract
In tight compaction one is given an array of balls some of which are marked 0 and the rest are marked 1. The output of the procedure is an array that contains all of the original balls except that now the 0-balls appear before the 1-balls. In other words, tight compaction is equivalent to sorting the array according to 1-bit keys (not necessarily maintaining order within same-key balls). Tight compaction is not only an important algorithmic task by itself, but its oblivious version has also played a key role in recent constructions of oblivious RAM compilers. We present an oblivious deterministic algorithm for tight compaction such that for input arrays of n balls requires O(n) total work and O(log n) depth. Our algorithm is in the Exclusive-Read-Exclusive-Write Parallel-RAM model (i.e., EREW PRAM, the most restrictive PRAM model), and importantly we achieve asymptotical optimality in both total work and depth. To the best of our knowledge no earlier work, even when allowing randomization, can achieve optimality in both total work and depth.
Cite as

Gilad Asharov, Ilan Komargodski, Wei-Kai Lin, Enoch Peserico, and Elaine Shi. Oblivious Parallel Tight Compaction. In 1st Conference on Information-Theoretic Cryptography (ITC 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 163, pp. 11:1-11:23, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{asharov_et_al:LIPIcs.ITC.2020.11,
  author =	{Asharov, Gilad and Komargodski, Ilan and Lin, Wei-Kai and Peserico, Enoch and Shi, Elaine},
  title =	{{Oblivious Parallel Tight Compaction}},
  booktitle =	{1st Conference on Information-Theoretic Cryptography (ITC 2020)},
  pages =	{11:1--11:23},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-151-1},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{163},
  editor =	{Tauman Kalai, Yael and Smith, Adam D. and Wichs, Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.ITC.2020.11},
  URN =		{urn:nbn:de:0030-drops-121164},
  doi =		{10.4230/LIPIcs.ITC.2020.11},
  annote =	{Keywords: Oblivious tight compaction, parallel oblivious RAM, EREW PRAM}
}
Document
DOI: 10.4230/LIPIcs.STACS.2019.56
Paging with Dynamic Memory Capacity

Authors: Enoch Peserico

Published in: LIPIcs, Volume 126, 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)

Abstract
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.
Cite as

Enoch Peserico. Paging with Dynamic Memory Capacity. In 36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 126, pp. 56:1-56:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2019)

Copy BibTex To Clipboard

@InProceedings{peserico:LIPIcs.STACS.2019.56,
  author =	{Peserico, Enoch},
  title =	{{Paging with Dynamic Memory Capacity}},
  booktitle =	{36th International Symposium on Theoretical Aspects of Computer Science (STACS 2019)},
  pages =	{56:1--56:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-100-9},
  ISSN =	{1868-8969},
  year =	{2019},
  volume =	{126},
  editor =	{Niedermeier, Rolf and Paul, Christophe},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2019.56},
  URN =		{urn:nbn:de:0030-drops-102951},
  doi =		{10.4230/LIPIcs.STACS.2019.56},
  annote =	{Keywords: paging, cache, adaptive, elastic, online, competitive, virtual, energy}
}
Document
DOI: 10.4230/LIPIcs.STACS.2018.18
On Approximating the Stationary Distribution of Time-reversible Markov Chains

Authors: Marco Bressan, Enoch Peserico, and Luca Pretto

Published in: LIPIcs, Volume 96, 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)

Abstract
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 pi(v) of a state v in a chain with mixing time tau, 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 pi(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-pi(v) barrier".
Cite as

Marco Bressan, Enoch Peserico, and Luca Pretto. On Approximating the Stationary Distribution of Time-reversible Markov Chains. In 35th Symposium on Theoretical Aspects of Computer Science (STACS 2018). Leibniz International Proceedings in Informatics (LIPIcs), Volume 96, pp. 18:1-18:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2018)

Copy BibTex To Clipboard

@InProceedings{bressan_et_al:LIPIcs.STACS.2018.18,
  author =	{Bressan, Marco and Peserico, Enoch and Pretto, Luca},
  title =	{{On Approximating the Stationary Distribution of Time-reversible Markov Chains}},
  booktitle =	{35th Symposium on Theoretical Aspects of Computer Science (STACS 2018)},
  pages =	{18:1--18:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-062-0},
  ISSN =	{1868-8969},
  year =	{2018},
  volume =	{96},
  editor =	{Niedermeier, Rolf and Vall\'{e}e, Brigitte},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2018.18},
  URN =		{urn:nbn:de:0030-drops-84949},
  doi =		{10.4230/LIPIcs.STACS.2018.18},
  annote =	{Keywords: Markov chains, MCMC sampling, large graph algorithms, randomized algorithms, sublinear algorithms}
}
  • Refine by Type
  • 10 Document/PDF
  • 6 Document/HTML

  • Refine by Publication Year
  • 2 2026
  • 4 2025
  • 1 2021
  • 1 2020
  • 1 2019
  • Show More...

  • Refine by Author
  • 4 Peserico, Enoch
  • 1 Asharov, Gilad
  • 1 Bressan, Marco
  • 1 De Stefani, Lorenzo
  • 1 Falk, Brett Hemenway
  • Show More...

  • Refine by Series/Journal
  • 10 LIPIcs

  • Refine by Classification
  • 3 Theory of computation → Online algorithms
  • 2 Security and privacy → Management and querying of encrypted data
  • 1 Information systems → Join algorithms
  • 1 Mathematics of computing → Spectra of graphs
  • 1 Security and privacy → Information-theoretic techniques
  • Show More...

  • Refine by Keyword
  • 2 Competitive analysis
  • 2 Metric matching
  • 1 Cocke-Younger-Kasami
  • 1 DORAM
  • 1 Dynamic Programming Algorithms
  • Show More...

Any Issues?
X

Feedback on the Current Page

CAPTCHA

Thanks for your feedback!

Feedback submitted to Dagstuhl Publishing

Could not send message

Please try again later or send an E-mail
© 2023-2026 Schloss Dagstuhl – LZI GmbH Schloss Dagstuhl – LZI GmbH About DROPS Imprint Privacy Contact