Abstract: Amir Abboud, Arturs Backurs, Thomas Dueholm Hansen, Virginia Vassilevska Williams, Or Zamir

The Subtree Isomorphism problem asks whether a given tree is contained in another given tree. The problem is of fundamental importance and has been studied since the 1960s. For some variants, e.g., ordered trees, near-linear time algorithms are known, but for the general case truly subquadratic algorithms remain elusive. Our first result is a reduction from the Orthogonal Vectors problem to Subtree Isomorphism, showing that a truly subquadratic algorithm for the latter refutes the Strong Exponential Time Hypothesis (SETH). In light of this conditional lower bound, we focus on natural special cases for which no truly subquadratic algorithms are known. We classify these cases against the quadratic barrier, showing in particular that: • Even for binary, rooted trees, a truly subquadratic algorithm refutes SETH. PubDate: Sat, 16 Jun 2018 00:00:00 GMT

Abstract: Samuel B. Hopkins, Pravesh Kothari, Aaron Henry Potechin, Prasad Raghavendra, Tselil Schramm

The problem of finding large cliques in random graphs and its “planted” variant, where one wants to recover a clique of size ω ≫ log (n) added to an Erdős-Rényi graph G ∼ G(n,&frac;12), have been intensely studied. Nevertheless, existing polynomial time algorithms can only recover planted cliques of size ω = Ω (&sqrt; n). By contrast, information theoretically, one can recover planted cliques so long as ω &Gt log (n). In this work, we continue the investigation of algorithms from the Sum of Squares hierarchy for solving the planted clique problem begun by Meka, Potechin, and Wigderson [2] and Deshpande and Montanari [25]. PubDate: Sat, 16 Jun 2018 00:00:00 GMT

We consider a new construction of locality-sensitive hash functions for Hamming space that is covering in the sense that is it guaranteed to produce a collision for every pair of vectors within a given radius r. The construction is efficient in the sense that the expected number of hash collisions between vectors at distance cr, for a given c>1, comes close to that of the best possible data independent LSH without the covering guarantee, namely, the seminal LSH construction of Indyk and Motwani (STOC’98). The efficiency of the new construction essentially matches their bound when the search radius is not too large—e.g., when cr = o(log (n)/ log log n), where n is the number of points in the dataset, and when cr = log (n)/k, where k is an integer constant. PubDate: Sat, 16 Jun 2018 00:00:00 GMT

Chazelle and Matoušek [J. Algorithms, 1996] presented a derandomization of Clarkson’s sampling-based algorithm [J. ACM, 1995] for solving linear programs with n constraints and d variables in d(7+o(1))dn deterministic time. The time bound can be improved to d(5+o(1))dn with subsequent work by Brönnimann, Chazelle, and Matoušek [SIAM J. Comput., 1999]. We first point out a much simpler derandomization of Clarkson’s algorithm that avoids ϵ-approximations and runs in d(3+o(1))dn time. We then describe a few additional ideas that eventually improve the deterministic time bound to d(1/2+o(1))dn. PubDate: Sat, 16 Jun 2018 00:00:00 GMT

Abstract: Matti Karppa, Petteri Kaski, Jukka Kohonen

We study the problem of detecting outlier pairs of strongly correlated variables among a collection of n variables with otherwise weak pairwise correlations. After normalization, this task amounts to the geometric task where we are given as input a set of n vectors with unit Euclidean norm and dimension d, and for some constants 0 PubDate: Sat, 16 Jun 2018 00:00:00 GMT

Randomization is a fundamental tool used in many theoretical and practical areas of computer science. We study here the role of randomization in the area of submodular function maximization. In this area, most algorithms are randomized, and in almost all cases the approximation ratios obtained by current randomized algorithms are superior to the best results obtained by known deterministic algorithms. Derandomization of algorithms for general submodular function maximization seems hard since the access to the function is done via a value oracle. This makes it hard, for example, to apply standard derandomization techniques such as conditional expectations. Therefore, an interesting fundamental problem in this area is whether randomization is inherently necessary for obtaining good approximation ratios. PubDate: Sat, 16 Jun 2018 00:00:00 GMT

Abstract: Fedor V. Fomin, Daniel Lokshtanov, Saket Saurabh, MichaŁ Pilipczuk, Marcin Wrochna

We investigate the complexity of several fundamental polynomial-time solvable problems on graphs and on matrices, when the given instance has low treewidth; in the case of matrices, we consider the treewidth of the graph formed by non-zero entries. In each of the considered cases, the best known algorithms working on general graphs run in polynomial time; however, the exponent of the polynomial is large. Therefore, our main goal is to construct algorithms with running time of the form poly(k)ṡ n or poly(k)ṡ nlog n, where k is the width of the tree decomposition given on the input. Such procedures would outperform the best known algorithms for the considered problems already for moderate values of the treewidth, like O(n1/c) for a constant c. PubDate: Sat, 16 Jun 2018 00:00:00 GMT

Abstract: Mark De Berg, Joachim Gudmundsson, Mehran Mehr

Let V be a set of n points in Rd, which we call voters. A point p ∈ Rd is preferred over another point p′ ∈ Rd by a voter υ ∈ V if dist(υ, p) < dist(υ, p′). A point p is called a plurality point if it is preferred by at least as many voters as any other point p′. We present an algorithm that decides in O(nlogn) time whether V admits a plurality point in the L2 norm and, if so, finds the (unique) plurality point. We also give efficient algorithms to compute a minimum-cost subset W ⊂ V such that V\W admits a plurality point, and to compute a so-called minimum-radius plurality ball. PubDate: Sat, 16 Jun 2018 00:00:00 GMT

There are two errors in our article “Approximating Minimum-Cost Connectivity Problems via Uncrossable Bifamilies” (ACM Transactions on Algorithms (TALG), 9(1), Article No. 1, 2012). In that article, we consider the (undirected) SURVIVABLE NETWORK problem. The input consists of a graph G&equal;(V,E) with edge-costs, a set T ⊆ V of terminals, and connectivity demands {rst> 0 : st ∈ D ⊆ T × T} . The goal is to find a minimum cost subgraph of G that for all st ∈ D contains rst pairwise internally disjoint st-paths. We claimed ratios O(k ln k) for rooted demands when the set D of demand pairs form a star, where k &equal; maxst∈Drst is the maximum demand. PubDate: Sat, 16 Jun 2018 00:00:00 GMT