The joint replenishment problem (JRP) is a classical inventory management problem. We consider a natural generalization with outliers, where we are allowed to reject (that is, not service) a subset of demand points. In this paper, we are motivated by issues of fairness - if we do not serve all of the demands, we wish to “spread out the pain” in a balanced way among customers, communities, or any specified market segmentation. One approach is to constrain the rejections allowed, and to have separate bounds for each given customer. In our most general setting, we consider a set of C features, where each demand point has an associated rejection cost for each feature, and we have a given bound on the allowed rejection cost incurred in total for each feature. This generalizes an extensively studied model of fairness introduced in earlier work on the Colorful k—Center problem in which (analogously) each demand point has a given color, and we bound the number of rejections of each color class. In the JRP, we seek to balance the cost incurred by a fixed ordering overhead with the cost of maintaining on-hand inventory over a longer period in advance of when it is needed. More precisely, there is a given set of item types, for which there is specified demand over a finite, discrete-time horizon, and placing any order at a given time incurs a general ordering cost and item-specific ordering costs (independent of the total demand serviced); in addition, for each unit of demand held in inventory for an interval of time, there is a corresponding item-specific holding cost incurred; the aim is to minimize the total cost.

Abstract We investigate algebraic attacks on the Learning Parity with Noise ($\mathsf{LPN}$) problem over large fields in parameter settings relevant to building indistinguishability obfuscation in which the proportion of corrupted equations is inverse-polynomially sparse. Our aim was to obtain a subexponential algorithm using the Macaulay expansion and relinearization. Alas, we did not. Nevertheless, our findings suggest an interesting relation between runtime and the rank of the Macaulay expansion. The runtime of this attack is $O\big(2^{d \log m}\big)$, where $m$ is the number of initial equations and $d$ is the degree of the Macaulay expansion. If the resulting system of equations has sufficiently large rank, we show that solving the $\mathsf{LPN}$ polynomial system requires an $O(\sqrt{m})$ degree expansion, which would imply a subexponential attack. Under the (more widely believed) assumption that the expanded system is semi-regular, however, we show that an $O(m)$ degree expansion is required to recover the secret vector. Since $O(\sqrt{m})$-degree expansions may not have sufficient rank, we propose a randomized algorithm which introduces carefully chosen equations that hold with high probability to increase the rank and improve the likelihood of a successful attack. We highlight the empirical and theoretical challenges in analyzing this approach. Our code is available at www.tinyurl.com/attacklpn.

Given a set of $n$ vectors in $\mathbb{R}^d$, the goal of the \emph{determinant maximization} problem is to pick $k$ vectors with the maximum volume. Determinant maximization is the MAP-inference task for determinantal point processes (DPP) and has recently received considerable attention for modeling diversity. As most applications for the problem use large amounts of data, this problem has been studied in the relevant \textit{composable coreset} setting. In particular, [Indyk-Mahabadi-OveisGharan-Rezaei--SODA'20, ICML'19] showed that one can get composable coresets with optimal approximation factor of $\tilde O(k)^k$ for the problem, and that a local search algorithm achieves an almost optimal approximation guarantee of $O(k)^{2k}$. In this work, we show that the widely-used Greedy algorithm also provides composable coresets with an almost optimal approximation factor of $O(k)^{3k}$, which improves over the previously known guarantee of $C^{k^2}$, and supports the prior experimental results showing the practicality of the greedy algorithm as a coreset. Our main result follows by showing a local optimality property for Greedy: swapping a single point from the greedy solution with a vector that was not picked by the greedy algorithm can increase the volume by a factor of at most $(1+\sqrt{k})$. This is tight up to the additive constant $1$. Finally, our experiments show that the local optimality of the greedy algorithm is even lower than the theoretical bound on real data sets.

As Approximate Nearest Neighbor Search (ANNS)-based dense retrieval becomes ubiquitous for search and recommendation scenarios, efficiently answering filtered ANNS queries has become a critical requirement. Filtered ANNS queries ask for the nearest neighbors of a query’s embedding from the points in the index that match the query’s labels such as date, price range, language. There has been little prior work on algorithms that use label metadata associated with vector data to build efficient indices for filtered ANNS queries. Consequently, current indices have high search latency or low recall which is not practical in interactive web-scenarios. We present two algorithms with native support for faster and more accurate filtered ANNS queries: one with streaming support, and another based on batch construction. Central to our algorithms is the construction of a graph-structured index which forms connections not only based on the geometry of the vector data, but also the associated label set. On real-world data with natural labels, both algorithms are an order of magnitude or more efficient for filtered queries than the current state of the art algorithms. The generated indices also be queried from an SSD and support thousands of queries per second at over recall@10.

Abstract. For positive integers [Formula: see text] and [Formula: see text], consider a multiset of nonempty subsets of [Formula: see text] such that there is a unique partition of these subsets into [Formula: see text] partitions of [Formula: see text]. We study the maximum possible size [Formula: see text] of such a multiset. We focus on the regime [Formula: see text] and show that [Formula: see text]. When [Formula: see text] for any [Formula: see text], this lower bound simplifies to [Formula: see text], and we show a matching upper bound [Formula: see text] that is optimal up to a factor of [Formula: see text]. We also compute [Formula: see text] exactly when [Formula: see text].