Ami Paz

I am a computer scientist interested in distributed graph algorithms, topological methods in distributed computing, dynamic graph algorithms, and the theory of computing in general.

I am a research scientist (chargé de recherche) in LISN lab - CNRS and Paris-Saclay University. We are always happy to host graduate students and postdocs interested in distributed computing and related topics.

Contact: amipaz.cs@gmail.com

The cover photo was taken by me at Méert, Lille. My photo was taken by Thaler Tamás.

News (Spring 2025)

Our paper A speedup theorem for asynchronous computation with applications to consensus and approximate agreement was published in the Distributed Computing journal's PODC'22 special issue. With Pierre Fraigniaud and Sergio Rejsbaum

Minh Hang Nguyen presented our paper Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structure in STACS'25 (arXiv). With Pierre Fraigniaud and Minh Hang Nguyen

Minh Hang Nguyen presented our paper A Simple Lower Bound for Set Agreement in Dynamic Networks in SOSA'25 (arXiv). With Pierre Fraigniaud and Minh Hang Nguyen

Our paper The Topology of Local Computing in Networks was published in the Journal of Applied and Computational Topology (APCT; see also arXiv). With Pierre Fraigniaud

New manuscript: Smoothed Analysis of Dynamic Graph Algorithms. With Uri Meir (arXiv)

Publications

See also my DBLP entry and arXiv. Author names are mostly alphabetically ordered, as is the common practice in theoretical computer science.

𝑘-Center Clustering in Distributed Models

Leyla Biabiani and Ami Paz

SIROCCO'24, arXiv

One Step Forward, One Step Back: FLP-Style Proofs and the Round-Reduction Technique for Colorless Tasks

Hagit Attiya, Pierre Fraigniaud, Ami Paz, Sergio Rajsbaum

DISC'23, arXiv

The Time Complexity of Consensus Under Oblivious Message Adversaries

Kyrill Winkler, Ami Paz, Hugo Rincon Galeana, Stefan Schmid, Ulrich Schmid

ITCS 2023 (Kyrill's talk), Algorithmica, arxiv

Sinkless Orientation Made Simple

Alkida Balliu, Janne H. Korhonen, Fabian Kuhn, Henrik Lievonen, Dennis Olivetti, Shreyas Pai, Ami Paz, Joel Rybicki, Stefan Schmid, Jan Studený, Jukka Suomela, Jara Uitto

SOSA'23, arxiv

The Augmentation-Speed Tradeoff for Consistent Network Updates

Monika Henzinger, Ami Paz, Arash Pourdamghani, and Stefan Schmid

ACM SIGCOMM SOSR 2022, arXiv

A Speedup Theorem for Asynchronous Computation with Applications to Consensus and Approximate Agreement

Pierre Fraigniaud, Ami Paz, and Sergio Rajsbaum

Distributed Computing, ACM PODC 2022, arXiv

Playing Guess Who with Your Kids

Ami Paz and Liat Peterfreund

FUN'22, TCS'24

Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs

Monika Henzinger, Ami Paz, A. R. Sricharan

ESA'22 (track A), arXiv

Sinkless orientation is hard also in the supported LOCAL model

Janne H. Korhonen, Ami Paz, Joel Rybicki, Stefan Schmid, and Jukka Suomela

arXiv, BA at DISC '21, Janne's presentation

Input-Dynamic Distributed Algorithms for Communication Networks

Klaus-Tycho Foerster, Janne H. Korhonen, Ami Paz, Joel Rybicki, and Stefan Schmid

POMACS 2021; ACM SIGMETRICS '21 (preprint); full version on arXiv

On the Complexity of Load Balancing in Dynamic Networks

Seth Gilbert, Uri Meir, Ami Paz, and Gregory Schwartzman

ACM SPAA'21 (Gregory's talk); full version on arXiv

On the Complexity of Weight-Dynamic Network Algorithms

Monika Henzinger , Ami Paz, and Stefan Schmid

IFIP Networking; full version on arXiv

Distributed Quantum Proofs for Replicated Data

Pierre Fraigniaud, François Le Gall, Harumichi Nishimura, and Ami Paz

QIP 2021 (Harumichi's talk); ITCS 2021 (my talk); BA at DISC 2020 (my talk); full version on arXiv

Fast Deterministic Algorithms for Highly-Dynamic Networks

Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov, Ami Paz, and Gregory Schwartzman

OPODIS 2020 (Victor's talk); full version on arXiv

Models of Smoothing in Dynamic Networks

Uri Meir, Ami Paz, and Gregory Schwartzman

DISC 2020; arXiv; my talk

Improved Hardness of Approximation of Diameter in the CONGEST Model

Ofer Grossman, Seri Khoury, and Ami Paz

DISC 2020 ; Seri's talk; mentioned in Oded's Goldreich's papers of choice list

Calcul distribué simple et efficace de la betweenness

Pierluigi Crescenzi, Pierre Fraigniaud and Ami Paz

ALGOTEL 2020

Based on our paper "Simple and Fast Distributed Computation of Betweenness Centrality"

The Topology of Local Computing in Networks

Pierre Fraigniaud and Ami Paz

JAPC [PDF], ICALP 2020 track B; arXiv

Simple and Fast Distributed Computation of Betweenness Centrality

Pierluigi Crescenzi, Pierre Fraigniaud, and Ami Paz

INFOCOM 2020, arXiv

Synchronous t-Resilient Consensus in Arbitrary Graphs

Armando Castañeda, Pierre Fraigniaud, Ami Paz, Sergio Rajsbaum, Matthieu Roy and Corentin Travers

Information and Computation (PDF), SSS 2019 (best paper award)

Trade-Offs in Distributed Interactive Proofs

Pierluigi Crescenzi, Pierre Fraigniaud, and Ami Paz

arXiv, DISC 2019

Hardness of Distributed Optimization

Nir Bachrach, Keren Censor-Hillel, Michal Dory, Yuval Efron, Dean Leitersdorf and Ami Paz

arXiv, PODC 2019

A Topological Perspective on Distributed Network Algorithms

Armando Castañeda, Pierre Fraigniaud, Ami Paz, Sergio Rajsbaum, Matthieu Roy and Corentin Travers

TCS 2021, SIROCCO 2019 (Invited talk); arXiv

Vérification de preuves distribuées: compromis temps-espace

Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen, Ami Paz and Mor Perry

ALGOTEL 2019 (best student paper award)

Based on our paper "Redundancy in Distributed Proofs"

Smaller Cuts, Higher Lower Bounds

Amir Abboud, Keren Censor-Hillel, Seri Khoury and Ami Paz

arXiv; ACM TALG

This paper is a merge of our paper "Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model", and the paper "Near-Linear Lower Bounds for Distributed Distance Computations, Even in Sparse Networks" by Abboud, Censor-Hillel and Khoury

The Sparsest Additive Spanner via Multiple Weighted BFS Trees

Keren Censor-Hillel, Ami Paz and Noam Ravid

TCS 2020; OPODIS 2018; arXiv; slides; HALG 2019 (short talk)

Redundancy in Distributed Proofs

Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen, Ami Paz and Mor Perry

Distributed Computing 2020; DISC 2018; arXiv; slides

Distributed Distance Computation and Related Topics

Ami Paz

PhD Thesis, Technion, 2017

Quadratic and Near-Quadratic Lower Bounds for the CONGEST Model

Keren Censor-Hillel, Seri Khoury and Ami Paz

DISC 2017; arXiv; HALG 2018 (short talk)

An updated version, merged with a paper by Abboud, Censor-Hillel and Khoury, is now available on arXiv

Approximate Proof-Labeling Schemes

Keren Censor-Hillel, Ami Paz and Mor Perry

TCS 2020; preliminary version at SIROCCO 2017; see also SIROCCO's pre-proceedings

A (2+ε)-Approximation for Maximum Weight Matching in the Semi-Streaming Model

Ami Paz and Gregory Schwartzman

TALG; preliminary version at SODA 2017 (best paper award and best student paper award); arxiv; HALG 2017 (invited talk); slides

Distributed Construction of Purely Additive Spanners

Keren Censor-Hillel, Telikepalli Kavitha, Ami Paz and Amir Yehudayoff

Distributed Computing 2018; preliminary version at DISC 2016; arxiv

Algebraic Methods in the Congested Clique

Keren Censor-Hillel, Petteri Kaski, Janne H. Korhonen, Christoph Lenzen, Ami Paz and Jukka Suomela

Distributed Computing 2019; preliminary version at PODC 2015; arxiv

Bremen Workshop Review

Ami Paz

SIGACT News 2013

Bounds on the Step and Namespace Complexity of Renaming

Hagit Attiya, Armando Castañeda, Maurice Herlihy and Ami Paz

SICOMP; preliminary version at PODC 2013 (best student paper award); slides

Counting-Based Impossibility Proofs for Distributed Tasks

Ami Paz

MSc Thesis, Technion, 2013

Counting-Based Impossibility Proofs for Set Agreement and Renaming

Hagit Attiya and Ami Paz

JPDC 2016; preliminary version at DISC 2012; slides

Academic Activities

Program Committees

The 44th ACM Symposium on Principles of Distributed Computing (ACM PODC) 2025
The 32nd International Colloquium on Structural Information and Communication Complexity (SIROCCO) 2025
The 43rd ACM Symposium on Principles of Distributed Computing (ACM PODC) 2024
The 31st International Colloquium on Structural Information and Communication Complexity (SIROCCO) 2024
The 25th International Conference on Principles of Distributed Systems (OPODIS) 2021
The 35th International Symposium on DIStributed Computing (DISC) 2021
The 18th IEEE International Conference on Sensing, Communication and Networking (IEEE SECON) 2021
The 39th ACM Symposium on Principles of Distributed Computing (ACM PODC) 2020
The 38th IEEE International Conference on Distributed Computing Systems, Distributed Algorithms & Theory Track (IEEE ICDCS) 2018

Organizer

10th French-Israeli Workshop on Foundations of Computer Science (FILOFOCS 2023)
FRAIGNIAUD workshop (Fundamental Research and Algorithmic Innovations in Graphs, Networks and the Internet, with Applications and Upcoming Directions), on the occasion of Pierre FRAIGNIAUD’s 60th birthday, 2022.
Technion CS Theory Lunch (2014-2016)

Journal Reviewer

SIAM Journal on Computing (SICOMP), SIAM Journal on Discrete Mathematics (SIDMA), ACM Transactions on Algorithms (TALG), Distributed Computing (DC), Algorithmica (Algo), Theoretical Computer Science (TCS), Theory of Computing Systems (ToCS), Information Processing Letters (IPL)

Conference Reviewer

ACM STOC, IEEE FOCS, ACM-SIAM SODA, ACM PODC, DISC, WWW, ITCS, SPAA, ICALP, OPODIS, STACS, SOSA, ESA, MFCS, ACDA, ISAAC, LATIN, FUN

Short Bio

I am a research scientist (chargé de recherche) in LISN lab - CNRS and Paris-Saclay University.

I did two years of post-doctoral research with Monika Henzinger and Stefan Schmid at the Faculty of Computer Science of the University of Vienna, and another two years with Pierre Fraigniaud at IRIF, Paris, under the interaction program of FSMP.

I earned my PhD under the supervision of Keren Censor-Hillel, and my MSc under the supervision of Hagit Attiya, both at the Computer Science Department, Technion, Israel.

Teaching

At the Parisian Master of Research in Computer Science (MPRI):

Distributed algorithms on networks (Lecturer)

At the University of Vienna:

Distributed and Parallel Algorithms (Lecturer)
Network Technologies (Teaching Assistant)

As a graduate student at the Technion, I was a teaching assistant in various courses:

Distributed Algorithms A: distributed graph algorithms
Distributed Algorithms B: shared memory systems
Modern Cryptology
Computability Theory
Logic and Set Theory
Combinatorics

Google Sites

Report abuse