7 citations · 7 across the 4 of their papers we have counts for
10 papers
Computing (1+epsilon)-Approximate Degeneracy in Sublinear Time
Valerie King, Alex Thomo, Quinton Yong
The problem of finding the degeneracy of a graph is a subproblem of the k-core decomposition problem. In this paper, we present a (1 + epsilon)-approximate solution to the degenera…
Communication Costs in a Geometric Communication Network
Sima Hajiaghaei Shanjani, Valerie King
A communication network is a graph in which each node has only local information about the graph and nodes communicate by passing messages along its edges. Here, we consider the {\…
Random -out subgraph leaves only inter-component edges
Jacob Holm, Valerie King, Mikkel Thorup +2
Each vertex of an arbitrary simple graph on vertices chooses random incident edges. What is the expected number of edges in the original graph that connect different connec…
Faster asynchronous MST and low diameter tree construction with sublinear communication
Ali Mashreghi, Valerie King
Building a spanning tree, minimum spanning tree (MST), and BFS tree in a distributed network are fundamental problems which are still not fully understood in terms of time and comm…
Scalable and Secure Computation Among Strangers: Resource-Competitive Byzantine Protocols
John Augustine, Valerie King, Anisur R. Molla +2
Motivated, in part, by the rise of permissionless systems such as Bitcoin where arbitrary nodes (whose identities are not known apriori) can join and leave at will, we extend estab…
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…