Michele Scquizzato

University of Padova

Department of Mathematics

Via Trieste 63, 35121 Padova, Italy

room 412, 4th floor

+39 049 827 1333

scquizza@math.unipd.it

DBLP

Google Scholar

Department of Mathematics

Via Trieste 63, 35121 Padova, Italy

room 412, 4th floor

+39 049 827 1333

scquizza@math.unipd.it

DBLP

Google Scholar

About Me

I am an assistant professor of computer science at University of Padova.

I received my Ph.D. from University of Padova in 2013, advised by Gianfranco Bilardi. Then, I was a post-doctoral researcher at University of Pittsburgh (2013-2014), working with Kirk Pruhs, at University of Houston (2014-2017), working with Gopal Pandurangan, and at KTH Royal Institute of Technology (2017-2018), working with Danupon Nanongkai.

I am interested in the design and analysis of algorithms.

*Prospective students: I am currently looking for highly motivated students with a strong background in theoretical computer science and mathematics.*

I received my Ph.D. from University of Padova in 2013, advised by Gianfranco Bilardi. Then, I was a post-doctoral researcher at University of Pittsburgh (2013-2014), working with Kirk Pruhs, at University of Houston (2014-2017), working with Gopal Pandurangan, and at KTH Royal Institute of Technology (2017-2018), working with Danupon Nanongkai.

I am interested in the design and analysis of algorithms.

Publications

Preprints

Enoch Peserico and Michele Scquizzato

**Matching on the Line Admits No o(√log n)-Competitive Algorithm**
[arXiv]

**Tight Bounds for Parallel Paging and Green Paging**
[link]
[pdf]

In Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)

Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, and Michele Scquizzato

**Brief Announcement: Green Paging and Parallel Paging**
[link]
[pdf]
[video]

In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020)

Danupon Nanongkai and Michele Scquizzato

**Equivalence Classes and Conditional Hardness in Massively Parallel Computations**
[link]
[pdf]
[arXiv]

In Proceedings of the 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Gopal Pandurangan, Peter Robinson, and Michele Scquizzato

**On the Distributed Complexity of Large-Scale Graph Computations**
[link]
[pdf]
[arXiv]

In Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2018)

*Invited to the special issue of ACM Transactions on Parallel Computing for SPAA 2018*

Gopal Pandurangan, Peter Robinson, and Michele Scquizzato

**A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees**
[link]
[pdf]
[arXiv]
[poster]

In Proceedings of the 49th Annual ACM Symposium on the Theory of Computing (STOC 2017)

Also a contributed presentation at the 3rd Highlights of Algorithms (HALG 2018)

Gopal Pandurangan, David Peleg, and Michele Scquizzato

**Message Lower Bounds via Efficient Network Synchronization**
[link]
[pdf]

In Proceedings of the 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO 2016)

*Invited to the special issue of Theoretical Computer Science for SIROCCO 2016*

Gopal Pandurangan, Peter Robinson, and Michele Scquizzato

**Fast Distributed Algorithms for Connectivity and MST in Large Graphs**
[link]
[pdf]
[arXiv]

In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016)

*Invited to the special issue of ACM Transactions on Parallel Computing for SPAA 2016*

Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, Kevin Schewior, and Michele Scquizzato

**Chasing Convex Bodies and Functions**
[link]
[pdf]

In Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN 2016)

Neal Barcelo, Michael Nugent, Kirk Pruhs, and Michele Scquizzato

**The Power of Heterogeneity in Near-Threshold Computing**
[link]
[pdf]

In Proceedings of the 6th International Green and Sustainable Computing Conference (IGSC 2015)

James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh, and Michele Scquizzato

**Toward Optimal Bounds in the Congested Clique: Graph Connectivity and MST**
[link]
[pdf]

In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC 2015)

Neal Barcelo, Michael Nugent, Kirk Pruhs, and Michele Scquizzato

**Almost All Functions Require Exponential Energy**
[link]
[pdf]

In Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015)

Neal Barcelo, Peter Kling, Michael Nugent, Kirk Pruhs, and Michele Scquizzato

**On the Complexity of Speed Scaling**
[link]
[pdf]

In Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015)

Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, and Michele Scquizzato

**Complexity-Theoretic Obstacles to Achieving Energy Savings with Near-Threshold Computing**
[link]
[pdf]

In Proceedings of the 5th International Green Computing Conference (IGCC 2014)

Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, and Michele Scquizzato

**A o(n)-Competitive Deterministic Algorithm for Online Matching on a Line**
[link]
[pdf]

In Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA 2014)

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**
[link]
[pdf]

In Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Michele Scquizzato and Francesco Silvestri

**Communication Lower Bounds for Distributed-Memory Computations**
[link]
[pdf]
[arXiv]

In Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Preliminarily presented at the 5th Workshop on Massive Data Algorithmics (MASSIVE 2013)

Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, and Michele Scquizzato

**Energy-Efficient Circuit Design**
[link]
[pdf]

In Proceedings of the 5th conference on Innovations in Theoretical Computer Science (ITCS 2014)

Gianfranco Bilardi, Michele Scquizzato, and Francesco Silvestri

**A Lower Bound Technique for Communication on BSP with Application to the FFT**
[link]
[pdf]

In Proceedings of the 18th International European Conference on Parallel and Distributed Computing (Euro-Par 2012)

Paolo Bertasi, Alberto Pettarin, Michele Scquizzato, and Francesco Silvestri

**A Novel Resource-Driven Job Allocation Scheme for Desktop Grid Environments**
[link]

In Proceedings of the 5th Symposium on Trustworthy Global Computing (TGC 2010)

**On the Distributed Complexity of Large-Scale Graph Computations**

ACM Transactions on Parallel Computing, to appear

Gopal Pandurangan, David Peleg, and Michele Scquizzato

**Message Lower Bounds via Efficient Network Synchronization**
[link]
[pdf]

Theoretical Computer Science 810:82-95, 2020

Gopal Pandurangan, Peter Robinson, and Michele Scquizzato

**A Time- and Message-Optimal Distributed Algorithm for Minimum Spanning Trees**
[link]
[pdf]

ACM Transactions on Algorithms 16(1), Article 13, 2020

Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, and Michele Scquizzato

**A o(n)-Competitive Deterministic Algorithm for Online Matching on a Line**
[link]
[pdf]

Algorithmica 81(7):2917-2933, 2019

Gopal Pandurangan, Peter Robinson, and Michele Scquizzato

**Fast Distributed Algorithms for Connectivity and MST in Large Graphs**
[link]
[pdf]

ACM Transactions on Parallel Computing 5(1), Article 4, 2018

Gianfranco Bilardi, Michele Scquizzato, and Francesco Silvestri

**A Lower Bound Technique for Communication in BSP**
[link]
[arXiv]

ACM Transactions on Parallel Computing 4(3), Article 14, 2018

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**
[link]
[pdf]

Algorithmica 79(2):568-597, 2017

Gianfranco Bilardi, Andrea Pietracaprina, Geppino Pucci, Michele Scquizzato, and Francesco Silvestri

**Network-Oblivious Algorithms**
[link]
[pdf]

Journal of the ACM 63(1), Article 3, 2016

**The Distributed Minimum Spanning Tree Problem**
[link]
[pdf]

Bulletin of the EATCS 125:52-80, 2018

Conference Papers

Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, and Michele ScquizzatoIn Proceedings of the 32nd ACM-SIAM Symposium on Discrete Algorithms (SODA 2021)

Kunal Agrawal, Michael A. Bender, Rathish Das, William Kuszmaul, Enoch Peserico, and Michele Scquizzato

In Proceedings of the 32nd ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2020)

Danupon Nanongkai and Michele Scquizzato

In Proceedings of the 23rd International Conference on Principles of Distributed Systems (OPODIS 2019)

Gopal Pandurangan, Peter Robinson, and Michele Scquizzato

In Proceedings of the 30th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2018)

Gopal Pandurangan, Peter Robinson, and Michele Scquizzato

In Proceedings of the 49th Annual ACM Symposium on the Theory of Computing (STOC 2017)

Also a contributed presentation at the 3rd Highlights of Algorithms (HALG 2018)

Gopal Pandurangan, David Peleg, and Michele Scquizzato

In Proceedings of the 23rd International Colloquium on Structural Information and Communication Complexity (SIROCCO 2016)

Gopal Pandurangan, Peter Robinson, and Michele Scquizzato

In Proceedings of the 28th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA 2016)

Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, Kevin Schewior, and Michele Scquizzato

In Proceedings of the 12th Latin American Theoretical Informatics Symposium (LATIN 2016)

Neal Barcelo, Michael Nugent, Kirk Pruhs, and Michele Scquizzato

In Proceedings of the 6th International Green and Sustainable Computing Conference (IGSC 2015)

James W. Hegeman, Gopal Pandurangan, Sriram V. Pemmaraju, Vivek B. Sardeshmukh, and Michele Scquizzato

In Proceedings of the 2015 ACM Symposium on Principles of Distributed Computing (PODC 2015)

Neal Barcelo, Michael Nugent, Kirk Pruhs, and Michele Scquizzato

In Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015)

Neal Barcelo, Peter Kling, Michael Nugent, Kirk Pruhs, and Michele Scquizzato

In Proceedings of the 40th International Symposium on Mathematical Foundations of Computer Science (MFCS 2015)

Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, and Michele Scquizzato

In Proceedings of the 5th International Green Computing Conference (IGCC 2014)

Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, and Michele Scquizzato

In Proceedings of the 12th Workshop on Approximation and Online Algorithms (WAOA 2014)

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

In Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Michele Scquizzato and Francesco Silvestri

In Proceedings of the 31st Symposium on Theoretical Aspects of Computer Science (STACS 2014)

Preliminarily presented at the 5th Workshop on Massive Data Algorithmics (MASSIVE 2013)

Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, and Michele Scquizzato

In Proceedings of the 5th conference on Innovations in Theoretical Computer Science (ITCS 2014)

Gianfranco Bilardi, Michele Scquizzato, and Francesco Silvestri

In Proceedings of the 18th International European Conference on Parallel and Distributed Computing (Euro-Par 2012)

Paolo Bertasi, Alberto Pettarin, Michele Scquizzato, and Francesco Silvestri

In Proceedings of the 5th Symposium on Trustworthy Global Computing (TGC 2010)

Journal Articles

Gopal Pandurangan, Peter Robinson, and Michele ScquizzatoACM Transactions on Parallel Computing, to appear

Gopal Pandurangan, David Peleg, and Michele Scquizzato

Theoretical Computer Science 810:82-95, 2020

Gopal Pandurangan, Peter Robinson, and Michele Scquizzato

ACM Transactions on Algorithms 16(1), Article 13, 2020

Antonios Antoniadis, Neal Barcelo, Michael Nugent, Kirk Pruhs, and Michele Scquizzato

Algorithmica 81(7):2917-2933, 2019

Gopal Pandurangan, Peter Robinson, and Michele Scquizzato

ACM Transactions on Parallel Computing 5(1), Article 4, 2018

Gianfranco Bilardi, Michele Scquizzato, and Francesco Silvestri

ACM Transactions on Parallel Computing 4(3), Article 14, 2018

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

Algorithmica 79(2):568-597, 2017

Gianfranco Bilardi, Andrea Pietracaprina, Geppino Pucci, Michele Scquizzato, and Francesco Silvestri

Journal of the ACM 63(1), Article 3, 2016

Surveys

Gopal Pandurangan, Peter Robinson, and Michele ScquizzatoBulletin of the EATCS 125:52-80, 2018

Professional Service

Program Committees:
Euro-Par 2020,
IPDPS 2020,
IPDPS 2019,
ICDCN 2019,
Euro-Par 2017,
ICDCN 2016,
IPDPS 2015

Teaching

At University of Padova:

Advanced Algorithms (Spring 2021, Spring 2020)

Algorithms and Data Structures (Spring 2021, Spring 2020, Spring 2019)

At University of Houston:

COSC 3320: Algorithms and Data Structures (Spring 2017, Spring 2016, Summer 2015)

COSC 6326: Distributed Algorithms (Spring 2017)

Advanced Algorithms (Spring 2021, Spring 2020)

Algorithms and Data Structures (Spring 2021, Spring 2020, Spring 2019)

At University of Houston:

COSC 3320: Algorithms and Data Structures (Spring 2017, Spring 2016, Summer 2015)

COSC 6326: Distributed Algorithms (Spring 2017)