7 papers
Polynomial Time Local Decision Revisited
Laurent Feuilloley, Soumyadeep Paul, Ami Paz
We consider three classification systems for distributed decision tasks: With unbounded computation and certificates, defined by Balliu, D'Angelo, Fraigniaud, and Olivetti [JCSS'18…
Lower Bounds for -Set Agreement in Fault-Prone Networks
Pierre Fraigniaud, Minh Hang Nguyen, Ami Paz +2
We develop a new lower bound for k-set agreement in synchronous message-passing systems connected by an arbitrary directed communication network, where up to t processes may crash.…
Semi-Streaming Algorithms for Graph Property Certification
Avinandan Das, Pierre Fraigniaud, Ami Paz +1
We introduce the {\em certification} of solutions to graph problems when access to the input is restricted. This topic has received a lot of attention in the distributed computing…
Smoothed Analysis of Dynamic Graph Algorithms
Uri Meir, Ami Paz
Recent years have seen significant progress in the study of dynamic graph algorithms, and most notably, the introduction of strong lower bound techniques for them (e.g., Henzinger,…
Distributed Non-Interactive Zero-Knowledge Proofs
Alex B. Grilo, Ami Paz, Mor Perry
Distributed certification is a set of mechanisms that allows an all-knowing prover to convince the units of a communication network that the network's state has some desired proper…
Agreement Tasks in Fault-Prone Synchronous Networks of Arbitrary Structure
Pierre Fraigniaud, Minh Hang Nguyen, Ami Paz
Consensus is arguably the most studied problem in distributed computing as a whole, and particularly in the distributed message-passing setting. In this latter framework, research…