46 citations · 67 across the 18 of their papers we have counts for
22 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…
Bankrupting DoS Attackers
Trisha Chakraborty, Abir Islam, Valerie King +3
Can we make a denial-of-service attacker pay more than the server and honest clients? Consider a model where a server sees a stream of jobs sent by either honest clients or an adve…
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…
Broadcast and minimum spanning tree with 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 bits of communication, in a graph with nodes and edges.…
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…
Construction and impromptu repair of an MST in a distributed network with o(m) communication
Valerie King, Shay Kutten, Mikkel Thorup
In the CONGEST model, a communications network is an undirected graph whose nodes are processors and whose edges are the communications links between processors. At any giv…
Kinetic -Semi-Yao Graph and its Applications
Zahed Rahmati, Mohammad Ali Abam, Valerie King +1
This paper introduces a new proximity graph, called the -Semi-Yao graph (-SYG), on a set of points in , which is a supergraph of the -nearest neighbor gr…
Kinetic Reverse -Nearest Neighbor Problem
Zahed Rahmati, Valerie King, Sue Whitesides
This paper provides the first solution to the kinetic reverse -nearest neighbor (\rknn) problem in , which is defined as follows: Given a set of moving poi…
A Simple, Faster Method for Kinetic Proximity Problems
Zahed Rahmati, Mohammad Ali Abam, Valerie King +2
For a set of points in the plane, this paper presents simple kinetic data structures (KDS's) for solutions to some fundamental proximity problems, namely, the all nearest neigh…
Proceedings Ninth International Workshop on Foundations of Mobile Computing
Keren Censor-Hillel, Valerie King
Mobile communication has become a vigorous field of research in computer science, due to the wide spreading of mobile technologies, applications and services. The intertwining of c…
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…
Kinetic Data Structures for the Semi-Yao Graph and All Nearest Neighbors in R^d
Zahed Rahmati, Mohammad Ali Abam, Valerie King +1
This paper presents a simple kinetic data structure for maintaining all the nearest neighbors of a set of moving points in , where the trajectory of each point is…
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…
They Know Where You Live!
Kazem Jahanbakhsh, Valerie King, Gholamali C. Shoja
In this paper, we demonstrate the possibility of predicting people's hometowns by using their geotagged photos posted on Flickr website. We employ Kruskal's algorithm to cluster ph…
A Resource-Competitive Jamming Defense
Valerie King, Seth Pettie, Jared Saia +1
Consider a scenario where Alice wishes to send a message to Bob in a time-slotted wireless network. However, there exists an adversary, Carol, who aims to prevent the transmiss…
Breaking the O(n^2) Bit Barrier: Scalable Byzantine agreement with an Adaptive Adversary
Valerie King, Jared Saia
We describe an algorithm for Byzantine agreement that is scalable in the sense that each processor sends only bits, where is the total number of processor…
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…