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.
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 2023)
I am co-organizing FILOFOCS 2023 workshop in Paris, May 9-11. Registration is free and open until May 2nd.
Our paper The Time Complexity of Consensus Under Oblivious Message Adversaries (arxiv) was presented in ITCS 2023 (Kyrill's talk) With Hugo Rincon Galeana, Stefan Schmid, Ulrich Schmid, and Kyrill Winkler
Our paper Sinkless Orientation Made Simple (arxiv) was presented in SOSA 2023. With Alkida Balliu, Janne H. Korhonen, Fabian Kuhn, Henrik Lievonen, Dennis Olivetti, Shreyas Pai, Joel Rybicki, Stefan Schmid, Jan Studený, Jukka Suomela, Jara Uitto
Publications
See also my DBLP entry and arXiv. Author names are alphabetically ordered - this is the common practice in theoretical computer science.
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
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"Fast and Simple Deterministic Algorithms for Highly-Dynamic Networks
Keren Censor-Hillel, Neta Dafni, Victor I. Kolobov, Ami Paz and Gregory Schwartzman
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.
Until September 2021, I spent two years as a post-doctoral researcher at the Faculty of Computer Science, University of Vienna, working with Monika Henzinger and Stefan Schmid, and another two years as a post-doctoral researcher at IRIF, Paris, under the interaction program of FSMP, hosted by Pierre Fraigniaud.
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