In the 3SUM problem we are given three lists \(\mathcal {A}\) , \(\mathcal {B}\) , \(\mathcal {C}\) , of n real numbers, and are asked to find \((a,b,c)\in \mathcal {A}\times \mathcal {B}\times \mathcal {C}\) such that \(a+b=c\) . The longstanding 3SUM conjecture—that 3SUM could not be solved in subquadratic time—was recently refuted by Grønlund and Pettie. They presented \(\hbox {O}\left( n^2(\log \log n)^{\alpha }/(\log n)^{\beta }\right) \) algorithms for 3SUM and for the related problems Convolution3SUM and ZeroTriangle, where \(\alpha \) and \(\beta \) are constants that depend on the problem and whether the algorithm is deterministic or randomized (and for ZeroTriangle the main factor is \(n^3\) rather than \(n^2\) ). We simplify Grønlund and Pettie’s algorithms and obtain better bounds, namely, \(\alpha =\beta =1\) , deterministically. For 3SUM our bound is better than both the deterministic and the randomized bounds of Grønlund and Pettie. For the other problems our bounds are better than their deterministic bounds, and match their randomized bounds.

Drawing a random variate from a given binomial distribution B(n, p) is an important subroutine in many large-scale simulations. The naive algorithm takes \(\mathcal {O}(n)\) time w.h.p. in the WordRAM model, which is too slow in many settings, though to its credit, it does not suffer from precision loss. The problem of sampling from a binomial distribution in sublinear time has been extensively studied and implemented in such packages as R [22] and the GNU Scientific Library  [11], however, all previous sublinear-time algorithms involve precision loss, which introduces artifacts such as discontinuities into the sampling. In this paper, we present the first algorithm, to the best of our knowledge, that samples binomial distributions in sublinear time with no precision loss. We assume that each bit of p can be obtained in \(\mathcal {O}(1)\) time.

We study the problem of finding a spanning tree with maximum number of leaves. We present a simple, linear time 2-approximation algorithm for this problem, improving on the previous best known algorithm for the problem, which has approximation ratio 3.

We investigate the design of dynamic programming algorithms in unreliable memories, i.e., in the presence of errors that lead the logical state of some bits to be read differently from how they were last written. Assuming that a limited number of memory faults can be inserted at run-time by an adversary with unbounded computational power, we obtain the first resilient algorithms for a broad range of dynamic programming problems, devising a general framework that can be applied to both iterative and recursive implementations. Besides all local dependency problems, where updates to table entries are determined by the contents of neighboring cells, we also settle challenging non-local problems, such as all-pairs shortest paths and matrix multiplication. All our algorithms are correct with high probability and match the running time of their standard non-resilient counterparts while tolerating a polynomial number of faults. The recursive algorithms are also cache-efficient and can tolerate faults at any level of the memory hierarchy. Our results exploit a careful combination of data replication, majority techniques, fingerprint computations, and lazy fault detection. To cope with the complex data access patterns induced by some of our algorithms, we also devise amplified fingerprints, which might be of independent interest in the design of resilient algorithms for different problems.

We introduce a new structure for a set of points in the plane and an angle \(\alpha \) , which is similar in flavor to a bounded-degree MST. We name this structure \(\alpha \) -MST. Let P be a set of points in the plane and let \(0 < \alpha \le 2\pi \) be an angle. An \(\alpha \) -ST of P is a spanning tree of the complete Euclidean graph induced by P, with the additional property that for each point \(p \in P\) , the smallest angle around p containing all the edges adjacent to p is at most \(\alpha \) . An \(\alpha \) -MST of P is then an \(\alpha \) -ST of P of minimum weight, where the weight of an \(\alpha \) -ST is the sum of the lengths of its edges. For \(\alpha < \pi /3\) , an \(\alpha \) -ST does not always exist, and, for \(\alpha \ge \pi /3\) , it always exists (Ackerman et al. in Comput Geom Theory Appl 46(3):213–218, 2013; Aichholzer et al. in Comput Geom Theory Appl 46(1):17–28, 2013; Carmi et al. in Comput Geom Theory Appl 44(9):477–485, 2011). In this paper, we study the problem of computing an \(\alpha \) -MST for several common values of \(\alpha \) . Motivated by wireless networks, we formulate the problem in terms of directional antennas. With each point \(p \in P\) , we associate a wedge \({\textsc {w}_{p}}\) of angle \(\alpha \) and apex p. The goal is to assign an orientation and a radius \(r_p\) to each wedge \({\textsc {w}_{p}}\) , such that the resulting graph is connected and its MST is an \(\alpha \) -MST (we draw an edge between p and q if \(p \in {\textsc {w}_{q}}\) , \(q \in {\textsc {w}_{p}}\) , and \(|pq| \le r_p, r_q\) ). We prove that the problem of computing an \(\alpha \) -MST is NP-hard, at least for \(\alpha =\pi \) and \(\alpha =2\pi /3\) , and present constant-factor approximation algorithms for \(\alpha = \pi /2, 2\pi /3, \pi \) . One of our major results is a surprising theorem for \(\alpha = 2\pi /3\) , which, besides being interesting from a geometric point of view, has important applications. For example, the theorem guarantees that given any set P of 3n points in the plane and any partitioning of the points into n triplets, one can orient the wedges of each triplet independently, such that the graph induced by P is connected. We apply the theorem to the antenna conversion problem and to the orientation and power assignment problem.

In this paper, we study the problem of augmenting a planar graph such that it becomes \(k\) -regular, \(c\) -connected and remains planar, either in the sense that the augmented graph is planar, or in the sense that the input graph has a fixed (topological) planar embedding that can be extended to a planar embedding of the augmented graph. We fully classify the complexity of this problem for all values of  \(k\) and  \(c\) in both, the variable embedding and the fixed embedding case. For  \(k \le 2\) all problems are simple and for  \(k \ge 4\) all problems are NP-complete. Our main results are efficient algorithms (with running time \(O(n^{1.5}))\) for deciding the existence of a \(c\) -connected, 3-regular augmentation of a graph with a fixed planar embedding for  \(c=0,1,2\) and a corresponding hardness result for  \(c=3\) . The algorithms are such that for yes-instances a corresponding augmentation can be constructed in the same running time.

We design a sublinear Fourier sampling algorithm for a case of sparse off-grid frequency recovery. These are signals with the form \(f(t) = \sum _{j=1}^k a_j \mathrm{e}^{i\omega _j t} + \int \nu (\omega )\mathrm{e}^{i\omega t}d\mu (\omega )\) ; i.e., exponential polynomials with a noise term. The frequencies \(\{\omega _j\}\) satisfy \(\omega _j\in [\eta ,2\pi -\eta ]\) and \(\min _{i\ne j} |\omega _i-\omega _j|\ge \eta \) for some \(\eta > 0\) . We design a sublinear time randomized algorithm which, for any \(\epsilon \in (0,\eta /k]\) , which takes \(O(k\log k\log (1/\epsilon )(\log k+\log (\Vert a\Vert _1/\Vert \nu \Vert _1))\) samples of \(f(t)\) and runs in time proportional to number of samples, recovering \(\omega _j'\approx \omega _j\) and \(a_j'\approx a_j\) such that, with probability \(\varOmega (1)\) , the approximation error satisfies \(|\omega _j'-\omega _j|\le \epsilon \) and \(|a_j-a_j'|\le \Vert \nu \Vert _1/k\) for all \(j\) with \(|a_j|\ge \Vert \nu \Vert _1/k\) . We apply our model and algorithm to bearing estimation or source localization and discuss their implications for receiver array processing.

We consider the facility location problem with submodular penalties (FLPSP) and the facility location problem with linear penalties (FLPLP), two extensions of the classical facility location problem (FLP). First, we introduce a general algorithmic framework for a class of covering problems with submodular penalties, extending the recent result of Geunes et al. (Math Program 130:85–106, 2011) with linear penalties. This framework leverages existing approximation results for the original covering problems to obtain corresponding results for their counterparts with submodular penalties. Specifically, any LP-based \(\alpha \) -approximation for the original covering problem can be leveraged to obtain an \(\left( 1-e^{-1/\alpha }\right) ^{-1}\) -approximation algorithm for the counterpart with submodular penalties. Consequently, any LP-based approximation algorithm for the classical FLP (as a covering problem) can yield, via this framework, an approximation algorithm for the counterpart with submodular penalties. Second, by exploiting some special properties of submodular/linear penalty function, we present an LP rounding algorithm which has the currently best \(2\) -approximation ratio over the previously best \(2.375\) by Li et al. (Theoret Comput Sci 476:109–117, 2013) for the FLPSP and another LP-rounding algorithm which has the currently best \(1.5148\) -approximation ratio over the previously best \(1.853\) by Xu and Xu (J Comb Optim 17:424–436, 2008) for the FLPLP, respectively.