Valerie King

activity

20072022

most citedBreaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary

46 citations · 67 across the 18 of their papers we have counts for

collaborators

Showing 2018Show all

3 papers · 1 filter

cs.DC2018★ 2 cited

Correction to Byzantine Agreement in Expected Polynomial Time, JACM 2016

Valerie King, Jared Saia

This is a correction by the authors to "Byzantine Agreement in Expected Polynomial Time" which appeared in the Journal of the ACM in 2016. It corrects a failure in the paper to con…

cs.DC2018★ 1 cited

Broadcast and minimum spanning tree with $o (m)$ messages in the asynchronous CONGEST model

Ali Mashreghi, Valerie King

We provide the first asynchronous distributed algorithms to compute broadcast and minimum spanning tree with $o (m)$ bits of communication, in a graph with $n$ nodes and $m$ edges.…

cs.DS2018★ 1 cited

A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in $O ~ (n^{3/2})$ Rounds

Udit Agarwal, Vijaya Ramachandran, Valerie King +1

We present a deterministic distributed algorithm to compute all-pairs shortest paths(APSP) in an edge-weighted directed or undirected graph. Our algorithm runs in $\tilde{O}(n^{3/2…

Correction to Byzantine Agreement in Expected Polynomial Time, JACM 2016

Broadcast and minimum spanning tree with o(m) messages in the asynchronous CONGEST model

A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in O~(n3/2) Rounds

Broadcast and minimum spanning tree with $o (m)$ messages in the asynchronous CONGEST model

A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in $O ~ (n^{3/2})$ Rounds