2 citations · 3 across the 4 of their papers we have counts for
5 papers · 1 filter
Settling The Round Complexity of Byzantine Agreement Against a Full-Information, Adaptive Adversary
Yuval Efron
We prove that every randomized synchronous Byzantine Agreement protocol in the full-information, strongly adaptive adversary model, secure against corrupt parties, has worst-ca…
Juggernaut: Efficient Crypto-Agnostic Byzantine Agreement
Daniel Collins, Yuval Efron, Jovan Komatovic
It is well known that a trusted setup allows one to solve the Byzantine agreement problem in the presence of corruptions, bypassing the setup-free barrier. Alas, th…
Distributed Distance Approximation
Bertie Ancona, Keren Censor-Hillel, Mina Dalirrooyfard +2
Diameter, radius and eccentricities are fundamental graph parameters, which are extensively studied in various computational settings. Typically, computing approximate answers can…
Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST
Yuval Efron, Ofer Grossman, Seri Khoury
By far the most fruitful technique for showing lower bounds for the CONGEST model is reductions to two-party communication complexity. This technique has yielded nearly tight resul…
Classification of distributed binary labeling problems
Alkida Balliu, Sebastian Brandt, Yuval Efron +4
We present a complete classification of the deterministic distributed time complexity for a family of graph problems: binary labeling problems in trees. These are locally checkable…