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 (Winter 2023-2024)
I will present our paper 𝑘-Center Clustering in Distributed Models in SIROCCO'24. With Leyla Biabiani.
Our paper The Time Complexity of Consensus Under Oblivious Message Adversaries was published in Algorithmica (arxiv). With Kyrill Winkler, Hugo Rincon Galeana, Stefan Schmid, and Ulrich Schmid.
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 (to appear)
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
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
The Augmentation-Speed Tradeoff for Consistent Network Updates
Monika Henzinger, Ami Paz, Arash Pourdamghani, and Stefan Schmid
A Speedup Theorem for Asynchronous Computation with Applications to Consensus and Approximate Agreement
Pierre Fraigniaud, Ami Paz, and Sergio Rajsbaum
Playing Guess Who with Your Kids
Ami Paz and Liat Peterfreund
Fine-Grained Complexity Lower Bounds for Families of Dynamic Graphs
Monika Henzinger, Ami Paz, A. R. Sricharan
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
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
Based on our paper "Simple and Fast Distributed Computation of Betweenness Centrality"The Topology of Local Computing in Networks
Pierre Fraigniaud and Ami Paz
ICALP 2020 track B; arXiv
Simple and Fast Distributed Computation of Betweenness Centrality
Pierluigi Crescenzi, Pierre Fraigniaud, and Ami Paz
Synchronous t-Resilient Consensus in Arbitrary Graphs
Armando Castañeda, Pierre Fraigniaud, Ami Paz, Sergio Rajsbaum, Matthieu Roy and Corentin Travers
Information and Computation, SSS 2019 (best paper award), PDF
Trade-Offs in Distributed Interactive Proofs
Pierluigi Crescenzi, Pierre Fraigniaud, and Ami Paz
Hardness of Distributed Optimization
Nir Bachrach, Keren Censor-Hillel, Michal Dory, Yuval Efron, Dean Leitersdorf and Ami Paz
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
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 KhouryThe 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
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 arXivApproximate 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
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
Counting-Based Impossibility Proofs for Set Agreement and Renaming
Hagit Attiya and Ami Paz
Academic Activities
Program Committees
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