6 papers · 1 filter
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.…
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…
A Simple Lower Bound for Set Agreement in Dynamic Networks
Pierre Fraigniaud, Minh Hang Nguyen, Ami Paz
Given a positive integer , -set agreement is the distributed task in which each process in a group of processing nodes starts with an input value in the…
-Center Clustering in Distributed Models
Leyla Biabani, Ami Paz
The -center problem is a central optimization problem with numerous applications for machine learning, data mining, and communication networks. Despite extensive study in variou…