Arrow Research search

Author name cluster

Valerie King

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

20 papers
2 author rows

Possible papers

20

ECAI Conference 2025 Conference Paper

Polynomial-Time Algorithms for Fair Orientations of Chores

  • Kevin Hsu
  • Valerie King

This paper addresses the problem of finding fair orientations of graphs of chores, in which each vertex corresponds to an agent, each edge corresponds to a chore, and a chore has zero marginal utility to an agent if its corresponding edge is not incident to the vertex corresponding to the agent. Recently, Zhou et al. (IJCAI, 2024) analyzed the complexity of deciding whether graphs containing a mixture of goods and chores have EFX orientations, and conjectured that deciding whether graphs containing only chores have EFX orientations is NP-complete. We resolve this conjecture by giving polynomial-time algorithms that find EF1 and EFX orientations of graphs containing only chores if they exist, even if there are self-loops. Remarkably, our result demonstrates a surprising separation between the case of goods and the case of chores, because deciding whether graphs containing only goods have EFX orientations was shown to be NP-complete by Christodoulou et al. (EC, 2023). In addition, we show the EF1 and EFX orientation problems for multigraphs to be NP-complete.

Details

TCS Journal 2023 Journal Article

Communication costs in a geometric communication network

  • Sima Hajiaghaei Shanjani
  • Valerie King

We represent a communication network as a graph in which each node has only local information about the graph, except for an upper bound on the number of nodes, and nodes communicate by passing messages along its edges. Here, we consider a geometric communication network where the nodes also occupy points in space and the distance between points is the Euclidean distance. Our goal is to understand the communication cost needed to solve several fundamental geometry problems, including Farthest Pair, Convex Hull, Closest Pair, and approximations of these problems, in the asynchronous CONGEST KT1 model, where each node knows its ID and those of its neighbors. This extends the 2011 result of Rajsbaum and Urrutia for finding a convex hull of a planar geometric communication network to networks of arbitrary topology. We define a new model where each node has a position on the plane and nodes can communicate to each other if and only if there is an edge between them. We motivate the model and study a number of geometric problems in this model. We prove lower bounds on the communication complexity of the problems in this new model and present approximation algorithms for them. We prove lower bounds on the number of expected bits required for any randomized algorithm to solve the problems.

Details DOI

IJCAI Conference 2023 Conference Paper

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 degeneracy problem which runs in O(n log n) time, sublinear in the input size for dense graphs, by sampling a small number of neighbors adjacent to high degree nodes. This improves upon the previous work on sublinear approximate degeneracy, which implies a (4 + epsilon)-approximate ~O(n) solution. Our algorithm can be extended to an approximate O(n log n) time solution to the k-core decomposition problem. We also explore the use of our approximate algorithm as a technique for speeding up exact degeneracy computation. We prove theoretical guarantees of our algorithm and provide optimizations, which improve the running time of our algorithm in practice. Experiments on massive real-world web graphs show that our algorithm performs significantly faster than previous methods for computing degeneracy.

PDF Details DOI

FOCS Conference 2019 Conference Paper

Random k-out Subgraph Leaves only O(n/k) Inter-Component Edges

  • Jacob Holm
  • Valerie King
  • Mikkel Thorup
  • Or Zamir
  • Uri Zwick

Each vertex of an arbitrary simple graph on n vertices chooses k random incident edges. What is the expected number of edges in the original graph that connect different connected components of the sampled subgraph? We prove that the answer is O(n/k), when k ≥ c log n, for some large enough c. We conjecture that the same holds for smaller values of k, possibly for any k ≥ 2. Such a result is best possible for any k ≥ 2. As an application, we use this sampling result to obtain a one-way communication protocol with private randomness for finding a spanning forest of a graph in which each vertex sends only O (√n log n) bits to a referee.

Details

STOC Conference 2013 Conference Paper

Byzantine agreement in polynomial expected time: [extended abstract]

  • Valerie King
  • Jared Saia

In the classic asynchronous Byzantine agreement problem, communication is via asynchronous message-passing and the adversary is adaptive with full information. In particular, the adversary can adaptively determine which processors to corrupt and what strategy these processors should use as the algorithm proceeds; the scheduling of the delivery of messages is set by the adversary, so that the delays are unpredictable to the algorithm; and the adversary knows the states of all processors at any time, and is assumed to be computationally unbounded. Such an adversary is also known as "strong". We present a polynomial expected time algorithm to solve asynchronous Byzantine Agreement with a strong adversary that controls up to a constant fraction of the processors. This is the first improvement in running time for this problem since Ben-Or's exponential expected time solution in 1983. Our algorithm tolerates an adversary that controls up to a $1/500$ fraction of the processors.

Details

SODA Conference 2013 Conference Paper

Dynamic graph connectivity in polylogarithmic worst case time

  • Bruce M. Kapron
  • Valerie King
  • Ben Mountjoy

The dynamic graph connectivity problem is the following: given a graph on a fixed set of n nodes which is undergoing a sequence of edge insertions and deletions, answer queries of the form q ( a, b ): “Is there a path between nodes a and b? ” While data structures for this problem with polylogarithmic amortized time per operation have been known since the mid-1990's, these data structures have Θ( n ) worst case time. In fact, no previously known solution has worst case time per operation which is. We present a solution with worst case times O (log 4 n ) per edge insertion, O (log 5 n ) per edge deletion, and O (log n /log log n ) per query. The answer to each query is correct if the answer is “yes” and is correct with high probability if the answer is “no”. The data structure is based on a simple novel idea which can be used to quickly identify an edge in a cutset. Our technique can be used to simplify and significantly speed up the preprocessing time for the emergency planning problem while matching previous bounds for an update, and to approximate the sizes of cutsets of dynamic graphs in time Õ (min{| S |, |V \ S |}) for an oblivious adversary.

Details

FOCS Conference 2006 Conference Paper

Towards Secure and Scalable Computation in Peer-to-Peer Networks

  • Valerie King
  • Jared Saia
  • Vishal Sanwalani
  • Erik Vee

We consider the problems of Byzantine agreement and leader election, where a constant fraction b < 1/3 of processors are controlled by a malicious adversary. The first problem requires that all uncorrupted processors come to an agreement on a bit initially held by one of the uncorrupted processors; the second requires that the uncorrupted processors choose a leader who is uncorrupted. Motivated by the need for robust and scalable computation in peer-to-peer networks, we design the first scalable protocols for these problems for a network whose degree is polylogarithmic in its size. By scalable, we mean that each uncorrupted processor sends and processes a number of bits that is only polylogarithmic in n. (We assume no limit on the number of messages sent by corrupted processors.) With high probability, our Byzantine agreement protocol results in agreement among a 1 - O(1/ln n) fraction of the uncorrupted processors. With constant probability, our leader election protocol elects an uncorrupted leader and ensures that a 1 - O(1/ln n) fraction of the uncorrupt processors know this leader. We assume a full information model. Thus, the adversary is assumed to have unlimited computational power and has access to all communications, but does not have access to processors' private random bits

Details

FOCS Conference 1999 Conference Paper

Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs

  • Valerie King

This paper presents the first fully dynamic algorithms for maintaining all-pairs shortest paths in digraphs with positive integer weights less than b. For approximate shortest paths with an error factor of (2+/spl epsiv/), for any positive constant /spl epsiv/, the amortized update time is O(n/sup 2/ log/sup 2/ n/log log n); for an error factor of (1+/spl epsiv/) the amortized update time is O(n/sup 2/ log/sup 3/ (bn)//spl epsiv//sup 2/). For exact shortest paths the amortized update time is O(n/sup 2. 5/ /spl radic/(b log n)). Query time for exact and approximate shortest distances is O(1); exact time and approximate paths can be generated in time proportional to their lengths. Also presented is a fully dynamic transitive closure algorithm with update time O(n/sup 2/ log n) and query time O(1). The previously known fully dynamic transitive closure algorithm with fast query time has one-sided error and update time O(n/sup 2. 28/). The algorithms use simple data structures, and are deterministic.

Details

FOCS Conference 1995 Conference Paper

Fully Dynamic Biconnectivity and Transitive Closure

  • Monika Henzinger
  • Valerie King

This paper presents an algorithm for the fully dynamic biconnectivity problem whose running time is exponentially faster than all previously known solutions. It is the first dynamic algorithm that answers biconnectivity queries in time O(log/sup 2/n) in a n-node graph and can be updated after an edge insertion or deletion in polylogarithmic time. Our algorithm is a Las-Vegas style randomized algorithm with the update time amortized update time O(log/sup 4/n). Only recently the best deterministic result for this problem was improved to O(/spl radic/nlog/sup 2/n). We also give the first fully dynamic and a novel deletions-only transitive closure (i. e. directed connectivity) algorithms. These are randomized Monte Carlo algorithms. Let n be the number of nodes in the graph and let m/spl circ/ be the average number of edges in the graph during the whole update sequence: The fully dynamic algorithms achieve (1) query time O(n/logn) and update time O(m/spl circ//spl radic/nlog/sup 2/n+n); or (2) query time O(n/logn) and update time O(nm/spl circ//sup /spl mu/-1/)log/sup 2/n=O(nm/spl circ//sup 0. 58/log/sup 2/n), where /spl mu/ is the exponent for boolean matrix multiplication (currently /spl mu/=2. 38). The deletions-only algorithm answers queries in time O(n/logn). Its amortized update time is O(nlog/sup 2/n).

Details

STOC Conference 1989 Conference Paper

Verifying Partial Orders

  • Claire Mathieu
  • Valerie King

We present a randomized algorithm which uses O ( n (log n ) 1/3 ) expected comparisons to verify that a given partial order holds on n elements from an unknown total order.

Details
v2026.09.13