Michele Scquizzato
Current Organizations / Institutes
The organizations/institutes from the scholar's latest article
Previous Organizations / Institutes
The organizations / institutes from the scholar's other articles in the past ten years
Michele Scquizzato has a total of 17 co-authors. Here are the top co-authors by number of shared publications:
- Danupon Nanongkai
MPI-INF Germany
3 shared publications Enoch Peserico
2 shared publicationsGopal Pandurangan
2 shared publications- Kirk Pruhs
University of Pittsburgh, Pittsburgh, PA, USA
2 shared publications Alberto Nicoletti
1 shared publication- Antonios Antoniadis
University of Twente
1 shared publication
Latest Publications
- 9 June 2026
- Published by Elsevier in Operations Research Letters
- Vol. 68
Permutation for online metric matching with m distinct servers
- 9 June 2026
- Published by Elsevier in Operations Research Letters
- Vol. 68
Permutation for online metric matching with m distinct servers
- Open Access
- 14 July 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 19 (3) , 1-4
Matching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive AlgorithmWe 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.- 14 July 2023
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 19 (3) , 1-4
Open AccessMatching on the Line Admits no \(o(\sqrt {\log n})\) -Competitive AlgorithmWe 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. - Open Access
Distributed Algorithms for Large-Scale Graphs
Motivated by the increasing need for fast processing of large-scale graphs, we study a number of fundamental graph problems in a message-passing model for distributed computing, called $k$-machine model, where we have $k$ machines that jointly perform computations on $n$-node graphs. The graph is assumed to be partitioned in a balanced fashion among the $k$ machines, a common implementation in many real-world systems. Communication is point-to-point via bandwidth-constrained links, and the goal is to minimize the round complexity, i.e., the number of communication rounds required to finish a computation. We present a generic methodology that allows to obtain efficient algorithms in the $k$-machine model using distributed algorithms for the classical CONGEST model of distributed computing. Using this methodology, we obtain algorithms for various fundamental graph problems such as connectivity, minimum spanning trees, shortest paths, maximal independent sets, and finding subgraphs, showing that many of these problems can be solved in $\tilde{O}(n/k)$ rounds; this shows that one can achieve speedup nearly linear in $k$. To complement our upper bounds, we present lower bounds on the round complexity that quantify the fundamental limitations of solving graph problems distributively. We first show a lower bound of $\Omega(n/k)$ rounds for computing a spanning tree of the input graph. This result implies the same bound for other fundamental problems such as computing a minimum spanning tree, breadth-first tree, or shortest paths tree. We also show a $\tilde \Omega(n/k^2)$ lower bound for connectivity, spanning tree verification and other related problems. The latter lower bounds follow from the development and application of novel results in a random-partition variant of the classical communication complexity model.Open AccessDistributed Algorithms for Large-Scale Graphs
Motivated by the increasing need for fast processing of large-scale graphs, we study a number of fundamental graph problems in a message-passing model for distributed computing, called $k$-machine model, where we have $k$ machines that jointly perform computations on $n$-node graphs. The graph is assumed to be partitioned in a balanced fashion among the $k$ machines, a common implementation in many real-world systems. Communication is point-to-point via bandwidth-constrained links, and the goal is to minimize the round complexity, i.e., the number of communication rounds required to finish a computation. We present a generic methodology that allows to obtain efficient algorithms in the $k$-machine model using distributed algorithms for the classical CONGEST model of distributed computing. Using this methodology, we obtain algorithms for various fundamental graph problems such as connectivity, minimum spanning trees, shortest paths, maximal independent sets, and finding subgraphs, showing that many of these problems can be solved in $\tilde{O}(n/k)$ rounds; this shows that one can achieve speedup nearly linear in $k$. To complement our upper bounds, we present lower bounds on the round complexity that quantify the fundamental limitations of solving graph problems distributively. We first show a lower bound of $\Omega(n/k)$ rounds for computing a spanning tree of the input graph. This result implies the same bound for other fundamental problems such as computing a minimum spanning tree, breadth-first tree, or shortest paths tree. We also show a $\tilde \Omega(n/k^2)$ lower bound for connectivity, spanning tree verification and other related problems. The latter lower bounds follow from the development and application of novel results in a random-partition variant of the classical communication complexity model. - Open Access
- 20 January 2022
- Published by Springer Nature in Distributed Computing
- Vol. 35 (2) , 165-183
Equivalence classes and conditional hardness in massively parallel computations
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 versus two cycles problem. This is unlike the traditional arguments based on conjectures about complexity classes (e.g., $$\textsf {P}\ne \textsf {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 $$\textsf {MPC}(o(\log N))$$ , and the standard space complexity classes $$\textsf {L}$$ and $$\textsf {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. Specifically, our main results are as follows. Lower bounds conditioned on the one cycle versus two cycles conjecture can be instead argued under the $$\textsf {L}\nsubseteq \textsf {MPC}(o(\log N))$$ conjecture: these two assumptions are equivalent, and refuting either of them would lead to $$o(\log N)$$ -round MPC algorithms for a large number of challenging problems, including list ranking, minimum cut, and planarity testing. In fact, we show that these problems and many others require asymptotically the same number of rounds as the seemingly much easier problem of distinguishing between a graph being one cycle or two cycles. Many lower bounds previously argued under the one cycle versus two cycles conjecture can be argued under an even more robust (thus harder to refute) conjecture, namely $$\textsf {NL}\nsubseteq \textsf {MPC}(o(\log N))$$ . Refuting this conjecture would lead to $$o(\log N)$$ -round MPC algorithms for an even larger set of problems, including all-pairs shortest paths, betweenness centrality, and all aforementioned ones. Lower bounds under this conjecture hold for problems such as perfect matching and network flow.- 20 January 2022
- Published by Springer Nature in Distributed Computing
- Vol. 35 (2) , 165-183
Open AccessEquivalence classes and conditional hardness in massively parallel computations
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 versus two cycles problem. This is unlike the traditional arguments based on conjectures about complexity classes (e.g., $$\textsf {P}\ne \textsf {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 $$\textsf {MPC}(o(\log N))$$ , and the standard space complexity classes $$\textsf {L}$$ and $$\textsf {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. Specifically, our main results are as follows. Lower bounds conditioned on the one cycle versus two cycles conjecture can be instead argued under the $$\textsf {L}\nsubseteq \textsf {MPC}(o(\log N))$$ conjecture: these two assumptions are equivalent, and refuting either of them would lead to $$o(\log N)$$ -round MPC algorithms for a large number of challenging problems, including list ranking, minimum cut, and planarity testing. In fact, we show that these problems and many others require asymptotically the same number of rounds as the seemingly much easier problem of distinguishing between a graph being one cycle or two cycles. Many lower bounds previously argued under the one cycle versus two cycles conjecture can be argued under an even more robust (thus harder to refute) conjecture, namely $$\textsf {NL}\nsubseteq \textsf {MPC}(o(\log N))$$ . Refuting this conjecture would lead to $$o(\log N)$$ -round MPC algorithms for an even larger set of problems, including all-pairs shortest paths, betweenness centrality, and all aforementioned ones. Lower bounds under this conjecture hold for problems such as perfect matching and network flow. - 1 March 2020
- Published by Elsevier in Theoretical Computer Science
- Vol. 810, 82-95
Message lower bounds via efficient network synchronization
- 1 March 2020
- Published by Elsevier in Theoretical Computer Science
- Vol. 810, 82-95
Message lower bounds via efficient network synchronization
- Open Access
Equivalence Classes and Conditional Hardness in Massively Parallel Computations
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., $\textsf{P} \neq \textsf{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 $\textsf{MPC}(o(\log N))$, and some standard classes concerning space complexity, namely $\textsf{L}$ and $\textsf{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.Open AccessEquivalence Classes and Conditional Hardness in Massively Parallel Computations
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., $\textsf{P} \neq \textsf{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 $\textsf{MPC}(o(\log N))$, and some standard classes concerning space complexity, namely $\textsf{L}$ and $\textsf{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. - Open Access
- 15 November 2019
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 16 (1) , 1-27
A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
This article presents a randomized (Las Vegas) distributed algorithm that constructs a minimum spanning tree (MST) in weighted networks with optimal (up to polylogarithmic factors) time and message complexity. This algorithm runs in Õ( D + √ n ) time and exchanges Õ( m ) messages (both with high probability), where n is the number of nodes of the network, D is the hop-diameter, and m is the number of edges. This is the first distributed MST algorithm that matches simultaneously the time lower bound of Ω ˜ ( D + √ n ) [10] and the message lower bound of Ω ( m ) [31], which both apply to randomized Monte Carlo algorithms. The prior time and message lower bounds are derived using two completely different graph constructions; the existing lower-bound construction that shows one lower bound does not work for the other. To complement our algorithm, we present a new lower-bound graph construction for which any distributed MST algorithm requires both Ω ˜ ( D + √ n ) rounds and Ω ( m ) messages.
- 15 November 2019
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Algorithms
- Vol. 16 (1) , 1-27
Open AccessA Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees
This article presents a randomized (Las Vegas) distributed algorithm that constructs a minimum spanning tree (MST) in weighted networks with optimal (up to polylogarithmic factors) time and message complexity. This algorithm runs in Õ( D + √ n ) time and exchanges Õ( m ) messages (both with high probability), where n is the number of nodes of the network, D is the hop-diameter, and m is the number of edges. This is the first distributed MST algorithm that matches simultaneously the time lower bound of Ω ˜ ( D + √ n ) [10] and the message lower bound of Ω ( m ) [31], which both apply to randomized Monte Carlo algorithms. The prior time and message lower bounds are derived using two completely different graph constructions; the existing lower-bound construction that shows one lower bound does not work for the other. To complement our algorithm, we present a new lower-bound graph construction for which any distributed MST algorithm requires both Ω ˜ ( D + √ n ) rounds and Ω ( m ) messages.
- 22 March 2019
- Published by Springer Nature in Algorithmica
- Vol. 81 (7) , 2917-2933
A ${o}\mathopen {}\left( n\right) \mathclose {}$-Competitive Deterministic Algorithm for Online Matching on a Line- 22 March 2019
- Published by Springer Nature in Algorithmica
- Vol. 81 (7) , 2917-2933
A ${o}\mathopen {}\left( n\right) \mathclose {}$-Competitive Deterministic Algorithm for Online Matching on a Line- 1 December 2015
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-4
The power of heterogeneity in Near-Threshold Computing
One potential method to attain more energy-efficient circuits with the current technology is Near-Threshold Computing. However, this energy savings comes at a cost of increased functional failure, which necessitates that circuits must be more fault-tolerant, and thus contain more gates. Thus, achieving energy savings with Near-Threshold Computing involves properly balancing the energy used per gate with the number of gates used. We consider both the setting where the supply voltages must be homogeneous and the setting where they may be heterogeneous. We show that, for small circuit error bounds, there are many natural functions that can be computed with a log factor less energy by heterogeneous circuits than is possible with homogeneous circuits, and that this result is tight for many functions. In contrast, we show that there are relations that can be computed with a log-squared factor less energy by heterogeneous circuits than is possible with homogeneous circuits.
- 1 December 2015
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-4
The power of heterogeneity in Near-Threshold Computing
One potential method to attain more energy-efficient circuits with the current technology is Near-Threshold Computing. However, this energy savings comes at a cost of increased functional failure, which necessitates that circuits must be more fault-tolerant, and thus contain more gates. Thus, achieving energy savings with Near-Threshold Computing involves properly balancing the energy used per gate with the number of gates used. We consider both the setting where the supply voltages must be homogeneous and the setting where they may be heterogeneous. We show that, for small circuit error bounds, there are many natural functions that can be computed with a log factor less energy by heterogeneous circuits than is possible with homogeneous circuits, and that this result is tight for many functions. In contrast, we show that there are relations that can be computed with a log-squared factor less energy by heterogeneous circuits than is possible with homogeneous circuits.