4 papers
Settling The Round Complexity of Byzantine Agreement Against a Full-Information, Adaptive Adversary
Yuval Efron
The paper establishes a new lower bound on the expected round complexity of randomized synchronous Byzantine Agreement protocols against a full‑information, strongly adaptive adver…
Optimal Good-Case Latency for Sleepy Consensus
Yuval Efron, Joachim Neu, Ling Ren +1
In the context of Byzantine consensus problems such as Byzantine broadcast (BB) and Byzantine agreement (BA), the good-case setting aims to study the minimal possible latency of a…
Unitary Complexity and the Uhlmann Transformation Problem
John Bostanci, Yuval Efron, Tony Metger +3
State transformation problems such as compressing quantum information or breaking quantum commitments are fundamental quantum tasks. However, their computational difficulty cannot…
A Simple Algorithm for Dynamic Carpooling with Recourse
Yuval Efron, Shyamal Patel, Cliff Stein
We give an algorithm for the fully-dynamic carpooling problem with recourse: Edges arrive and depart online from a graph with nodes according to an adaptive adversary. Our…