46 citations · 67 across the 18 of their papers we have counts for
6 papers · 1 filter
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…
A Deterministic Distributed Algorithm for Exact Weighted All-Pairs Shortest Paths in 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…
Dynamic graph connectivity with improved worst case update time and sublinear space
David Gibb, Bruce Kapron, Valerie King +1
This paper considers fully dynamic graph algorithms with both faster worst case update time and sublinear space. The fully dynamic graph connectivity problem is the following: give…
Quorums Quicken Queries: Efficient Asynchronous Secure Multiparty Computation
Varsha Dani, Valerie King, Mahnush Movahedi +1
We describe an asynchronous algorithm to solve secure multiparty computation (MPC) over n players, when strictly less than a 1/8 fraction of the players are controlled by a static…
Secure Multi-Party Computation in Large Networks
Varsha Dani, Valerie King, Mahnush Movahedi +2
We describe scalable protocols for solving the secure multi-party computation (MPC) problem among a large number of parties. We consider both the synchronous and the asynchronous c…
Sleeping on the Job: Energy-Efficient Broadcast for Radio Networks
Valerie King, Cynthia Phillips, Jared Saia +1
We address the problem of minimizing power consumption when performing reliable broadcast on a radio network under the following popular model. Each node in the network is located…