5 Search Results for "Scquizzato, Michele"

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-dev.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.OPODIS.2019.33
Equivalence Classes and Conditional Hardness in Massively Parallel Computations

Authors: Danupon Nanongkai and Michele Scquizzato

Published in: LIPIcs, Volume 153, 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Abstract
The Massively Parallel Computation (MPC) model serves as a common abstraction of many modern large-scale data processing frameworks, and has been receiving increasingly more attention over the past few years, especially in the context of classical graph problems. So far, the only way to argue lower bounds for this model is to condition on conjectures about the hardness of some specific problems, such as graph connectivity on promise graphs that are either one cycle or two cycles, usually called the one cycle vs. two cycles problem. This is unlike the traditional arguments based on conjectures about complexity classes (e.g., P ≠ NP), which are often more robust in the sense that refuting them would lead to groundbreaking algorithms for a whole bunch of problems. In this paper we present connections between problems and classes of problems that allow the latter type of arguments. These connections concern the class of problems solvable in a sublogarithmic amount of rounds in the MPC model, denoted by MPC(o(log N)), and some standard classes concerning space complexity, namely L and NL, and suggest conjectures that are robust in the sense that refuting them would lead to many surprisingly fast new algorithms in the MPC model. We also obtain new conditional lower bounds, and prove new reductions and equivalences between problems in the MPC model.
Cite as

Danupon Nanongkai and Michele Scquizzato. Equivalence Classes and Conditional Hardness in Massively Parallel Computations. In 23rd International Conference on Principles of Distributed Systems (OPODIS 2019). Leibniz International Proceedings in Informatics (LIPIcs), Volume 153, pp. 33:1-33:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{nanongkai_et_al:LIPIcs.OPODIS.2019.33,
  author =	{Nanongkai, Danupon and Scquizzato, Michele},
  title =	{{Equivalence Classes and Conditional Hardness in Massively Parallel Computations}},
  booktitle =	{23rd International Conference on Principles of Distributed Systems (OPODIS 2019)},
  pages =	{33:1--33:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-133-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{153},
  editor =	{Felber, Pascal and Friedman, Roy and Gilbert, Seth and Miller, Avery},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.OPODIS.2019.33},
  URN =		{urn:nbn:de:0030-drops-118194},
  doi =		{10.4230/LIPIcs.OPODIS.2019.33},
  annote =	{Keywords: Massively parallel computation, conditional hardness, fine-grained complexity}
}
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-dev.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.2014.63
Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules

Authors: Antonios Antoniadis, Neal Barcelo, Mario Consuegra, Peter Kling, Michael Nugent, Kirk Pruhs, and Michele Scquizzato

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
We give a polynomial time algorithm to compute an optimal energy and fractional weighted flow trade-off schedule for a speed-scalable processor with discrete speeds. Our algorithm uses a geometric approach that is based on structural properties obtained from a primal-dual formulation of the problem.
Cite as

Antonios Antoniadis, Neal Barcelo, Mario Consuegra, Peter Kling, Michael Nugent, Kirk Pruhs, and Michele Scquizzato. Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 63-74, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{antoniadis_et_al:LIPIcs.STACS.2014.63,
  author =	{Antoniadis, Antonios and Barcelo, Neal and Consuegra, Mario and Kling, Peter and Nugent, Michael and Pruhs, Kirk and Scquizzato, Michele},
  title =	{{Efficient Computation of Optimal Energy and Fractional Weighted Flow Trade-off Schedules}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{63--74},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.63},
  URN =		{urn:nbn:de:0030-drops-44474},
  doi =		{10.4230/LIPIcs.STACS.2014.63},
  annote =	{Keywords: scheduling, flow time, energy efficiency, speed scaling, primal-dual}
}
Document
DOI: 10.4230/LIPIcs.STACS.2014.627
Communication Lower Bounds for Distributed-Memory Computations

Authors: Michele Scquizzato and Francesco Silvestri

Published in: LIPIcs, Volume 25, 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Abstract
In this paper we propose a new approach to the study of the communication requirements of distributed computations, which advocates for the removal of the restrictive assumptions under which earlier results were derived. We illustrate our approach by giving tight lower bounds on the communication complexity required to solve several computational problems in a distributed-memory parallel machine, namely standard matrix multiplication, stencil computations, comparison sorting, and the Fast Fourier Transform. Our bounds rely only on a mild assumption on work distribution, and significantly strengthen previous results which require either the computation to be balanced among the processors, or specific initial distributions of the input data, or an upper bound on the size of processors' local memories.
Cite as

Michele Scquizzato and Francesco Silvestri. Communication Lower Bounds for Distributed-Memory Computations. In 31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014). Leibniz International Proceedings in Informatics (LIPIcs), Volume 25, pp. 627-638, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2014)

Copy BibTex To Clipboard

@InProceedings{scquizzato_et_al:LIPIcs.STACS.2014.627,
  author =	{Scquizzato, Michele and Silvestri, Francesco},
  title =	{{Communication Lower Bounds for Distributed-Memory Computations}},
  booktitle =	{31st International Symposium on Theoretical Aspects of Computer Science (STACS 2014)},
  pages =	{627--638},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-65-1},
  ISSN =	{1868-8969},
  year =	{2014},
  volume =	{25},
  editor =	{Mayr, Ernst W. and Portier, Natacha},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2014.627},
  URN =		{urn:nbn:de:0030-drops-44937},
  doi =		{10.4230/LIPIcs.STACS.2014.627},
  annote =	{Keywords: Communication, lower bounds, distributed memory, parallel algorithms, BSP}
}
  • Refine by Author
  • 4 Scquizzato, Michele
  • 2 Peserico, Enoch
  • 1 Antoniadis, Antonios
  • 1 Barcelo, Neal
  • 1 Consuegra, Mario
  • Show More...

  • Refine by Classification
  • 1 Theory of computation → Caching and paging algorithms
  • 1 Theory of computation → Massively parallel algorithms
  • 1 Theory of computation → Online algorithms

  • Refine by Keyword
  • 1 BSP
  • 1 Communication
  • 1 Massively parallel computation
  • 1 Metric matching
  • 1 adaptive
  • Show More...

  • Refine by Type
  • 5 document

  • Refine by Publication Year
  • 2 2014
  • 1 2019
  • 1 2020
  • 1 2021

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

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