Byzantine Agreement in Polynomial Time
March 8, 2013, 6:25 pm
Filed under: Uncategorized | Tags: , ,

I just put up a paper from Val and I that will appear in this upcoming STOC. The paper is:

Byzantine Agreement in Polynomial Expected Time

It gives the first expected polynomial time algorithm for Byzantine agreement as it was originally posed: adaptive adversary, full-information model, with asynchronous communication. ┬áIt’s something that we’ve both been working on for many years.