User satisfaction metrics are an integral part of search engine development as they help system developers to understand and evaluate the quality of the user experience. Research to date has mostly focused on predicting success or frustration as a proxy for satisfaction. However, users' search experience is more complex than merely being either successful or not. As such, using success rate as a measure of satisfaction can be limiting. In this work, we propose the use of utility as a measure of searcher satisfaction. This concept represents the fulfillment a user receives from con-suming a service and explains how users aim to gain optimal overall satisfaction. Our utility metrics measure the user satisfac-tion by aggregating all their interaction with the search engine. These interactions are represented as a timeline of actions and their dwelltimes, where each action is classified as having a posi-tive or negative effect on the user. We examine sessions mined from Bing logs, with multi-point scale assessment of searcher satisfaction and show that utility is a better proxy for satisfaction compared to success. Leveraging that data, we design metrics of searcher satisfaction that assess the overall utility accumulated by a user during her search session. We use real user traffic from millions of users in an A/B setting to compare utility metrics to success rate metrics. We show that utility is a better metric for evaluating searcher satisfaction with the search engine, and a more sensitive and accurate metric when compared to predicting success. These metrics are currently adopted as the top-level met-ric for evaluating the thousands of A/B experiments that are run on Bing each year.

In this paper, we describe principles for designing metrics in the context of A/B experiments. We share some issues that comes up in designing such experiments and provide solutions to avoid such pitfalls.

We derive new time-space tradeoff lower bounds and algorithms for exactly computing statistics of input data, including frequency moments, element distinctness, and order statistics, that are simple to calculate for sorted data. We develop a randomized algorithm for the element distinctness problem whose time T and space S satisfy T ∈ Õ (n3/2/S1/2), smaller than previous lower bounds for comparison-based algorithms, showing that element distinctness is strictly easier than sorting for randomized branching programs. This algorithm is based on a new time and space efficient algorithm for finding all collisions of a function f from a finite set to itself that are reachable by iterating f from a given set of starting points. We further show that our element distinctness algorithm can be extended at only a polylogarithmic factor cost to solve the element distinctness problem over sliding windows, where the task is to take an input of length 2n-1 and produce an output for each window of length n, giving n outputs in total. In contrast, we show a time-space tradeoff lower bound of T ∈ Ω(n2/S) for randomized branching programs to compute the number of distinct elements over sliding windows. The same lower bound holds for computing the low-order bit of F0and computing any frequency moment Fk,≠1. This shows that those frequency moments and the decision problem F0mod 2 are strictly harder than element distinctness. We complement this lower bound with a T ∈ Õ(n2/S) comparison-based deterministic RAM algorithm for exactly computing Fkover sliding windows, nearly matching both our lower bound for the sliding-window version and the comparison-based lower bounds for the single-window version. We further exhibit a quantum algorithm for F0over sliding windows with T ∈ O(n3/2/S1/2). Finally, we consider the computations of order statistics over sliding windows.

We prove a time-space tradeoff lower bound of T = Ω (n log(n/s) log log(n/s)) for randomized oblivious branching programs to compute 1GAP, also known as the pointer jumping problem, a problem for which there is a simple deterministic time n and space O(log n) RAM (random access machine) algorithm. We give a similar time-space tradeoff of T = Ω (n log(n/s) log log(n/s)) for Boolean randomized oblivious branching programs computing GIP-MAP, a variation of the generalized inner product problem that can be computed in time n and space O(log2n) by a deterministic Boolean branching program. These are also the first lower bounds for randomized oblivious branching programs computing explicit functions that apply for T = ω(n log n). They also show that any simulation of general branching programs by randomized oblivious ones requires either a superlogarithmic increase in time or an exponential increase in space.

We prove that q-ary sparse codes with small bias are self-correctable and locally testable. We generalize a result of Kaufman and Sudan that proves the local testability and correctability of binary sparse codes with small bias. We use properties of q-ary Krawtchouk polynomials and the McWilliams identity -that relates the weight distribution of a code to the weight distribution of its dual- to derive bounds on the error probability of the randomized tester and self-corrector we are analyzing.

Repeat accumulate accumulate (RAA) codes are turbo-like codes where the message is first repeated k ges 2 times, passed through a first permutation (called interleaver), then an accumulator, then a second permutation, and finally a second accumulator. Bazzi, Mahdian, and Spielman (2003) prove that RAA codes are asymptotically good with high probability when the two permutations are chosen at random. RAA codes admit linear-time encoding algorithms, and are perhaps the simplest known family of linear-time encodable asymptotically good codes. An explicit construction of an asymptotically good RAA code is thus a very interesting goal. We focus on the case when k = 2 and we consider a variation of RAA codes where the inner repeat accumulate code is systematic. We give an explicit construction of the first permutation for which we show that the resulting code is asymptotically good with high probability when the second permutation is chosen at random. The explicit construction uses a cubic Hamiltonian graph with logarithmic girth.