Search

Given n elements, an integer k ≤ n/2 and a parameter ε ≥ 1/n, we study the problem of selecting an element with rank in (k-nε, k+nε] using unreliable comparisons where the outcome of each comparison is incorrect independently with a constant error probability, and multiple comparisons between the same pair of elements are independent. In this fault model, the fundamental problems of finding the minimum, selecting the k-th smallest element and sorting have been shown to require Θ(n log 1/Q), Θ(n log k/Q) and Θ(n log n/Q) comparisons, respectively, to achieve success probability 1-Q [Uriel Feige et al., 1994]. Considering the increasing complexity of modern computing, it is of great interest to develop approximation algorithms that enable a trade-off between the solution quality and the number of comparisons. In particular, approximation algorithms would even be able to attain a sublinear number of comparisons. Very recently, Leucci and Liu [Stefano Leucci and Chih-Hung Liu, 2022] proved that the approximate minimum selection problem, which covers the case that k ≤ nε, requires expected Θ(ε^{-1} log 1/Q) comparisons, but the general case, i.e., for nε < k ≤ n/2, is still open. We develop a randomized algorithm that performs expected O(k/n ε^{-2} log 1/Q) comparisons to achieve success probability at least 1-Q. For k = n ε, the number of comparisons is O(ε^{-1} log 1/Q), matching Leucci and Liu’s result [Stefano Leucci and Chih-Hung Liu, 2022], whereas for k = n/2 (i.e., approximating the median), the number of comparisons is O(ε^{-2} log 1/Q). We also prove that even in the absence of comparison faults, any randomized algorithm with success probability at least 1-Q performs expected Ω(min{n, k/n ε^{-2} log 1/Q}) comparisons. As long as n is large enough, i.e., when n = Ω(k/n ε^{-2} log 1/Q), our lower bound demonstrates the optimality of our algorithm, which covers the possible range of attaining a sublinear number of comparisons. Surprisingly, for constant Q, our algorithm performs expected O(k/n ε^{-2}) comparisons, matching the best possible approximation algorithm in the absence of computation faults. In contrast, for the exact selection problem, the expected number of comparisons is Θ(n log k) with faults versus Θ(n) without faults. Our results also indicate a clear distinction between approximating the minimum and approximating the k-th smallest element, which holds even for the high probability guarantee, e.g., if k = n/2, Q = 1/n and ε = n^{-α} for α ∈ (0, 1/2), the asymptotic difference is almost quadratic, i.e., Θ̃(n^α) versus Θ̃(n^{2α})., LIPIcs, Vol. 254, 40th International Symposium on Theoretical Aspects of Computer Science (STACS 2023), pages 37:1-37:23

We develop the first fast spectral algorithm to decompose a random third-order tensor over of rank up to O(d3/2/polylog(d)). Our algorithm only involves simple linear algebra operations and can recover all components in time O(d6.05) under the current matrix multiplication time. Prior to this work, comparable guarantees could only be achieved via sum-of-squares [Ma, Shi, Steurer 2016]. In contrast, fast algorithms [Hopkins, Schramm, Shi, Steurer 2016] could only decompose tensors of rank at most O(d4/3/polylog(d)). Our algorithmic result rests on two key ingredients. A clean lifting of the third-order tensor to a sixth-order tensor, which can be expressed in the language of tensor networks. A careful decomposition of the tensor network into a sequence of rectangular matrix multiplications, which allows us to have a fast implementation of the algorithm., Proceedings of Machine Learning Research, 178, ISSN:2640-3498, Proceedings of Thirty Fifth Conference on Learning Theory

We develop machinery to design efficiently computable and consistent estimators, achieving estimation error approaching zero as the number of observations grows, when facing an oblivious adversary that may corrupt responses in all but an α fraction of the samples. As concrete examples, we investigate two problems: sparse regression and principal component analysis (PCA). For sparse regression, we achieve consistency for optimal sample size n≳(klogd)/α^2 and optimal error rate O([(klogd)/(n⋅α^2)]^{1/2} where n is the number of observations, d is the number of dimensions and k is the sparsity of the parameter vector, allowing the fraction of inliers to be inverse-polynomial in the number of samples. Prior to this work, no estimator was known to be consistent when the fraction of inliers α is o(1/loglogn), even for (non-spherical) Gaussian design matrices. Results holding under weak design assumptions and in the presence of such general noise have only been shown in dense setting (i.e., general linear regression) very recently by d'Orsi et al. [dNS21]. In the context of PCA, we attain optimal error guarantees under broad spikiness assumptions on the parameter matrix (usually used in matrix completion). Previous works could obtain non-trivial guarantees only under the assumptions that the measurement noise corresponding to the inliers is polynomially small in n (e.g., Gaussian with variance 1/n^2). To devise our estimators, we equip the Huber loss with non-smooth regularizers such as the ℓ1 norm or the nuclear norm, and extend d'Orsi et al.'s approach [dNS21] in a novel way to analyze the loss function. Our machinery appears to be easily applicable to a wide range of estimation problems., Advances in Neural Information Processing Systems 34, ISBN:9781713845393

We consider the problem of sorting n elements in the case of persistent comparison errors. In this problem, each comparison between two elements can be wrong with some fixed (small) probability p, and comparisons cannot be repeated (Braverman and Mossel, SODA'08). Sorting perfectly in this model is impossible, and the objective is to minimize the dislocation of each element in the output sequence, that is, the difference between its true rank and its position. Existing lower bounds for this problem show that no algorithm can guarantee, with high probability, maximum dislocation and total dislocation better than Omega(log n) and Omega(n), respectively, regardless of its running time. In this paper, we present the first O(n log n)-time sorting algorithm that guarantees both O(log n) maximum dislocation and O(n) total dislocation with high probability. This settles the time complexity of this problem and shows that comparison errors do not increase its computational difficulty: a sequence with the best possible dislocation can be obtained in O(n log n) time and, even without comparison errors, Omega(n log n) time is necessary to guarantee such dislocation bounds. In order to achieve this optimality result, we solve two sub-problems in the persistent error comparisons model, and the respective methods have their own merits for further application. One is how to locate a position in which to insert an element in an almost-sorted sequence having O(log n) maximum dislocation in such a way that the dislocation of the resulting sequence will still be O(log n). The other is how to simultaneously insert m elements into an almost sorted sequence of m different elements, such that the resulting sequence of 2m elements remains almost sorted., Leibniz International Proceedings in Informatics (LIPIcs), 144, ISSN:1868-8969, 27th Annual European Symposium on Algorithms (ESA 2019), ISBN:978-3-95977-124-5

The geodesic Voronoi diagram of m point sites inside a simple polygon of n vertices is a subdivision of the polygon into m cells, one to each site, such that all points in a cell share the same nearest site under the geodesic distance. The best known lower bound for the construction time is Omega( n + m log m ), and a matching upper bound is a long-standing open question. The state-of-the-art construction algorithms achieve O( (n+m) log (n+m) ) and O( n+m log m log^2 n ) time, which are optimal for m=Omega(n) and m=O( n / log^3 n ), respectively. In this paper, we give a construction algorithm with O( n+m( log m+ log^2 n) ) time, and it is nearly optimal in the sense that if a single Voronoi vertex can be computed in O( log n ) time, then the construction time will become the optimal O( n+m log m ). In other words, we reduce the problem of constructing the diagram in the optimal time to the problem of computing a single Voronoi vertex in O( log n ) time.

We investigate higher-order Voronoi diagrams in the city metric. This metric is induced by quickest paths in the L1 metric in the presence of an accelerating transportation network of axis-parallel line segments. For the structural complexity of kth-order city Voronoi diagrams of n point sites, we show an upper bound of O(k(n - k) + kc) and a lower bound of {\Omega}(n + kc), where c is the complexity of the transportation network. This is quite different from the bound O(k(n - k)) in the Euclidean metric. For the special case where k = n - 1 the complexity in the Euclidean metric is O(n), while that in the city metric is {\Theta}(nc). Furthermore, we develop an O(k^2(n + c) log n)-time iterative algorithm to compute the kth-order city Voronoi diagram and an O(nc log^2(n + c) log n)-time divide-and-conquer algorithm to compute the farthest-site city Voronoi diagram., Comment: 15 pages, extended version of paper to appear in Proc. 13th Scandinavian Symposium and Workshops on Algorithm Theory (SWAT'12), Helsinki, Finland, 2012