#### Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues

Suguru Tamaki (Kyoto University); Yuichi Yoshida (National Institute of Informatics, and Preferred Infrastructure, Inc.)We provide evidence that computing the maximum flow value between every pair of nodes in a directed graph on $n$ nodes, $m$ edges, and capacities in the range $[1..n]$, which we call the All-Pairs Max-Flow problem, cannot be solved in time that is faster significantly than $O(n^2 m)$. Since a single maximum $st$-flow in such graphs can be solved in time $\tO(m\sqrt{n})$ [Lee and Sidford, FOCS 2014], we conclude that the all-pairs version might require time equivalent to $\tilde\Omega(n^{3/2})$ computations of maximum $st$-flow, which strongly separates the directed case from the undirected one. Moreover, if maximum $st$-flow can be solved in time $\tO(m)$, then the runtime of $\tilde\Omega(n^2)$ computations is needed. This is in contrast to a conjecture of Lacki, Nussbaum, Sankowski, and Wulf-Nilsen [FOCS 2012] that All-Pairs Max-Flow in general graphs can be solved faster than the time of $O(n^2)$ computations of maximum $st$-flow. Specifically, we show that in sparse graphs $G=(V,E,w)$, if one can compute All-Pairs Max-Flow in time $O((n^2 m)^{1-\varepsilon})$, for some constant $\varepsilon>0$, then MAX-CNF-SAT with $n'$ variables and $m'$ clauses can be solved in time ${m'}^{O(1)}2^{(1-\delta)n'}$ for a constant $\delta(\varepsilon)>0$, a problem for which not even $2^{n'}/\poly(n')$ algorithms are known. Such runtime for MAX-CNF-SAT would in particular refute the Strong Exponential Time Hypothesis (SETH). Hence, we improve the lower bound of Abboud, Vassilevska-Williams, and Yu [STOC 2015], who showed that for every fixed $\varepsilon>0$ and $\card{S}=\card{T}=O(\sqrt{n})$, if the above problem can be solved in time $O(n^{3/2-\varepsilon})$, then some incomparable (and intuitively weaker) conjecture is false.

We show how to compute for n-vertex planar graphs in O(n^{11/6} polylog(n)) expected time the diameter and the sum of the pairwise distances. The algorithms work for directed graphs with real weights and no negative cycles. In O(n^{15/8} polylog(n)) expected time we can also compute the number of pairs of vertices at distance smaller than a given threshold, These are the first algorithms for these problems using time O(n^c) for some constant c < 2, even when restricted to undirected, unweighted planar graphs.

Dynamic Time Warping (DTW) and Geometric Edit Distance (GED) are basic similarity measures between curves or general temporal sequences (e.g., time series) that are represented as sequences of points in some metric space $(X, dist)$. The DTW and GED measures are massively used in various fields of computer science and computational biology. Consequently, the tasks of computing these measures are among the core problems in P. Despite extensive efforts to find more efficient algorithms, the best-known algorithms for computing the DTW or GED between two sequences of points in $X = \mathbb{R}^d$ are long-standing dynamic programming algorithms that require quadratic runtime, even for the one-dimensional case $d = 1$, which is perhaps one of the most used in practice. In this paper, we break the nearly 50 years old quadratic time bound for computing DTW or GED between two sequences of $n$ points in $\mathbb{R}$, by presenting deterministic algorithms that run in $O\left( n^2 \log\log\log n / \log\log n \right)$ time. Our algorithms can be extended to work also for higher dimensional spaces $\mathbb{R}^d$, for any constant $d$, when the underlying distance-metric $dist$ is polyhedral (e.g., $L_1, L_\infty$).

A filtration over a simplicial complex K is an ordering of the simplices of K such that all prefixes in the ordering are subcomplexes of K. Filtrations are at the core of Persistent Homology, a major tool in Topological Data Analysis. In order to represent the filtration of a simplicial complex, the entire filtration can be appended to any data structure that explicitly stores all the simplices of the complex such as the Hasse diagram or the recently introduced Simplex Tree [Algorithmica '14]. However, with the popularity of various computational methods that need to handle simplicial complexes, and with the rapidly increasing size of the complexes, the task of finding a compact data structure that can still support efficient queries is of great interest. In this paper, we propose a new data structure called the Critical Simplex Diagram (CSD) which is a variant of the Simplex Array List (SAL) [SoCG '15]. Our data structure allows to store in a compact way the filtration of a simplicial complex, and allows for the efficient implementation of a large range of basic operations. Moreover, we prove that our data structure is essentially optimal with respect to the requisite storage space. Finally, we show that the CSD representation admits fast construction algorithms for Flag complexes and relaxed Delaunay complexes.

Properties definable in first-order logic are algorithmically interesting for both theoretical and pragmatic reasons. Many of the most studied algorithmic problems, such as Hitting Set and Orthogonal Vectors, are first-order, and the first-order properties naturally arise as relational database queries. A relatively straightforward algorithm for evaluating a property with k+1 quantifiers takes time $O(m^k)$ and, assuming the Strong Exponential Time Hypothesis (SETH), some such properties require $O(m^{k-\epsilon})$ time for any $\epsilon > 0$. (Here, m represents the size of the input structure, i.e. the number of tuples in all relations.) We give algorithms for every first-order property that improves this upper bound to $m^k/2^{\Theta(\sqrt{\log n})}$, i.e., an improvement by a factor more than any poly-log, but less than the polynomial required to refute SETH. Moreover, we show that further improvement is equivalent to improving algorithms for sparse instances of the well-studied Orthogonal Vectors problem. Surprisingly, both results are obtained by showing completeness of the Sparse Orthogonal Vectors problem for the class of first-order properties under fine-grained reductions. To obtain improved algorithms, we apply the fast Orthogonal Vectors algorithm of [AWY15,CW16]. While fine-grained reductions (reductions that closely preserve the conjectured complexities of problems) have been used to relate the hardness of disparate specific problems both within P and beyond, this is the first such completeness result for a standard complexity class.

We study the problem of testing whether an unknown n-variable Boolean function is a k-junta in the distribution-free property testing model, where the distance between functions is measured with respect to an arbitrary and unknown probability distribution over {0,1}^{n}. Our first main result is that distribution-free k-junta testing can be performed, with one-sided error, by an adaptive algorithm that uses Õ(k^{2})/µ queries (independent of n). Complementing this, our second main result is a lower bound showing that any non-adaptive distribution-free k-junta testing algorithm must make ©(2^{k/3}) queries even to test to accuracy µ = 1/3. These bounds establish that while the optimal query complexity of non-adaptive k-junta testing is 2^{(k)}, for adaptive testing it is poly(k), and thus show that adaptivity provides an exponential improvement in the distribution-free query complexity of testing juntas.

We study the online submodular maximization problem with free disposal under a matroid constraint. Elements from some ground set arrive one by one in rounds, and the algorithm maintains a feasible set that is independent in the underlying matroid. In each round when a new element arrives, the algorithm may accept the new element into its feasible set and possibly remove elements from it, provided that the resulting set is still independent. The goal is to maximize the value of the final feasible set under some monotone submodular function, to which the algorithm has oracle access. For $k$-uniform matroids, we give a deterministic algorithm with competitive ratio at least $0.2959$, and the ratio approaches $\frac{1}{\alpha_\infty} \approx 0.3178$ as $k$ approaches infinity, improving the previous best ratio of $0.25$ by Chakrabarti and Kale (IPCO 2014), Buchbinder et al.\ (SODA 2015) and Chekuri et al. (ICALP 2015). We also show that our algorithm is optimal among a class of deterministic monotone algorithms that accept a new arriving element only if the objective is strictly increased. Further, we prove that no deterministic monotone algorithm can be strictly better than $0.25$-competitive even for partition matroids, the most modest generalization of $k$-uniform matroids, matching the competitive ratio by Chakrabarti and Kale (IPCO 2014) and Chekuri et al. (ICALP 2015). Interestingly, we show that randomized algorithms are strictly more powerful by giving a (non-monotone) randomized algorithm for partition matroids with ratio $\frac{1}{\alpha_\infty} \approx 0.3178$.

We propose polynomial-time algorithms that sparsify planar and bounded-genus graphs while preserving optimal or near-optimal solutions to Steiner problems. Our main contribution is a polynomial-time algorithm that, given an unweighted graph $G$ embedded on a surface of genus $g$ and a designated face $f$ bounded by a simple cycle of length $k$, uncovers a set $F \subseteq E(G)$ of size polynomial in $g$ and $k$ that contains an optimal Steiner tree for any set of terminals that is a subset of the vertices of $f$. We apply this general theorem to prove that: * given an unweighted graph $G$ embedded on a surface of genus $g$ and a terminal set $\terms \subseteq V(G)$, one can in polynomial time find a set $F \subseteq E(G)$ that contains an optimal Steiner tree $T$ for $\terms$ and that has size polynomial in $g$ and $|E(T)|$; * an analogous result holds for an optimal Steiner forest for a set $T$ of terminal pairs; * given an unweighted planar graph $G$ and a terminal set $\terms \subseteq V(G)$, one can in polynomial time find a set $F \subseteq E(G)$ that contains an optimal (edge) multiway cut $C$ separating $\terms$ (i.e., a cutset that intersects any path with endpoints in different terminals from $\terms$) and that has size polynomial in $|C|$.

Given a planar graph $G$ and a partition of the neighbors of each vertex $v$ in four sets $\overset{\nearrow}{v}$, $\overset{\nwarrow}{v}$, $\overset{\swarrow}{v}$, and $\overset{\searrow}{v}$, the problem {\sc Windrose Planarity} asks to decide whether $G$ admits a \emph{windrose-planar drawing}, that is, a planar drawing in which \begin{inparaenum}[(i)] \item each neighbor $u \in \overset{\nearrow}{v}$ is above and to the right of $v$, \item each neighbor $u \in \overset{\nwarrow}{v}$ is above and to the left of $v$, \item each neighbor $u \in \overset{\swarrow}{v}$ is below and to the left of $v$, \item each neighbor $u \in \overset{\searrow}{v}$ is below and to the right of $v$, and \item edges are represented by curves that are monotone with respect to each axis. \end{inparaenum} By exploiting both the horizontal and the vertical relationship among vertices, windrose-planar drawings allow to simultaneously visualize two partial orders defined by means of the edges of the graph. Although the problem is NP-complete in the general case, we give a polynomial-time algorithm for testing whether there exists a windrose-planar drawing that respects a given combinatorial embedding. This algorithm is based on a characterization of the plane triangulations admitting a windrose-planar drawing. Furthermore, for any embedded graph with $n$ vertices that has a windrose-planar drawing, we can construct one with at most one bend per edge and with at most $2n-5$ bends in total, which lies on the $3n \times 3n$ grid. The latter result contrasts with the fact that straight-line windrose-planar drawings may require exponential area.

We consider a natural generalization of the classical multiple knapsack problem in which instead of packing single items we are packing groups of items. In this problem, we have multiple knapsacks and a set of items which are partitioned into groups. Each item has an individual weight, while the profit is associated with groups rather than items. The profit of a group can be attained if and only if every item of this group is packed. Such a general model finds applications in various practical problems, e.g., delivering bundles of goods. The tractability of this problem relies heavily on how large a group could be. Deciding if a group of items of total weight $2$ could be packed into two knapsacks of unit capacity is already $NP$-hard and it thus rules out a constant-approximation algorithm for this problem in general. We then focus on the parameterized version where the total weight of items in each group is bounded by a factor $\delta$ of the total capacity of all knapsacks. Both approximation and inapproximability results with respect to $\delta$ are derived. We also show that, depending on whether the number of knapsacks is a constant or part of the input, the approximation ratio for the problem, as a function on $\delta$, changes substantially, which has a clear difference from the classical multiple knapsack problem.

We study a path-planning problem amid a set *O* of obstacles in *R*^{2}, in which we wish to compute a short path between two points while also maintaining a high clearance from *O*; the clearance of a point is its distance from a nearest obstacle in *O*. Specifically, the problem asks for a path minimizing the reciprocal of the clearance integrated over the length of the path. We present the first polynomial-time approximation scheme for this problem. Let *n* be the total number of obstacle vertices and let µ (0,1]. Our algorithm computes in time *O*((*n*^{2} / µ^{2}) log(*n* / µ)) a path of total cost at most (1+µ) times the cost of the optimal path.

Unaggregated data, in a streamed or distributed form, is prevalent and comes from diverse sources such as interactions of users with web services and IP traffic. Data elements have {\em keys} (cookies, users, queries) and elements with different keys interleave. Analytics on such data typically utilizes statistics expressed as a sum over keys in a specified segment of a function $f$ applied to the frequency (the total number of occurrences) of the key. In particular, {\em Distinct} is the number of active keys in the segment, {\em Sum} is the sum of their frequencies, and both are special cases of {\em frequency cap} statistics, which cap the frequency by a parameter T. The number of distinct active keys in the data can be very large, making exact computation of queries costly. Instead, we can estimate these statistics from a sample. An optimal sample for a given function $f$ would include a key with frequency $w$ with probability roughly proportional to $f(w)$. But while such a "gold-standard" sample can be easily computed over the aggregated data (the set of key-frequency pairs), exact aggregation itself is costly, requiring state proportional to the number of active keys. Ideally, we would like to compute a sample without exact aggregation. We present a sampling framework for unaggregated data that uses a single pass (for streams) or two passes (for distributed data) and state equal to the desired sample size and applies to all cap statistics.

Many randomized algorithms can be derandomized efficiently using either the method of conditional expectations or probability spaces with low (almost-) independence. A series of papers, beginning with Luby (1988) and continuing with Berger \& Rompel (1991) and Chari et al. (1994), showed that these techniques can be combined to give deterministic parallel algorithms for combinatorial optimization problems involving sums of $w$-juntas. We improve these algorithms through derandomized variable partitioning and a new code construction for fooling Fourier characters over $GF(2)$. This reduces the processor complexity to essentially independent of $w$ while the running time is reduced from exponential in $w$ to linear in $w$. As a key subroutine, we give a new algorithm to generate a probability space which can fool a given set of neighborhoods, each of size at most $w$. Schulman (1992) gave an NC algorithm to do so for $w \leq O(\log n)$. Our new algorithm is NC1, with essentially optimal time and processor complexity, when $w = O(\log n)$; it remains NC up to $w = \text{polylog}(n)$. This answers an open problem of Schulman. One major application of these algorithms is an NC algorithm for the Lov\'{a}sz Local Lemma. Previous NC algorithms, including the seminal algorithm of Moser \& Tardos (2010) and the work of Chandrasekaran et. al (2013), required that (essentially) the bad-events could span only $O(\log n)$ variables; we relax this to $\text{polylog}(n)$ variables. We use this to give algorithms for defective vertex coloring and domatic graph partition in graphs of maximum degree $\text{polylog}(n)$.

We study the unsplittable flow on a path problem (UFP), which arises naturally in many applications such as bandwidth allocation, job scheduling, and caching. Here we are given a path with nonnegative edge capacities and a set of tasks, which are characterized by a subpath, a demand, and a profit. The goal is to find the most profitable subset of tasks whose total demand does not violate the edge capacities. If the demand of each task is at most a small enough fraction $\delta$ of the capacity along its subpath ($\delta$-small tasks), then it has been known for a long time [Chekuri et al., ICALP 2003] how to compute a solution of value arbitrarily close to the optimum via LP rounding. However, much remains unknown for the complementary case, that is, when the demand of each task is at least some fraction $\delta>0$ of the smallest capacity of its subpath ($\delta$-large tasks). For this setting a constant factor approximation, improving on an earlier logarithmic approximation, was found only recently~[Bonsma et al., FOCS 2011]. In this paper we present a PTAS for $\delta$-large tasks, for any constant $\delta>0$. Key to this result is a complex geometrically inspired dynamic program. Our result implies a $2+\epsilon$ approximation for UFP, for any constant $\epsilon>0$, improving on the previously best $7+\epsilon$ approximation by Bonsma et al. We remark that our improved approximation algorithm matches the best known approximation ratio for the considerably easier special case of uniform edge capacities.

We introduce the dependent doors problem as an abstraction for situations in which one must perform a sequence of dependent decisions, without receiving feedback information on the effectiveness of previously made actions. Informally, the problem considers a set of d doors that are initially closed. To open a door, the algorithm knocks on it and it might open or not according to some probability distribution. This distribution may depend on which other doors are currently open, as well as on which other doors were open during each of the previous knocks on that door. The algorithm aims to minimize the expected time until all doors open without knowing whether or which other doors have already opened. Here, we focus on scenarios where dependencies are positively correlated and acyclic. The fundamental distribution of a door describes the probability it opens in the best of conditions. We show that if in two configurations corresponding doors share the same fundamental distribution, then these configurations have the same optimal running time up to a universal constant, no matter what are the dependencies between doors and what are the distributions. We also identify algorithms that are optimal up to a universal constant factor. We then turn our attention to investigate precise bounds. Even for the case of two doors, identifying the optimal sequence is an intriguing combinatorial question. Here, we study the case of two cascading memoryless doors and solve it almost completely.

We consider the problem of estimating the size of a maximum matching when the edges are revealed in a streaming fashion. When the input graph is planar, we present a simple and elegant streaming algorithm that with high probability estimates the size of a maximum matching within a constant factor using O(n^{2/3}) space, where n is the number of vertices. The approach generalizes to the family of graphs that have bounded arboricity, which include graphs with an excluded constant-size minor. To the best of our knowledge, this is the first result for estimating the size of a maximum matching in the adversarial-order streaming model in o(n) space. We circumvent the barriers inherent in the adversarial-order model by exploiting several structural properties of planar graphs, and more generally, graphs with bounded arboricity. We further reduce the required memory size to O(\sqrt{n}) for three restricted settings: (i) when the input graph is a forest and (ii) when we have 2-passes and the input graph has bounded arboricity. Finally, we design a reduction from the Boolean Hidden Matching Problem to show that there is no randomized streaming algorithm that estimates the size of the maximum matching to within a factor better than 3/2 and uses only o(n^{1/2}) bits of space. Using the same reduction, we show that there is no deterministic algorithm that computes this kind of estimate in $o(n)$ bits of space. The lower bounds hold even for graphs that are collections of paths of constant length.

We give the first optimal bounds for returning the $\ell_1$-heavy hitters in a data stream of insertions, together with their approximate frequencies, closing a long line of work on this problem. For a stream of $m$ items in $\{1, 2, \ldots, n\}$ and parameters $0 < \epsilon < \phi \leq 1$, let $f_i$ denote the frequency of item $i$, i.e., the number of times item $i$ occurs in the stream. With arbitrarily large constant probability, our algorithm returns all items $i$ for which $f_i \geq \phi m$, returns no items $j$ for which $f_j \leq (\phi -\epsilon)m$, and returns approximations $\tilde{f}_i$ with $|\tilde{f}_i - f_i| \leq \epsilon m$ for each item $i$ that it returns. Our algorithm uses $O(\epsilon^{-1} \log\phi^{-1} + \phi^{-1} \log n + \log \log m)$ bits of space, processes each stream update in $O(1)$ worst-case time, and can report its output in time linear in the output size. We also prove a lower bound, which implies that our algorithm is optimal up to a constant factor in its space complexity. A modification of our algorithm can be used to estimate the maximum frequency up to an additive $\epsilon m$ error in the above amount of space, resolving Question 3 in the IITK 2006 Workshop on Algorithms for Data Streams for the case of $\ell_1$-heavy hitters. We also introduce several variants of the heavy hitters problem, inspired by rank aggregation and voting schemes, and show how our techniques can be applied in such settings.

The main result of this paper is a generalization of the classical blossom algorithm for finding perfect matchings. Our algorithm can efficiently solve Boolean CSPs where each variable appears in exactly two constraints (we call it edge CSP) and all constraints are even -matroid relations (represented by lists of tuples). As a consequence of this, we settle the complexity classification of planar Boolean CSPs started by DvoYák and Kupec. Knowing that edge CSP is tractable for even -matroid constraints allows us to extend the tractability result to a larger class of -matroids that includes many classes that were known to be tractable before, namely co-independent, compact, local and binary.