Being able to measure the success of online shopping interactions is crucial in order to evaluate and optimize the performance of e-commerce systems. It is especially challenging in the domain of voice shopping, typically supported by voice-based AI assistants. Unlike Web shopping, which offers a rich amount of behavioral signals such as clicks, in voice shopping a non-negligible amount of shopping interactions frequently ends without any immediate explicit or implicit user behavioral signal. Moreover, users may start their journey using a voice-enabled device, but complete it elsewhere, for example on their smartphone mobile app or a Web browser. We explore the challenge of measuring successful interactions in voice product search based on users’ behavior, and propose a medium-term reward metric named Extended ConVersion (ECVR). ECVR extends the notion of conversion beyond the usual purchase action, which serves as an undisputed measure of success in e-commerce. More specifically, it also captures purchase actions that occur at a later stage during a same shopping journey, and possibly on different channel than the one on which the interaction started. In this paper, we formally define the ECVR metric, describe multiple ways of evaluating the quality of a metric, and use these to explore different parameters for ECVR. After selecting the most appropriate parameters, we show that a ranking system optimized for ECVR, set up with these parameters, leads to improvements in long-term engagement and revenue, without compromising immediate conversion gains.

Implicit feedback from users behavior is a natural and scalable source for training and evaluating ranking models in human-interactive systems. However, inherent biases such as the position bias are key obstacles to its effective usage. This is further accentuated in cases of extreme bias, where behavioral feedback can be collected exclusively on the top ranked result. In fact, in such cases, state-of-art debiasing methods cannot be applied. A prominent use case of extreme position bias is the voice shopping medium, where only a small amount of information can be presented to the user during a single interaction, resulting in user behavioral signals that are almost exclusively limited to the top offer. There is no way to know how the user would have reacted to a different offer than the top one he was actually exposed to. Thus, any new ranker we wish to evaluate with respect to a behavioral metric, requires online experimentation. We propose a novel approach, based on anexternal estimator model, for accurately predicting offline the performance of a new ranker. The accuracy of our solution is proven theoretically, as well as demonstrated by a line of experiments. In these experiments, we focus on the use case of purchase prediction, and show that our estimator can accurately predict offline the purchase rate of different rankers over a segment of voice shopping traffic. Our prediction is validated online, as being compared to the actual performance obtained by each ranker when being exposed to users.

The problem of constructing error-resilient interactive protocols was introduced in the seminal works of Schulman (FOCS 1992, STOC 1993). These works show how to convert any two-party interactive protocol into one that is resilient to constant-fraction of error, while blowing up the communication by only a constant factor. Since these seminal works, there have been many followup works which improve the error rate, the communication rate, and the computational efficiency. All these works only consider only an increase in communication complexity and did not consider an increase in round complexity. This work is the first one that considers the blowup of round complexity in noisy setting. While techniques from other papers can be easily adapted encode protocols with arbitrarily round complexity this coding schemes will lead to large(and usually unbounded) increase in round complexity of the protocol. In this work, we show how to convert any protocol Π, with no a priori known communication bound, into an error-resilient protocol Π', with comparable computational efficiency, that is resilient to constant fraction of adversarial error, while blowing up both the communication complexity and the round complexity by at most a constant factor. We consider the model where in each round each party may send a message of arbitrary length, where the length of the messages and the length of the protocol may be adaptive, and may depend on the private inputs of the parties and on previous communication. We consider the adversarial error model, where ε-fraction of the communication may be corrupted, where we allow each corruption to be an insertion or deletion (in addition to toggle). In addition, we try to minimize the blowup parameters: In particular, we construct such Π' with (1+Õ(ε^(1/4))) blowup in communication and O(1) blowup in rounds. We also show how to reduce the blowup in rounds at the expense of increasing the blowup in communication, and construct Π' where both the blowup in rounds and communication, approaches one (i.e., no blowup) as ε approaches zero. We give "evidence" that our parameters are "close to" optimal.

One emerging benefit of voice assistants is to facilitate product search experience, allowing users to express orally which products they seek, and taking actions on retrieved results such as adding them to their cart or sending the product details to their mobile phone for further examination. Looking at users' behavior in product search, supported by a digital voice assistant, we have observed an interesting phenomenon where users purchase or engage with search results that are objectively judged irrelevant to their queries.

Learning a ranking model in product search involves satisfying many requirements such as maximizing the relevance of retrieved products with respect to the user query, as well as maximizing the purchase likelihood of these products. Multi-Objective Ranking Optimization (MORO) is the task of learning a ranking model from training examples while optimizing multiple objectives simultaneously. Label aggregation is a popular solution approach for multi-objective optimization, which reduces the problem into a single objective optimization problem, by aggregating the multiple labels of the training examples, related to the different objectives, to a single label. In this work we explore several label aggregation methods for MORO in product search. We propose a novel stochastic label aggregation method which randomly selects a label per training example according to a given distribution over the labels. We provide a theoretical proof showing that stochastic label aggregation is superior to alternative aggregation approaches, in the sense that any optimal solution of the MORO problem can be generated by a proper parameter setting of the stochastic aggregation process. We experiment on three different datasets: two from the voice product search domain, and one publicly available dataset from the Web product search domain. We demonstrate empirically over these three datasets that MORO with stochastic label aggregation provides a family of ranking models that fully dominates the set of MORO models built using deterministic label aggregation.

Let $D$ be a $b$-wise independent distribution over $\{0,1\}^m$. Let $E$ be the “noise” distribution over $\{0,1\}^m$ where the bits are independent and each bit is 1 with probability $\eta/2$. We study which tests $f \colon \{0,1\}^m \to [-1,1]$ are $\varepsilon$-fooled by $D+E$, i.e., $|{\rm E}[f(D+E)] - {\rm E}[f(U)]| \le \varepsilon$, where $U$ is the uniform distribution. We show that $D+E$ $\varepsilon$-fools product tests $f : (\{0,1\}^n)^k \to [-1,1]$ given by the product of $k$ bounded functions on disjoint $n$-bit inputs with error $\varepsilon = k(1-\eta)^{\Omega(b^2/m)}$, where $m = nk$ and $b \ge n$. This bound is tight when $b = \Omega(m)$ and $\eta \ge (\log k)/m$. For $b \ge m^{2/3} \log m$ and any constant $\eta$ the distribution $D+E$ also $0.1$-fools log-space algorithms. We develop two applications of this type of results. First, we prove communication lower bounds for decoding noisy codewords of length $m$ split among $k$ parties. For Reed--Solomon codes of dimension $m/k$ where $k = O(1)$, communication $\Omega(\eta m) - O(\log m)$ is required to decode one message symbol from a codeword with $\eta m$ errors, and communication $O(\eta m \log m)$ suffices. Second, we obtain pseudorandom generators. We can $\varepsilon$-fool product tests $f\colon (\{0,1\}^n)^k \to [-1,1]$ under any permutation of the bits with seed lengths $2n + \tilde O(k^2 \log (1/\varepsilon))$ and $O(n) + \tilde O(\sqrt{nk \log 1/\varepsilon})$. Previous generators have seed lengths $\ge nk/2$ or $\ge n \sqrt{n k}$. For the special case where the $k$ bounded functions have range $\{0,1\}$ the previous generators have seed length $\ge (n+\log k)\log (1/\varepsilon)$.

Motivated by an attempt to understand the formation and development of (human) language, we introduce a "distributed compression" problem. In our problem a sequence of pairs of players from a set of K players are chosen and tasked to communicate messages drawn from an unknown distribution Q. Arguably languages are created and evolve to compress frequently occurring messages, and we focus on this aspect. The only knowledge that players have about the distribution Q is from previously drawn samples, but these samples differ from player to player. The only common knowledge between the players is restricted to a common prior distribution P and some constant number of bits of information (such as a learning algorithm). Letting T_epsilon denote the number of iterations it would take for a typical player to obtain an epsilon-approximation to Q in total variation distance, we ask whether T_epsilon iterations suffice to compress the messages down roughly to their entropy and give a partial positive answer. We show that a natural uniform algorithm can compress the communication down to an average cost per message of O(H(Q) + log (D(P || Q)) in tilde{O}(T_epsilon) iterations while allowing for O(epsilon)-error, where D(. || .) denotes the KL-divergence between distributions. For large divergences this compares favorably with the static algorithm that ignores all samples and compresses down to H(Q) + D(P || Q) bits, while not requiring T_epsilon * K iterations that it would take players to develop optimal but separate compressions for each pair of players. Along the way we introduce a "data-structural" view of the task of communicating with a natural language and show that our natural algorithm can also be implemented by an efficient data structure, whose storage is comparable to the storage requirements of Q and whose query complexity is comparable to the lengths of the message to be compressed. Our results give a plausible mathematical analogy to the mechanisms by which human languages get created and evolve, and in particular highlights the possibility of coordination towards a joint task (agreeing on a language) while engaging in distributed learning.

Finding a maximal independent set (MIS) in a graph is a cornerstone task in distributed computing. The local nature of an MIS allows for fast solutions in a static distributed setting, which are logarithmic in the number of nodes or in their degrees. The result trivially applies for the dynamic distributed model, in which edges or nodes may be inserted or deleted. In this paper, we take a different approach which exploits locality to the extreme, and show how to update an MIS in a dynamic distributed setting, either synchronous or asynchronous, with only a single adjustment and in a single round, in expectation. These strong guarantees hold for the complete fully dynamic setting: Insertions and deletions, of edges as well as nodes, gracefully and abruptly. This strongly separates the static and dynamic distributed models, as super-constant lower bounds exist for computing an MIS in the former.

We study a variant of the generalized assignment problem ( gap ), which we label all-or-nothing gap ( agap ). We are given a set of items, partitioned into n groups, and a set of m bins. Each item ℓ has size s ℓ > 0, and utility a ℓ j ⩾ 0 if packed in bin j . Each bin can accommodate at most one item from each group; the total size of the items in a bin cannot exceed its capacity. A group of items is satisfied if all of its items are packed. The goal is to find a feasible packing of a subset of the items in the bins such that the total utility from satisfied groups is maximized. We motivate the study of agap by pointing out a central application in scheduling advertising campaigns. Our main result is an O (1)-approximation algorithm for agap instances arising in practice, in which each group consists of at most m /2 items. Our algorithm uses a novel reduction of agap to maximizing submodular function subject to a matroid constraint. For agap instances with a fixed number of bins, we develop a randomized polynomial time approximation scheme (PTAS) , relying on a nontrivial LP relaxation of the problem. We present a (3 + ε)-approximation as well as PTASs for other special cases of agap , where the utility of any item does not depend on the bin in which it is packed. Finally, we derive hardness results for the different variants of agap studied in this paper.

A local tester for a code probabilistically views a small set of coordinates of a given word and based on this local view accepts code words with probability one while rejecting words far from the code with constant probability. A local tester for a code is said to be "robust" if the local views of the tester are far from acceptable views when the word being tested is far from the code. Robust testability of codes play a fundamental role in constructions of probabilistically checkable proofs where robustness is a critical element in composition. In this work we consider a broad class of codes, called lifted codes, that include codes formed by low-degree polynomials, and show that an almost natural test, extending a low-degree test proposed by Raz and Safra (STOC 1997), is robust. Our result is clean and general -- the robustness of the test depends only on the distance of the code being lifted, and is positive whenever the distance is positive. We use our result to get the first robust low-degree test that works when the degree of the polynomial being tested is more than half the field size. Our results also show that the high-rate codes of Guo et al. (ITCS 2013) are robustly locally testable with sub linear query complexity. Guo et al. Also show several other interesting classes of locally testable codes that can be derived from lifting and our result shows all such codes have robust testers, at the cost of a quadratic blow up in the query complexity of the tester. Of technical interest is an intriguing relationship between tensor product codes and lifted codes that we explore and exploit.

Communication in "natural" settings, e.g., between humans, is distinctly different than that in classical designed settings, in that the former is characterized by the sender and receiver not being in perfect agreement with each other. Solutions to classical communication problems thus have to overcome an extra layer of uncertainty introduced by this lack of prior agreement. One of the classical goals of communication is compression of information, and in this context lack of agreement implies that sender and receiver may not agree on the "prior" from which information is being generated. Most classical mechanisms for compressing turn out to be non-robust when sender and receiver do not agree on the prior. Juba et al. (Proc. ITCS 2011) showed that there do exists compression schemes with shared randomness between sender and reciever that can compress information down roughly to its entropy.

We consider the problem of testing if a given function f : Fqn→Fqis close to a n-variate degree d polynomial over the finite field Fqof q elements. The natural, low-query, test for this property would be to pick the smallest dimension t = tq,d≈ d/q such that every function of degree greater than d reveals this aspect on some i-dimensional affine subspace of Fqnand to test that f when restricted to a random i-dimensional affine subspace is a polynomial of degree at most d on this subspace. Such a test makes only qtqueries, independent of n. Previous works, by Alon et al. [1], and Kaufman and Ron [7] and Jutla et al. [6], showed that this natural test rejected functions that were Ω(1)-far from degree d-polynomials with probability at least Ω,(q-t). (The initial work [1] considered only the case of q = 2, while the work [6] only considered the case of prime q. The results in [7] hold for all fields.) Thus to get a constant probability of detecting functions that are at constant distance from the space of degree d polynomials, the tests made q2tqueries. Kaufman and Ron also noted that when q is prime, then qtqueries are necessary. Thus these tests were off by at least a quadratic factor from known lower bounds. Bhattacharyya et al. [2] gave an optimal analysis of this test for the case of the binary field and showed that the natural test actually rejects functions that were Ω(1)-far from degree d- polynomials with probability Ω(1). In this work we extend this result for all fields showing that the natural test does indeed reject functions that are Ω(1)-far from degree d polynomials with Ω(1)-probability, where the constants depend only on q the field size. Thus our analysis thus shows that this test is optimal (matches known lower bounds) when q is prime. The main technical ingredient in our work is a tight analysis of the number of "hyperplanes" (affine subspaces of co-dimension 1) on which the restriction of a degree d polynomial has degree less than d. We show that the number of such hyperplanes is at most O(qtq-d) - which is tight to within constant factors.

In this paper we study the structure of polynomials of degree three and four that have high bias or high Gowers norm, over arbitrary prime fields. In particular we obtain the following results. 1. We give a canonical representation for degree three or four polynomials that have a significant bias (i.e. they are not equidistributed). This result generalizes the corresponding results from the theory of quadratic forms. This significantly improves previous results for such polynomials. 2. For the case of degree four polynomials with high Gowers norm we show that (a subspace of constant co-dimension of) Fn can be partitioned to subspaces of dimension Omega(n) such that on each of the subspaces the polynomial is equal to some degree three polynomial. It was previously shown that a quartic polynomial with a high Gowers norm is not necessarily correlated with any cubic polynomial. Our result shows that a slightly weaker statement does hold. The proof is based on finding a structure in the space of partial derivatives of the underlying polynomial.