Sorting items by user rating is a fundamental interaction pattern of the modern Web, used to rank products (Amazon), posts (Reddit), businesses (Yelp), movies (YouTube), and more. To implement this pattern, designers must take in a distribution of ratings for each item and define a sensible total ordering over them. This is a challenging problem, since each distribution is drawn from a distinct sample population, rendering the most straightforward method of sorting --- comparing averages --- unreliable when the samples are small or of different sizes. Several statistical orderings for binary ratings have been proposed in the literature (e.g., based on the Wilson score, or Laplace smoothing), each attempting to account for the uncertainty introduced by sampling. In this paper, we study this uncertainty through the lens of human perception, and ask "How do people sort by ratings?" In an online study, we collected 48,000 item-ranking pairs from 4,000 crowd workers along with 4,800 rationales, and analyzed the results to understand how users make decisions when comparing rated items. Our results shed light on the cognitive models users employ to choose between rating distributions, which sorts of comparisons are most contentious, and how the presentation of rating information affects users' preferences.

Given a (multi) set S of n positive integers and a target integer u , the subset sum problem is to decide if there is a subset of S that sums up to u . We present a series of new algorithms that compute and return all the realizable subset sums up to the integer u in Õ(min { √ n u , u 5/4 ,σ }), where σ is the sum of all elements of S and Õ hides polylogarithmic factors. We also present a modified algorithm for integers modulo m , which computes all the realizable subset sums modulo m in Õ(min { √ n m , m 5/4 }) time. Our contributions improve upon the standard dynamic programming algorithm that runs in O ( nu ) time. To the best of our knowledge, the new algorithms are the fastest deterministic algorithms for this problem. The new results can be employed in various algorithmic problems, from graph bipartition to computational social choice. Finally, we also improve a result on covering Z m , which might be of independent interest.

Given a multiset S of n positive integers and a target integer t, the subset sum problem is to decide if there is a subset of S that sums up to t. We present a new divide-and-conquer algorithm that computes all the realizable subset sums up to an integer u in where σ is the sum of all elements in S and Õ hides polylogarithmic factors. This result improves upon the standard dynamic programming algorithm that runs in O(nu) time. To the best of our knowledge, the new algorithm is the fastest general deterministic algorithm for this problem. We also present a modified algorithm for finite cyclic groups, which computes all the realizable subset sums within the group in time, where m is the order of the group.