Search ACM DL

Search Issue

enter search term and/or author name

**Editorial**: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016 Special Issue

Arnab Bhattacharyya, Fabrizio Grandoni, Aleksandar Nikolov, Barna Saha, Saket Saurabh, Aravindan Vijayaraghavan, Qin Zhang

Article No.: 26

DOI: 10.1145/3230647

**Subtree Isomorphism Revisited**

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

Article No.: 27

DOI: 10.1145/3093239

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...

**On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique**

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

Article No.: 28

DOI: 10.1145/3178538

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* ∼...

**CoveringLSH**: Locality-Sensitive Hashing without False Negatives

Rasmus Pagh

Article No.: 29

DOI: 10.1145/3155300

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...

**Improved Deterministic Algorithms for Linear Programming in Low Dimensions**

Timothy M. CHAN

Article No.: 30

DOI: 10.1145/3155312

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...

**A Faster Subquadratic Algorithm for Finding Outlier Correlations**

Matti Karppa, Petteri Kaski, Jukka Kohonen

Article No.: 31

DOI: 10.1145/3174804

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...

**Deterministic Algorithms for Submodular Maximization Problems**

Niv Buchbinder, Moran Feldman

Article No.: 32

DOI: 10.1145/3184990

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...

**Near-Optimal Light Spanners**

Shiri Chechik, Christian Wulff-Nilsen

Article No.: 33

DOI: 10.1145/3199607

A spanner *H* of a weighted undirected graph *G* is a “sparse” subgraph that approximately preserves distances between every pair of vertices in *G*. We refer to *H* as a δ-spanner of *G* for some...

**Fully Polynomial-Time Parameterized Computations for Graphs and Matrices of Low Treewidth**

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

Article No.: 34

DOI: 10.1145/3186898

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...

**Subexponential Parameterized Algorithm for I nterval Completion**

Ivan Bliznets, Fedor V. Fomin, Marcin Pilipczuk, MichaŁ Pilipczuk

Article No.: 35

DOI: 10.1145/3186896

In the I*n*-vertex graph *G* and an integer *k*, and the task is to transform *G* by making use of at most *k* edge additions into an interval graph. This is...

**Faster Algorithms for Computing Plurality Points**

Mark De Berg, Joachim Gudmundsson, Mehran Mehr

Article No.: 36

DOI: 10.1145/3186990

Let *V* be a set of *n* points in R^{d}, which we call voters. A point *p* ∈ R^{d} is preferred over another point *p*′ ∈ R^{d} by a voter υ ∈ *V* if...

**Erratum**: Approximating Minimum-Cost Connectivity Problems via Uncrossable Bifamilies

Zeev Nutov

Article No.: 37

DOI: 10.1145/3186991

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...

**Exploring the Complexity of Layout Parameters in Tournaments and Semicomplete Digraphs**

Florian Barbero, Christophe Paul, MichaŁ Pilipczuk

Article No.: 38

DOI: 10.1145/3196276

A simple digraph is *semicomplete* if for any two of its vertices *u* and *v*, at least one of the arcs (*u*,*v*) and (*v*,*u*) is present. We study the complexity of computing two layout parameters of...

**Data Structures for Weighted Matching and Extensions to b-matching and f-factors**

Harold N. Gabow

Article No.: 39

DOI: 10.1145/3183369

This article shows the weighted matching problem on general graphs can be solved in time *O*(*n*(*m* + *n* log *n*)) for *n* and *m* the number of vertices and edges, respectively. This was previously known only...