We provide and study several algorithms for sorting an array of n comparable distinct elements subject to probabilistic comparison errors. In this model, the comparison of two elements returns the wrong answer according to a fixed probability, p_e < 1/2, and otherwise returns the correct answer. The dislocation of an element is the distance between its position in a given (current or output) array and its position in a sorted array. There are various algorithms that can be utilized for sorting or near-sorting elements subject to probabilistic comparison errors, but these algorithms are not data oblivious because they all make heavy use of noisy binary searching. In this paper, we provide new methods for sorting with comparison errors that are data oblivious while avoiding the use of noisy binary search methods. In addition, we experimentally compare our algorithms and other sorting algorithms.

Dating back to two famous experiments by the social-psychologist, Stanley Milgram, in the 1960s, the small-world phenomenon is the idea that all people are connected through a short chain of acquaintances that can be used to route messages. Many subsequent papers have attempted to model this phenomenon, with most concentrating on the "short chain" of acquantances rather than their ability to efficiently route messages. For example, a well-known preferential attachment model by Barabási and Albert provides a mathematical explanation of how a social network can have small diameter---hence, short chains between participants--- but this model doesn't explain how they can route messages. A notable exception is a well-known model by Jon Kleinberg, which shows that it is possible for participants in a n × n grid to route a message in O(log2 n) hops by augmenting the grid with a small number of long-range random links and using a simple greedy routing strategy. Although Kleinberg's model is intriguing, it does not take into account the road network of the United States used in the original Milgram experiments and its O(log2 n) number of hops for messages is actually quite far from the average of six hops for successful messages observed by Milgram in his experiments, which gave rise to the "six-degrees-of-separation" expression. In this paper, we study the small-world navigability of the U.S. road network, with the goal of providing a model that explains how messages in the original small-world experiments could be routed along short paths using U.S. roads. To this end, we introduce the Neighborhood Preferential Attachment model, which combines elements from Kleinberg's model and the Barabási-Albert model, such that long-range links are chosen according to both the degrees and (road-network) distances of vertices in the network. We empirically evaluate all three models by running a decentralized routing algorithm, where each vertex only has knowledge of its own neighbors, and find that our model outperforms both of these models in terms of the average hop length. Moreover, our experiments indicate that similar to the Barabási-Albert model, networks generated by our model are scale-free, which could be a more realistic representation of acquaintanceship links in the original small-world experiment.

The completeness of road network data is significant in the quality of various routing services and applications. We introduce an efficient randomized algorithm for exact learning of road networks using simple distance queries, which can find missing roads and improve the quality of routing services. The efficiency of our algorithm depends on a cluster degree parameter, d_max, which is an upper bound on the degrees of vertex clusters defined during our algorithm. Unfortunately, we leave open the problem of theoretically bounding d_max, although we conjecture that d_max is small for road networks and other similar types of graphs. We support this conjecture by experimentally evaluating our algorithm on road network data for the U.S. and 5 European countries of various sizes. This analysis provides experimental evidence that our algorithm issues a quasilinear number of queries in expectation for road networks and similar graphs.