skip to main content


Search for: All records

Creators/Authors contains: "Robinson, P."

Note: When clicking on a Digital Object Identifier (DOI) number, you will be taken to an external site maintained by the publisher. Some full text articles may not yet be available without a charge during the embargo (administrative interval).
What is a DOI Number?

Some links on this page may take you to non-federal websites. Their policies may differ from this site.

  1. We study local symmetry breaking problems in the Congest model, focusing on ruling set problems, which generalize the fundamental Maximal Independent Set (MIS) problem. The time (round) complexity of MIS (and ruling sets) have attracted much attention in the Local model. Indeed, recent results (Barenboim et al., FOCS 2012, Ghaffari SODA 2016) for the MIS problem have tried to break the long-standing O(log n)-round “barrier” achieved by Luby’s algorithm, but these yield o(log n)-round complexity only when the maximum degree  is somewhat small relative to n. More importantly, these results apply only in the Local model. In fact, the best known time bound in the Congest model is still O(log n) (via Luby’s algorithm) even for moderately small  (i.e., for  = (log n) and  = o(n)). Furthermore, message complexity has been largely ignored in the context of local symmetry breaking. Luby’s algorithm takes O(m) messages on m-edge graphs and this is the best known bound with respect to messages. Our work is motivated by the following central question: can we break the (log n) time complexity barrier and the (m) message complexity barrier in the Congest model for MIS or closelyrelated symmetry breaking problems? This paper presents progress towards this question for the distributed ruling set problem in the Congest model. A -ruling set is an independent set such that every node in the graph is at most hops from a node in the independent set. We present the following results: Time Complexity: We show that we can break the O(log n) “barrier” for 2- and 3-ruling sets. We compute 3-ruling sets in O  log n log log n  rounds with high probability (whp). More generally we show that 2-ruling sets can be computed in O  log · (log n)1/2+" + log n log log n  rounds for any " > 0, which is o(log n) for a wide range of  values (e.g.,  = 2(log n)1/2−" ). These are the first 2- and 3-ruling set algorithms to improve over the O(log n)-round complexity of Luby’s algorithm in the Congest model. Message Complexity: We show an (n2) lower bound on the message complexity of computing an MIS (i.e., 1-ruling set) which holds also for randomized algorithms and present a contrast to this by showing a randomized algorithm for 2-ruling sets that, whp, uses only O(n log2 n) messages and runs in O( log n) rounds. This is the first message-efficient algorithm known for ruling sets, which has message complexity nearly linear in n (which is optimal up to a polylogarithmic factor). 
    more » « less
  2. The extent of increasing anthropogenic impacts on large marine vertebrates partly depends on the animals’ movement patterns. Effective conservation requires identification of the key drivers of movement including intrinsic properties and extrinsic constraints associated with the dynamic nature of the environments the animals inhabit. However, the relative importance of intrinsic versus extrinsic factors remains elusive. We analyze a global dataset of ∼2.8 million locations from >2,600 tracked individuals across 50 marine vertebrates evolutionarily separated by millions of years and using different locomotion modes (fly, swim, walk/paddle). Strikingly, movement patterns show a remarkable convergence, being strongly conserved across species and independent of body length and mass, despite these traits ranging over 10 orders of magnitude among the species studied. This represents a fundamental difference between marine and terrestrial vertebrates not previously identified, likely linked to the reduced costs of locomotion in water. Movement patterns were primarily explained by the interaction between species-specific traits and the habitat(s) they move through, resulting in complex movement patterns when moving close to coasts compared with more predictable patterns when moving in open oceans. This distinct difference may be associated with greater complexity within coastal microhabitats, highlighting a critical role of preferred habitat in shaping marine vertebrate global movements. Efforts to develop understanding of the characteristics of vertebrate movement should consider the habitat(s) through which they move to identify how movement patterns will alter with forecasted severe ocean changes, such as reduced Arctic sea ice cover, sea level rise, and declining oxygen content. 
    more » « less