ACM DL

ACM Transactions on

Algorithms (TALG)

Menu
Latest Articles

Selection and Sorting in the “Restore” Model

Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal

Deterministic Truncation of Linear Matroids

Efficient Computation of Middle Levels Gray Codes

Approximation Algorithms for Minimum-Load k-Facility Location

Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time

Randomized Embeddings with Slack and High-Dimensional Approximate Nearest Neighbor

The Alternating Stock Size Problem and the Gasoline Puzzle

Perfect Phylogenies via Branchings in Acyclic Digraphs and a Generalization of Dilworth’s Theorem

Distributed Online and Stochastic Queueing on a Multiple Access Channel

Computing 2-Walks in Polynomial Time

NEWS

In Memoriam: David S. Johnson

http://dl.acm.org/citation.cfm?id=2907073

About TALG

The ACM Transactions on Algorithms (TALG) publishes original research of the highest quality dealing with algorithms that are inherently discrete and finite, and having mathematical content in a natural way, either in the objective or in the analysis.

read more

Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues

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

The problem of finding large cliques in random graphs and its ``planted" variant, where one wants to recover a clique of size $\omega \gg \log{(n)}$ added to an \Erdos-\Renyi graph $G \sim G(n,\frac{1}{2})$, have been intensely studied. Nevertheless, existing polynomial time algorithms can only recover planted cliques of size $\omega = \Omega(\sqrt{n})$. By contrast, information theoretically, one can recover planted cliques so long as $\omega \gg \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 \cite{MPW15} and Deshpande and Montanari \cite{DM15}. Our main result is that degree four SoS does not recover the planted clique unless $\omega \gg \sqrt n / \polylog n$, improving upon the bound $\omega \gg n^{1/3}$ due to \cite{DM15}. An argument of Kelner shows that the this result cannot be proved using the same certificate as prior works. Rather, our proof involves constructing and analyzing a new certificate that yields the nearly tight lower bound by ``correcting" the certificate of \cite{MPW15,DM15,FeigeK03}.

Firefighting on Trees Beyond Integrality Gaps

The Firefighter problem and a variant of it, known as Resource Minimization for Fire Containment (RMFC), are natural models for optimal inhibition of harmful spreading processes. Despite considerable progress on several fronts, the approximability of these problems is still badly understood. This is the case even when the underlying graph is a tree, which is one of the most-studied graph structures in this context and the focus of this paper. In their simplest version, a fire spreads from one fixed vertex step by step from burning to adjacent non-burning vertices, and at each time step B many non-burning vertices can be protected from catching fire. The Firefighter problem asks, for a given B, to maximize the number of vertices that will not catch fire, whereas RMFC (on a tree) asks to find the smallest B that allows for saving all leaves of the tree. Prior to this work, the best known approximation ratios were an O(1)-approximation for the Firefighter problem and an O(log^* n)-approximation for RMFC, both being LP-based and essentially matching the integrality gaps of two natural LP relaxations. We improve on both approximations by presenting a PTAS for the Firefighter problem and an O(1)-approximation for RMFC, both qualitatively matching the known hardness results. Our results are obtained through a combination of the known LPs with several new techniques, which allow for efficiently enumerating over super-constant size sets of constraints to strengthen the natural LPs.

Erratum: Approximating minimum-cost connectivity problems via uncrossable bifamilies

There are two errors in our paper ``Approximating minimum-cost connectivity problems via uncrossable bifamilies'' (ACM Transactions on Algorithms (TALG), 9(1), Article No. 1, 2012). In that paper we consider the (undirected) {\sc Survivable Network} problem. The input consists of a graph $G=(V,E)$ with edge-costs, a set $T \subs V$ of terminals, and connectivity demands $\{r_{st}>0:st \in D \subs T \times T\}$. The goal is to find a minimum cost subgraph $H$ of $G$ that for all $st \in D$ contains $r_{st}$ pairwise internally-disjoint $st$-paths. We claimed ratios $O(k \ln k)$ for rooted demands when the set $D$ of demand pairs forms a star, where $k=\max_{st \in D} r_{st}$ is the maximum demand. This ratio is correct when the requirements are $r_{st}=k$ for all $t \in T \sem \{s\}$, but for general rooted demands our paper implies only ratio $O(k^2)$ (which however is still the currently best known ratio for the problem). We also obtained various ratios for the node-weighted version of the problem. These results are valid, but the proof needs a correction described here.

Batched Point Location in SINR Diagrams via Algebraic Tools

The SINR model attempts to predict whether a particular transmitter is heard at a specific location, in a setting consisting of n simultaneous transmitters and background noise. The SINR model gives rise to the SINR diagram, which partitions the space into n regions, one per transmitter, and the remaining space where no transmitter can be heard. Point location in the SINR diagram, i.e., determining which transmitter is heard at a query point (if any), has been investigated in several papers. These planar data structures are constructed in time at least quadratic in n and support logarithmic-time approximate queries. Moreover, the performance of some of them depends also on some geometric parameters that cannot be bounded as a function of n or epsilon. In this paper, we address the question of batched point-location queries, i.e., answering many queries simultaneously. In one dimension, we can answer n queries exactly in amortized polylogarithmic time per query, while in the plane we can do it approximately. These results can handle arbitrary power assignments to the transmitters. Moreover, the amortized query time depends only on n and epsilon. We also show how to speed up the preprocessing in a previously proposed point-location structure for uniform-power sites, by almost a full order of magnitude. For this we obtain results on the sensitivity of the reception regions to slight changes in the reception threshold, which are of independent interest. Finally, these results demonstrate the power of combining algebraic tools with those of computational geometry and other fields.

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

This paper 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 for bipartite graphs. The crux is a data structure for blossom creation. It uses a dynamic nearest-common-ancestor algorithm to simplify blossom steps, so they involve only back edges rather than arbitrary nontree edges. The rest of the paper presents direct extensions of Edmonds' blossom algorithm to weighted $b$-matching and $f$-factors. Again the time bound is the one previously known for bipartite graphs: for $b$-matching the time is $O(\min\{b(V),n\log n\}(m + n\log n))$ and for $f$-factors the time is $O(\min {f(V),m\log n\}( m + n\log n) )$, where $b(V)$ and $f(V)$ denote the sum of all degree constraints. Several immediate applications of the $f$-factor algorithm are given: The generalized shortest path structure of \cite{GS13}, i.e., the analog of the shortest path tree for conservative undirected graphs, is shown to be a version of the blossom structure for $f$-factors. This structure is found in time $O(|N|(m+n\log n))$ for $N$ the set of negative edges ($0<|N|

Conditional Lower Bounds for All-Pairs Max-Flow

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.

Fully polynomial-time parameterized computations for graphs and matrices of low treewidth

We investigate the complexity of several fundamental polynomial-time solvable problems on graphs and matrices of low treewidth. Our goal is to construct algorithms with running time of the form poly(k) * n, where k is the width of a tree decomposition given on input. Such procedures would outperform the best known algorithms already for moderate values of the treewidth, like O(n^{1/c}) for some small constant c. Our results include: - an algorithm for computing the determinant and the rank of an n x n matrix using O(k^3 * n) time and arithmetic operations; - an algorithm for solving a system of linear equations using O(k^3 * n) time and arithmetic operations; - an O(k^3 * n log n)-time randomized algorithm for finding the cardinality of a maximum matching in a graph; - an O(k^4 * n log^2 n)-time randomized algorithm for constructing a maximum matching in a graph; - an O(k^2 * n log n)-time algorithm for finding a maximum vertex flow in a directed graph. Moreover, we give an approximation algorithm for treewidth with suitable time complexity: given a graph G and integer k, in time O(k^7 * n log n) it concludes that G has treewidth larger than k, or constructs a decomposition of width O(k^2). The results stand in contrast with the recent work of Abboud et al. [SODA 2016], which shows that the algorithms with similar running times are unlikely for the problems of finding the diameter and radius of a graph of low treewidth.

Subquadratic Algorithms for the Diameter and the Sum of Pairwise Distances in Planar Graphs

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.

Deterministic Algorithms for Submodular Maximization Problems

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. In this work we give evidence that randomization is not necessary for obtaining good algorithms by presenting a new technique for derandomization of algorithms for submodular function maximization. Our high level idea is to maintain explicitly a (small) distribution over the states of the algorithm, and carefully update it using marginal values obtained from an extreme point solution of a suitable linear formulation. We demonstrate our technique on two recent algorithms for unconstrained submodular maximization and for maximizing submodular function subject to a cardinality constraint. In particular, for unconstrained submodular maximization we obtain an optimal deterministic $1/2$-approximation showing that randomization is unnecessary for obtaining optimal results for this setting.

Faster Algorithms for Computing Plurality Points

Let V be a set of n points in R^d, which we call voters, where d is a fixed constant. A point p in R^d is preferred over another point p' in R^d by a voter v in V if dist(v,p) < dist(v,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(n log n) time whether V admits a plurality point in the L_2 norm and, if so, finds the (unique) plurality point. We also give efficient algorithms to compute the smallest subset W of V such that V - W admits a plurality point, and to compute a so-called minimum-radius plurality ball. Finally, we consider the problem in the personalized L_1 norm, where each point v in V has a preference vector and the distance from v to any point p in R^d is given by sum_{i=1}^d w_i(v) cdot |x_i(v)-x_i(p)|. For this case we can compute in O(n^(d-1)) time the set of all plurality points of V. When all preference vectors are equal, the running time improves to O(n).

A Faster Subquadratic Algorithm for Finding Outlier Correlations

We study the problem of detecting {\em 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 we are asked to find all the outlier pairs of vectors whose inner product is at least $\rho$ in absolute value, subject to the promise that all but at most $q$ pairs of vectors have inner product at most $\tau$ in absolute value for some constants $0<\tau<\rho<1$. Improving on an algorithm of G.~Valiant [FOCS~2012; J.\,ACM~2015], we present a randomized algorithm that for Boolean inputs ($\{-1,1\}$-valued data normalized to unit Euclidean length) runs in time \[ \tilde O\bigl(n^{\max\,\{1-\gamma+M(\Delta\gamma,\gamma),\,M(1-\gamma,2\Delta\gamma)\}}+qdn^{2\gamma}\bigr)\,, \] where $0<\gamma<1$ is a constant tradeoff parameter and $M(\mu,\nu)$ is the exponent to multiply an $\lfloor n^\mu\rfloor\times\lfloor n^\nu\rfloor$ matrix with an $\lfloor n^\nu\rfloor\times \lfloor n^\mu\rfloor$ matrix and $\Delta=1/(1-\log_\tau\rho)$. As corollaries we obtain randomized algorithms that run in time \[ \tilde O\bigl(n^{\frac{2\omega}{3-\log_\tau\rho}}+qdn^{\frac{2(1-\log_\tau\rho)}{3-\log_\tau\rho}}\bigr) \] and in time \[ \tilde O\bigl(n^{\frac{4}{2+\alpha(1-\log_\tau\rho)}}+qdn^{\frac{2\alpha(1-\log_\tau\rho)}{2+\alpha(1-\log_\tau\rho)}}\bigr)\,, \] where $2\leq\omega<2.38$ is the exponent for square matrix multiplication and $0.3<\alpha\leq 1$ is the exponent for\, rectangular matrix multiplication. We present further corollaries for the light bulb problem and for learning sparse Boolean functions. (The notation {$\tilde O(\cdot)$} hides polylogarithmic factors in $n$ and $d$ whose degree may depend on $\rho$ and $\tau$.)

An Efficient Representation for Filtrations of Simplicial Complexes

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.

Completeness for First-Order Properties on Sparse Structures with Algorithmic Applications

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.

Exploring the complexity of layout parameters in tournaments and semi-complete digraphs

A simple digraph is semi-complete 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 semi-complete digraphs: cutwidth and optimal linear arrangement (Ola). We prove that: " Both parameters are NP-hard to compute and the known exact and parameterized algorithms for them have essentially optimal running times, assuming the Exponential Time Hypothesis. " The cutwidth parameter admits a quadratic Turing kernel, whereas it does not admit any polyno- mial kernel unless NP † coNP/poly. By contrast, Ola admits a linear kernel. These results essentially complete the complexity analysis of computing cutwidth and Ola on semi- complete digraphs. Our techniques can be also used to analyze the sizes of minimal obstructions for having small cutwidth under the induced subdigraph relation.

Tight Space Bounds for 2-Dimensional Approximate Range Counting

We study the problem of $2$-dimensional orthogonal range counting with additive error. Given a set $P$ of $n$ points drawn from an $n\times n$ grid and an error parameter $\eps$, the goal is to build a data structure, such that for any orthogonal range $R$, it can return the number of points in $P\cap R$ with additive error $\eps n$. A well-known solution for this problem is the {\em $\eps$-approximation}, which is a subset $A\subseteq P$ that can estimate the number of points in $P\cap R$ with the number of points in $A\cap R$. It is known that an $\eps$-approximation of size $O(\frac{1}{\eps} \log^{2.5} \frac{1}{\eps})$ exists for any $P$ with respect to orthogonal ranges, and the best lower bound is $\Omega(\frac{1}{\eps} \log \frac{1}{\eps})$. The $\eps$-approximation is a rather restricted data structure, as we are not allowed to store any information other than the coordinates of the points in $P$. In this paper, we explore what can be achieved without any restriction on the data structure. We first describe a simple data structure that uses $O(\frac{1}{\eps}(\log^2\frac{1} {\eps} + \log n) )$ bits and answers queries with error $\eps n$. We then prove a lower bound that any data structure that answers queries with error $\eps n$ must use $\Omega(\frac{1}{\eps}(\log^2\frac{1} {\eps} + \log n) )$ bits. Our lower bound is information-theoretic: We show that there is a collection of $2^{\Omega(n\log n)}$ point sets with large {\em union combinatorial discrepancy}, and thus are hard to distinguish unless we use $\Omega(n\log n)$ bits.

Subexponential parameterized algorithm for Interval Completion

In the Interval Completion problem we are given an 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 a fundamental graph modifi cation problem with applications in sparse matrix multiplication and molecular biology. The question about fi xed-parameter tractability of Interval Completion was asked by Kaplan, Shamir and Tarjan [FOCS 1994; SIAM J. Comput. 1999] and was answered a rmatively more than a decade later by Villanger at el. [STOC 2007; SIAM J. Comput. 2009], who presented an algorithm with running time O(k^{2k} n^3 m). We give the first subexponential parameterized algorithm solving Interval Completion in time k^O(sqrt(k)) n^O(1). This adds Interval Completion to a very small list of parameterized graph modi fication problems solvable in subexponential time.

Graph Reconstruction and Verification

How efficiently can we find an unknown graph using distance or shortest path queries between its vertices? We assume that the unknown graph G is connected, unweighted, and has bounded degree. In the reconstruction problem, the goal is to find the graph G. In the verification problem, we are given a hypothetical graph $\hat G$ and want to check whether G is equal to $\hat G$. We provide a randomized algorithm for reconstruction using $\tilde O(n^{3/2})$ distance queries, based on Voronoi cell decomposition. Next, we analyze natural greedy algorithms for reconstruction using a shortest path oracle and also for verification using either oracle, and show that their query complexity is $n^{1+o(1)}$. We further improve the query complexity when the graph is chordal or outerplanar. Finally, we show some lower bounds, and consider an approximate version of the reconstruction problem.

Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs

The Weighted Tree Augmentation Problem (WTAP) is a fundamental well-studied problem in the field of network design. Given an undirected tree $G=(V,E)$, an additional set of edges $L \subseteq V\times V$ disjoint from $E$ called \textit{links} and a cost vector $c\in \mathbb{R}_{\geq 0}^L$, WTAP asks to find a minimum-cost set $F\subseteq L$ with the property that $(V,E\cup F)$ is $2$-edge connected. The special case where $c_\ell = 1$ for all $\ell\in L$ is called the Tree Augmentation Problem (TAP). For the class of bounded cost vectors, we present a first improved approximation algorithm for WTAP since more than three decades. Concretely, for any $M\in \mathbb{R}_{\geq 1}$ and $\epsilon > 0$, we present an LP based $(\delta+\epsilon)$-approximation for WTAP restricted to cost vectors $c$ in $[1,M]^L$ for $\delta \approx 1.96417$. More generally, our result is a $(\delta+\epsilon)$-approximation algorithm with running time $n^{r^{O(1)}}$, where $r = c_{\max}/c_{\min}$ is the ratio between the largest and the smallest cost of any link. For the special case of TAP we improve this factor to $\frac{5}{3}+\epsilon$. Our results rely on several new ideas, including a new LP relaxation of WTAP and a two-phase rounding algorithm.

The Dependent Doors Problem: An Investigation into Sequential Decisions without Feedback

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.

Near-Optimal Light Spanners

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 \delta-spanner of G for some parameter \delta\geq 1 if the distance in H between every vertex pair is at most a factor \delta bigger than in G. In this case, we say that H has stretch \delta. Two main measures of the sparseness of a spanner are the size (number of edges) and the total weight (the sum of weights of the edges in the spanner). Recently Elkin, Neiman and Solomon [ICALP 14] presented an improved analysis of the greedy algorithm, proving that the greedy algorithm admits (2k-1) \cdot (1+\eps) stretch and total edge weight of O_{\eps}((k/\log{k}) \cdot \omega(MST(G))\cdot n^{1/k}), where \omega(MST(G)) is the weight of a minimum spanning tree of G. The previous analysis by Chandra \etal [SOCG 92] admitted (2k-1)\cdot (1+\eps) stretch and total edge weight of O_{\eps}(k \omega(MST(G)) n^{1/k}). Hence, Elkin \etal improved the weight of the spanner by a \log{k} factor. In this work, we completely remove the k factor from the weight, presenting a spanner with (2k-1)\cdot (1+\eps) stretch, O_{\eps}(\omega(MST(G)) n^{1/k}) total weight, and O(n^{1+1/k}) edges. Up to a $(1+\eps)$ factor in the stretch this matches the girth conjecture of Erd\H{o}s \cite{Er64}.

Bibliometrics

Publication Years 2005-2018
Publication Count 607
Citation Count 3887
Available for Download 607
Downloads (6 weeks) 1861
Downloads (12 Months) 16445
Downloads (cumulative) 232043
Average downloads per article 382
Average citations per article 6
First Name Last Name Award
Pankaj Agarwal ACM Fellows (2002)
Noga Alon ACM Fellows (2016)
Lars Arge ACM Fellows (2012)
ACM Distinguished Member (2009)
Guy Blelloch ACM Fellows (2011)
Allan Borodin ACM Fellows (2014)
Moses Charikar ACM Paris Kanellakis Theory and Practice Award (2012)
Danny Z Chen ACM Distinguished Member (2014)
ACM Senior Member (2011)
Siu-Wing Cheng ACM Distinguished Member (2017)
Mahdi Cheraghchi ACM Senior Member (2016)
Kenneth Clarkson ACM Fellows (2008)
Edith Cohen ACM Fellows (2017)
Richard J Cole ACM Fellows (1998)
Anne Condon ACM Fellows (2010)
ACM Doctoral Dissertation Award
Series Winner (1988)
Graham R. Cormode ACM Distinguished Member (2013)
Constantinos Daskalakis ACM Doctoral Dissertation Award (2008)
Erik Demaine ACM Fellows (2016)
Xiaotie Deng ACM Fellows (2008)
ACM Senior Member (2006)
Martin Dietzfelbinger ACM Distinguished Member (2011)
David Eppstein ACM Fellows (2011)
Joan Feigenbaum ACM Fellows (2001)
Pedro F Felzenszwalb ACM Grace Murray Hopper Award (2013)
Harold N Gabow ACM Fellows (2002)
Zvi Galil ACM Fellows (1995)
Emden R Gansner ACM Distinguished Member (2016)
Mohsen Ghaffari ACM Doctoral Dissertation Award (2017)
Andrew V Goldberg ACM Fellows (2009)
Michael T Goodrich ACM Fellows (2009)
ACM Distinguished Member (2006)
Ronald L. Graham ACM Fellows (1999)
Martin Grohe ACM Fellows (2017)
Rachid Guerraoui ACM Fellows (2012)
Leonidas Guibas ACM AAAI Allen Newell Award (2007)
ACM Fellows (1999)
Rajesh Gupta ACM Fellows (2016)
Venkatesan Guruswami ACM Fellows (2017)
Venkatesan Guruswami ACM Doctoral Dissertation Award (2002)
Monika Henzinger ACM Fellows (2016)
John Hershberger ACM Fellows (2012)
Piotr Indyk ACM Fellows (2015)
ACM Paris Kanellakis Theory and Practice Award (2012)
David S Johnson ACM Fellows (1995)
Erich L Kaltofen ACM Fellows (2009)
Howard J Karloff ACM Fellows (2011)
Valerie King ACM Fellows (2014)
Philip N Klein ACM Fellows (2010)
Richard E. Ladner ACM Fellows (1995)
Charles E Leiserson ACM-IEEE CS Ken Kennedy Award (2014)
ACM Paris Kanellakis Theory and Practice Award (2013)
ACM Fellows (2006)
ACM Doctoral Dissertation Award (1982)
Carsten Lund ACM Doctoral Dissertation Award
Series Winner (1991) ACM Doctoral Dissertation Award
Series Winner (1991)
Dahlia Malkhi ACM Fellows (2011)
Yishay Mansour ACM Fellows (2014)
Madhav Marathe ACM Fellows (2013)
Kurt Mehlhorn ACM Paris Kanellakis Theory and Practice Award (2010)
ACM Fellows (1999)
Joseph Mitchell ACM Fellows (2011)
Mukesh Mohania ACM Distinguished Member (2011)
Rajeev Motwani ACM Fellows (2007)
Ian Munro ACM Fellows (2008)
S. Muthukrishnan ACM Fellows (2010)
Moni Naor ACM Paris Kanellakis Theory and Practice Award (2016)
Noam Nissan ACM Doctoral Dissertation Award
Series Winner (1990) ACM Doctoral Dissertation Award
Series Winner (1990)
David Peleg ACM Fellows (2016)
Satish Rao ACM Fellows (2013)
Edward M Reingold ACM Fellows (1996)
Omer Reingold ACM Fellows (2014)
ACM Grace Murray Hopper Award (2005)
Micha Sharir ACM Fellows (1997)
David Shmoys ACM Fellows (2001)
Sandeep K Shukla ACM Distinguished Member (2012)
ACM Senior Member (2007)
Aravind Srinivasan ACM Fellows (2014)
Clifford Stein ACM Fellows (2012)
David Steurer ACM Doctoral Dissertation Award
Honorable Mention (2011) ACM Doctoral Dissertation Award
Honorable Mention (2011)
Madhu Sudan ACM Fellows (2008)
ACM Doctoral Dissertation Award (1993)
Subhash Suri ACM Fellows (2010)
ACM Distinguished Member (2007)
Eva Tardos ACM Fellows (1998)
Robert E Tarjan ACM Paris Kanellakis Theory and Practice Award (1999)
ACM Fellows (1994)
ACM A. M. Turing Award (1986)
Mikkel Thorup ACM Fellows (2005)
Eli Upfal ACM Fellows (2005)
Salil P Vadhan ACM Doctoral Dissertation Award (2000)
Jeffrey S Vetter ACM Distinguished Member (2012)
ACM Gordon Bell Prize
Performance (2010)
Jennifer L Welch ACM Distinguished Member (2012)
Emmerich Welzl ACM Fellows (1998)
Peter Widmayer ACM Fellows (1997)
Rebecca N. Wright ACM Distinguished Member (2017)

First Name Last Name Paper Counts
Saket Saurabh 13
Mohammadtaghi Hajiaghayi 12
Dániel Marx 12
Guy Kortsarz 11
Daniel Lokshtanov 11
Robert Tarjan 10
Uri Zwick 9
Pankaj Agarwal 8
Erik Demaine 8
Mikkel Thorup 8
Haim Kaplan 8
Gonzalo Navarro 7
Magnús Halldórsson 7
David Peleg 7
Fedor Fomin 7
Zeev Nutov 7
Samir Khuller 7
Maxim Sviridenko 7
Anupam Gupta 7
Viswanath Nagarajan 6
Andrzej Pelc 6
Ke Yi 6
Venkatesh Raman 6
Moshe Lewenstein 6
Noga Alon 6
Micha Sharir 6
Rohit Khandekar 6
Adi Rosén 5
David Eppstein 5
Chandra Chekuri 5
Kirk Pruhs 5
Hadas Shachnai 5
Joseph Naor 5
Raphael Yuster 5
Inge Gørtz 5
Timothy Chan 5
Graham Cormode 5
Yossi Azar 5
Shay Solomon 5
Philip Klein 5
S Muthukrishnan 5
Michael Elkin 5
Seth Pettie 5
Liam Roditty 5
Sariel Har-Peled 5
Nikhil Bansal 5
Loukas Georgiadis 4
Telikepalli Kavitha 4
Kurt Mehlhorn 4
Glencora Borradaile 4
Dimitrios Thilikos 4
Marek Cygan 4
Bernhard Haeupler 4
Harold Gabow 4
Dana Ron 4
Boris Aronov 4
Ola Svensson 4
Srinivasa Satti 4
Meng He 4
Ashish Goel 4
Oren Weimann 4
M Ramanujan 4
Baruch Schieber 4
T Chan 4
Guy Even 4
Fabrizio Grandoni 4
Chaitanya Swamy 4
Sudipto Guha 4
Amin Saberi 4
Martín Farach-Colton 4
Susanne Albers 4
Paolo Ferragina 4
Ignaz Rutter 4
Asaf Levin 4
Thore Husfeldt 4
Svante Janson 3
Andreas Björklund 3
Andrew McGregor 3
Dror Rawitz 3
Artur Czumaj 3
Michael Bender 3
Alberto Marchetti-Spaccamela 3
Berthold Vöcking 3
Surender Baswana 3
Yuval Emek 3
James Munro 3
Daniel Berend 3
Harald Räcke 3
Stephen Alstrup 3
David Harris 3
Edward Reingold 3
Zachary Friggstad 3
Rob Van Stee 3
Leah Epstein 3
Giuseppe Italiano 3
Amotz Bar-Noy 3
Sanjeev Khanna 3
Julia Chuzhoy 3
Christian Sohler 3
Pat Morin 3
Gabriel Scalosub 3
Shai Gutner 3
George Karakostas 3
Aravind Srinivasan 3
Baruch Awerbuch 3
John Iacono 3
Amos Korman 3
Kenichi Kawarabayashi 3
Wojciech Szpankowski 3
Amol Deshpande 3
Jeff Edmonds 3
Roberto Grossi 3
Laurent Alonso 3
Heiko Röglin 3
Sergio Cabello 3
Anastasios Sidiropoulos 3
Kazuo Iwama 3
Marek Chrobak 3
Hsienkuei Hwang 3
Amit Chakrabarti 3
Rajiv Gandhi 3
Danny Segev 3
Stefan Kratsch 3
Zoya Svitkina 3
David Johnson 3
Allan Borodin 3
Refael Hassin 3
Mohammad Salavatipour 3
Philip Bille 3
Shay Mozes 3
Dimitrios Michail 3
Ramamoorthi Ravi 3
Yonatan Aumann 3
Yuval Rabani 3
Joseph Cheriyan 3
Konstantin Makarychev 3
Rajeev Raman 3
Morteza Zadimoghaddam 3
Lisa Hellerstein 3
Bundit Laekhanukit 2
Thomas Sauerwald 2
Petteri Kaski 2
Amr Elmasry 2
Lisa Fleischer 2
Rina Panigrahy 2
Lisa Zhang 2
Vijaya Ramachandran 2
Veli Mäkinen 2
Moran Feldman 2
Lapchi Lau 2
Pierre Fraigniaud 2
Marcin Pilipczuk 2
Hamid Mahini 2
Subhash Suri 2
James Aspnes 2
Éva Tardos 2
Ioannis Caragiannis 2
Takwah Lam 2
Tami Tamir 2
Anne Driemel 2
Djamal Belazzougui 2
László Végh 2
Adrian Vetta 2
Dilys Thomas 2
An Zhu 2
Julián Mestre 2
Mohammad Mahdian 2
Jiří Sgall 2
Luca Becchetti 2
Dieter Kratsch 2
Bruce Maggs 2
Martin Dietzfelbinger 2
Avinatan Hassidim 2
Geevarghese Philip 2
Thomas Bläsius 2
Dekel Tsur 2
Yoann Dieudonné 2
Suresh Venkatasubramanian 2
Lars Arge 2
Ely Porat 2
Michael Dinitz 2
Vincenzo Bonifaci 2
Alexander Russell 2
Kenneth Clarkson 2
Ramakrishna Thurimella 2
Goran Konjevod 2
Jittat Fakcharoenphol 2
John Hershberger 2
Adam Meyerson 2
Yishay Mansour 2
Joan Feigenbaum 2
Gregory Sorkin 2
Danupon Nanongkai 2
Dariusz Kowalski 2
Holger Dell 2
Cristopher Moore 2
Katarzyna Paluch 2
Jochen Könemann 2
Christoph Ambühl 2
Ravishankar Krishnaswamy 2
Merav Parter 2
Sungjin Im 2
Rossano Venturini 2
Hiroki Yanagisawa 2
Tobias Jacobs 2
Siddhartha Sen 2
Conrado Martínez 2
Alfredo Viola 2
Don Coppersmith 2
Atri Rudra 2
Mohammad Salavatipour 2
Joseph Leung 2
Joe Sawada 2
Peter Korteweg 2
Camil Demetrescu 2
Clifford Stein 2
Joan Boyar 2
HoLeung Chan 2
Kamesh Munagala 2
Venkatesan Guruswami 2
Thomas Erlebach 2
MohammadHossein Bateni 2
Stefan Langerman 2
Irene Finocchi 2
Alex Kesselman 2
Amihood Amir 2
Hans Bodlaender 2
Vijay Kumar 2
Carmit Hazay 2
Shuichi Miyazaki 2
Theis Rauhe 2
Serge Gaspers 2
Monika Henzinger 2
Teofilo Gonzalez 2
Roy Schwartz 2
Jérémy Barbay 2
Milan Ružić 2
Martin Strauss 2
Fahad Panolan 2
Magnus Wahlström 2
Leen Stougie 2
Antoine Vigneron 2
Andréa Richa 2
Claire Mathieu 2
Dimitris Fotakis 2
Hamid Nazerzadeh 2
Yury Makarychev 2
Matthew Andrews 2
Michael Drmota 2
Bodo Manthey 2
Michele Flammini 2
R Sritharan 2
Helmut Prodinger 2
Alexandr Andoni 2
Eduardo Laber 2
Shi Li 2
Siuwing Cheng 2
Konstantinos Panagiotou 2
Yusu Wang 2
Jie Gao 2
Ulrich Meyer 2
MohammadTaghi Hajiaghayi 2
Christophe Paul 2
Petr Kolman 2
Iftah Gamzu 2
Holeung Chan 2
Kunihiko Sadakane 2
Dina Sokol 2
Somnath Sikdar 2
Robert Krauthgamer 2
Ioannis Koutis 2
Jesper Nederlof 2
Piotr Indyk 2
Sándor Fekete 2
Danny Hermelin 2
Jeremy Fineman 2
Benjamin Raichel 2
Angelika Steger 2
Shanghua Teng 2
Jon Feldman 2
Mingyang Kao 2
Mikko Koivisto 2
Ignasi Sau 2
Christos Kaklamanis 2
Klaus Jansen 2
Martin Skutella 2
Martin Aumüller 2
Nicole Megow 2
Łukasz Kowalik 2
Tomás Feder 2
Cyril Gavoille 2
Yuli Ye 2
Seth Gilbert 2
Jarosław Byrka 1
Luca Foschini 1
Piotr Krysta 1
Matthias Függer 1
Jennifer Welch 1
Matt DeVos 1
John Carlsson 1
Leonidas Guibas 1
Louis Ibarra 1
David Ilcinkas 1
Panagiotis Cheilaris 1
Jakub Łącki 1
Dömötör Pálvölgyi 1
Timothy Chan 1
Alex Scott 1
Bogdan Chlebus 1
Moses Charikar 1
Venkatesh Natarajan 1
Yijie Han 1
Phong Nguyêñ 1
Hiroshi Fujiwara 1
Matthew Maxel 1
Michael Krivelevich 1
Eldar Fischer 1
Ying Xu 1
Gruia Călinescu 1
Fabrizio Luccio 1
Xiaotie Deng 1
Juanjo Rué 1
Martin Pál 1
Uriel Feige 1
Sébastien Collette 1
Kristian Lichtenberg 1
David Hay 1
Marcelo De Carvalho 1
Kinsum Mak 1
Claus Jensen 1
Steven Skiena 1
Renato Werneck 1
Xin Chen 1
Sangil Oum 1
Leszek Gąsieniec 1
Manuel Kauers 1
Michael Fuchs 1
Giovanni Manzini 1
Ryan Hayward 1
Ruben Van Der Zwaan 1
Maciej Kurowski 1
Stephen Kobourov 1
Amir Sapir 1
Kobbi Nissim 1
Christina Fragouli 1
Christian Sommer 1
Alexander Kulikov 1
Ramamohan Paturi 1
Hjalte VildhØj 1
Csaba Tóth 1
Ivan Mihajlin 1
Donglin Xia 1
Atlas IV 1
Ekkehard Köhler 1
Mark Petrick 1
George Yuhasz 1
Himanshu Gupta 1
Vitaly Feldman 1
Poshen Loh 1
Joseph Mitchell 1
Valentin Polishchuk 1
Jukka Suomela 1
Ittai Abraham 1
Jelani Nelson 1
Marc Van Kreveld 1
Ran Raz 1
Alexander Langer 1
Michael Kapralov 1
Cristiane Sato 1
David Eppstein 1
Erik Van Leeuwen 1
Shaofeng Jiang 1
Keren Censor 1
Rajesh Chitnis 1
Mohammadamin Fazli 1
Sina Sadeghabad 1
MohammadAli Safari 1
Dannyziyi Chen 1
Jan Kratochvíl 1
Richard Cole 1
Frank Ruskey 1
Shay Kutten 1
Gagan Aggarwal 1
Yusuke Kobayashi 1
Shimon Shahar 1
Hisao Tamaki 1
Hung Yu 1
Mahdi Cheraghchi 1
Vladlen Koltun 1
Gilad Tsur 1
Avner Magen 1
Tomasz Nowicki 1
Karsten Tiemann 1
Thomas Pensyl 1
Robert Ganian 1
Sandeep Sen 1
Justus Schwartz 1
Bojan Mohar 1
Ulrich Faigle 1
Reid Andersen 1
Valerie King 1
Nishanth Chandran 1
Mohammad Safari 1
Jens Vygen 1
Shakhar Smorodinsky 1
Constantinos Daskalakis 1
Thomas Rothvoß 1
Meirav Zehavi 1
Sara Ahmadian 1
Babak Behsaz 1
Pranabendu Misra 1
Yusuke Kobayashi 1
Rohan Fernandes 1
Mihai Bǎdoiu 1
David Fernández-Baca 1
Sebastian Böcker 1
Greg Little 1
Satish Rao 1
Chris Harrelson 1
Oded Lachish 1
Orly Yahalom 1
François Nicolas 1
Bob Sedgewick 1
Francis Chin 1
Alessandro Panconesi 1
Jaikumar Radhakrishnan 1
Nikos Karanikolas 1
Piyush Kurur 1
Balaji Raghavachari 1
Mordecai Golin 1
Julien Clément 1
Pierre Nicodème 1
Guy Louchard 1
Alexey Stepanov 1
Ge Nong 1
M Paal 1
Sivan Toledo 1
Tomasz Radzik 1
Markus Püschel 1
Lene Favrholdt 1
Per Austrin 1
Konstantinos Georgiou 1
Carsten Lund 1
Edith Cohen 1
Nick Duffield 1
Irit Katriel 1
Hu Zhang 1
Alexander Golovnev 1
Ryan Williams 1
Johannes Fischer 1
Erich Kaltofen 1
Stefan Hougardy 1
Micah Adler 1
Alex Levin 1
Frank Staals 1
Martin Hoefer 1
Stéphan Thomassé 1
Stanislav Živný 1
David Kim 1
Prasad Raghavendra 1
Yi Wu 1
Guillaume Moroz 1
Nikhil Devanur 1
Benjamin Aminof 1
Orna Kupferman 1
Jérémie Chalopin 1
Yann Disser 1
Matúš Mihaľák 1
Vít Jelínek 1
Afshin Nikzad 1
T Chan 1
Aaron Williams 1
Krishnaram Kenthapadi 1
Daniel Lemire 1
Gerhard Woeginger 1
Ron Levy 1
Bastian Pochon 1
Hyunchul Lee 1
Christian Glacet 1
Shmuel Safra 1
Martin Gairing 1
Kasturi Varadarajan 1
Axel Bacher 1
Tsunghsi Tsai 1
Michael Etscheid 1
Jiongxin Jin 1
Mankit Lau 1
Niv Buchbinder 1
Steve Oudot 1
Deepak Ajwani 1
Rafail Ostrovsky 1
Takeshi Tokuyama 1
Tim Nieberg 1
Nir Ailon 1
Ademir Hujdurović 1
Martin Milanič 1
Romeo Rizzi 1
Amin Jorati 1
Evangelos Anagnostopoulos 1
Abhinandan Nath 1
Xiaowei Wu 1
Rogers Mathew 1
Siddhartha Sen 1
Jianer Chen 1
Songjian Lu 1
Fenghui Zhang 1
Anke Truß 1
Roberto De Prisco 1
Sandy Irani 1
Tali Kaufman 1
Wojciech Jawor 1
Zohar Yakhini 1
Eric Chen 1
Reinhard Kutzelnigg 1
Petteri Kaski 1
Sharon Marko 1
Xiaotie Deng 1
Anne Condon 1
Christian Knauer 1
Arlindo Oliveira 1
Howard Karloff 1
David Pritchard 1
Shlomo Moran 1
Wingkin Sung 1
Guochuan Zhang 1
Eli Upfal 1
Ulrich Schwarz 1
Friedhelm Heide 1
Amalia Duch 1
Yan Zhang 1
Andrea Ribichini 1
Danny Raz 1
Lapkei Lee 1
Mathieu Liedloff 1
Ioan Todinca 1
Vanbang Le 1
Alessandro Panconesi 1
Gad Landau 1
Jeff Phillips 1
Erel Segal-Halevi 1
Wei Chen 1
Estrella Eisenberg 1
Peter Sanders 1
Ravi Kolluri 1
Srinivasan Parthasarathy 1
Saurabh Ray 1
Aaron Jaggard 1
Jian Li 1
Devorah Kletenik 1
Alexander Wolff 1
Georg Baier 1
Ondřej Pangrác 1
Bernhard Von Stengel 1
Tamás Fleiner 1
Benjamin Moseley 1
Yngve Villanger 1
Ronald Graham 1
Marcelo Mydlarz 1
F Shepherd 1
Assaf Naor 1
Peter Rossmanith 1
Petra Berenbrink 1
Omid Madani 1
Aravindan Vijayaraghavan 1
Omrit Filtser 1
Shayan Ehsani 1
Abbas Mehrabian 1
Morteza Saghafian 1
Peter Widmayer 1
Patrizio Angelini 1
Daniel Panario 1
Matthew Drescher 1
Christos Levcopoulos 1
Retsef Levi 1
Patchrawat Uthaisombut 1
Yongbin Ou 1
Ittai Abraham 1
Noam Nisan 1
Archontia Giannopoulou 1
Keren Cohavi 1
Robert Irving 1
Daniel Rockmore 1
Markus Nebel 1
Josef Widder 1
Stefanie Gerke 1
Christian Wulff-Nilsen 1
Britta Peis 1
Benjamin Armbruster 1
Yinyu Ye 1
Mohammad Hajiaghayi 1
Bruce Kapron 1
David Kempe 1
Jared Saia 1
Paul Medvedev 1
Omkant Pandey 1
Walter Kern 1
Paweł Gawrychowski 1
Edin Husić 1
Fei Chen 1
Singhoi Sze 1
Vladimir Braverman 1
Matteo Frigo 1
Sandeep Shukla 1
Kedar Dhamdhere 1
Anil Maheshwari 1
Renars Gailis 1
Jessica Chang 1
Luís Russo 1
Matthew Katz 1
Eleanor Rieffel 1
Dawn Song 1
Eyal Gordon 1
Ryan Williams 1
Cecilia Procopiuc 1
Rachid Guerraoui 1
Chidambaram Annamalai 1
Jens Gramm 1
Rolf Niedermeier 1
Michael Pinedo 1
Rajsekar Manokaran 1
Martin Wahlén 1
Zvi Galil* 1
Evangelos Kranakis 1
Danny Krizanc 1
Thomas Hansen 1
Sriram Pemmaraju 1
Kashyap Dixit 1
Comandur Seshadhri 1
Mohsen Ghaffari 1
Richard Geary 1
Jeffrey Vitter 1
René Meier 1
Azarakhsh Malekian 1
Sebastian Wild 1
Frederic Dorn 1
Sagi Snir 1
Ari Freund 1
Valentina Ciriani 1
Norbert Zeh 1
Valentina Damerow 1
Raja Jothi 1
Andrea Vitaletti 1
F Bruss 1
Benjamin Rossman 1
Prudence Wong 1
Daniel Golovin 1
László Babai 1
Pedro Felzenszwalb 1
Yochai Twitto 1
Lusheng Wang 1
Éric De Verdière 1
Alexander Schrijver 1
Sambuddha Roy 1
Xiaohui Zhang 1
Amitabh Chaudhary 1
Siavosh Benabbas 1
David Mount 1
Nikos Parotsidis 1
Olaf Maurer 1
Yuval Ishai 1
Łukasz Jeż 1
Jay Sethuraman 1
Satish Rao 1
Arie Koster 1
Daniel Blandford 1
Gilles Schaeffer 1
Nicole Immorlica 1
Vahab Mirrokni 1
Li Ning 1
Madhav Marathe 1
Hoyee Cheung 1
Benjamin Sach 1
Christian Konrad 1
Rahul Garg 1
Alexander Hall 1
Heiko Schilling 1
Michael Spriggs 1
Daming Zhu 1
Richard Ladner 1
Yixin Cao 1
Artur Jež 1
Marcel Ackermann 1
Markus Bläser 1
Jens Maßberg 1
David Shmoys 1
Johanna Seif 1
David Wood 1
Leana Golubchik 1
Yang Liu 1
Ojas Parekh 1
Yoav Giora 1
Sridhar Ramachandran 1
Giuseppe Persiano 1
Rajesh Gupta 1
Jacques Yuster 1
Tomáš Tichý 1
Tom Leighton 1
Robert Kleinberg 1
Gauri Shah 1
Ilan Newman 1
Yoav Katz 1
Vincent Berry 1
Keke Chen 1
Bruno Salvy 1
Yong Zhang 1
Gopal Pandurangan 1
Ning Chen 1
Vida Dujmović 1
Christian Scheideler 1
Till Tantau 1
Serge Plotkin 1
Jacob Holm 1
Wolfgang Bein 1
Frédérique Bassino 1
Joseph Chan 1
Andreas Brandstädt 1
Mark Pedigo 1
Jyrki Katajainen 1
Sundar Vishwanathan 1
Noa Lewenstein 1
Sen Zhang 1
Zheng Liu 1
William Aiello 1
Avraham Ben-Aroya 1
Ralph Neininger 1
Peter Grabner 1
Arnaud Labourel 1
Alon Efrat 1
Felix Reidl 1
Justin Thaler 1
Alon Shalita 1
Annamária Kovács 1
Cenk Sahinalp 1
Shuheng Zhou 1
Nicholas Harvey 1
Huy Nguyeݱn 1
Shantanu Das 1
Giuseppe Di Battista 1
Maurizio Patrignani 1
Yufei Tao 1
Takuro Fukunaga 1
Evangelos Markakis 1
Boaz Patt-Shamir 1
Shuxin Nie 1
Adam Buchsbaum 1
Iam Roditty 1
Herman Haverkort 1
Biingfeng Wang 1
Bart Jansen 1
David Cashman 1
Omer Reingold 1
Shahar Dobzinski 1
James Korsh 1
Yumei Huo 1
Stefan Schmid 1
Rajiv Raman 1
Bartosz Rybicki 1
Olivier Bodini 1
Ankur Gupta 1
Hyungchan An 1
Johannes Blömer 1
Vishal Sanwalani 1
Amit Sahai 1
Spyros Kontogiannis 1
Paul Spirakis 1
Akiko Suzuki 1
Johann Hurink 1
T Jayram 1
Edo Liberty 1
Andreas Schmid 1
Ioannis Psarros 1
Andrew Shallue 1
Maxim Babenko 1
Wuzhou Zhang 1
Theocharis Malamatos 1
Luigi Laura 1
C Subramanian 1
Guy Kortsarz 1
Joachim Giesen 1
Éric Fusy 1
Tal Wagner 1
Wei Hu 1
Ron Adany 1
Elad Haramaty 1
Sanjiv Kapoor 1
Hristo Djidjev 1
Carola Wenk 1
Dan Rubenstein 1
JöRg Thuswaldner 1
Stavros Kolliopoulos 1
Shiri Chechik 1
Eunjung Kim 1
Piotr Berman 1
Pekka Parviainen 1
Zhiyi Huang 1
Stephan Held 1
Rinat Avraham 1
Haitao Wang 1
Guyslain Naves 1
Michael Dom 1
Tobias Friedrich 1
Joachim Gudmundsson 1
Giri Narasimhan 1
Gianni Franceschini 1
Yefim Dinitz 1
Qianping Gu 1
Mark De Berg 1
Alexander Shvartsman 1
Tzuchin Lin 1
Yi Li 1
Aadhar Jain 1
Yossi Richter 1
Dana Moshkovitz 1
Jiong Guo 1
Nina Taslaman 1
Dany Breslauer 1
Chaiwah Wu 1
Sunil Arya 1
Christos Kalaitzis 1
Jerri Nummenpalo 1
Roei Tov 1
Manan Sanghi 1
Balaji Venkatachalam 1
Damien Stehlé 1
Charles Leiserson 1
Harald Prokop 1
Vincenzo Auletta 1
Oren Melamud 1
Andrei Krokhin 1
Günter Rote 1
Asaf Shapira 1
J Munro 1
Paul Bonsma 1
Yoshiharu Kohayakawa 1
Antonios Antoniadis 1
Angelo Fanelli 1
Aaron Archer 1
Florian Diedrich 1
Noam Solomon 1
Michael Goldwasser 1
Emo Welzl 1
Bin Fu 1
Amitabha Bagchi 1
Andrew Goldberg 1
Jeremy Spinrad 1
Christian Duncan 1
Tal Malkin 1
Fei Li 1
Javad Ebrahimi 1
Yajun Wang 1
Avivit Levy 1
David Steurer 1
Dominique Poulalhon 1
Guy Blelloch 1
Kaiman Leung 1
Yoshio Okamoto 1
Tsvi Kopelowitz 1
Adrian Dumitrescu 1
Michael Langberg 1
Panagiotis Kanellopoulos 1
Therese Biedl 1
Eyal Even-Dar 1
Moni Naor 1
Udi Wieder 1
Deeparnab Chakrabarty 1
Madhav Jha 1
George Giakkoupis 1
Khoa Trinh 1
Stefan Szeider 1
David Kirkpatrick 1
Ashkan Norouzi-Fard 1
Bernadette Charron-Bost 1
Piotr Sankowski 1
Yue Wang 1
Tobias Friedrich 1
Ryan Moriarty 1
Alexandru Tomescu 1
Jens Schmidt 1
Pradeesha Ashok 1
Sudeshna Kolay 1
Torsten Mütze 1
Dorit Hochbaum 1
Bruce Reed 1
Robert Schweller 1
Robert Carr 1
Quang Bui 1
Shayan Oveisgharan 1
Paolo Penna 1
Madhu Sudan 1
Ron Pinter 1
Arie Matsliah 1
Toshihiro Fujito 1
Prosenjit Bose 1
Guojun Li 1
Ningning Wu 1
Zdeněk Dvořák 1
Robin Thomas 1
Michèle Soria 1
Brigitte Vallee 1
Alexander Izsak 1
Hingfung Ting 1
Renato Carmo 1
Luca Moscardelli 1
Arash Asadpour 1
Ariel Procaccia 1
Lars Prädel 1
Philippe Baptiste 1
Lawrence Larmore 1
Rami Cohen 1
Christian Scheideler 1
Jianxing Feng 1
Rephael Wenger 1
Katarína Cechlárová 1
Daniel Binkele-Raible 1
Henning Fernau 1
Miklós Ajtai 1
Ariel Levavi 1
Bernd Gärtner 1
Maarten Löffler 1
Mikkel Thorup 1
Martin Grohe 1
Neva Cherniavsky 1
Bruce Bobier 1
Elias Koutsoupias 1
Ayelet Butman 1
Justin Ward 1
Hsinhao Su 1
Karl Wimmer 1
Gorjan Alagic 1
Eric Torng 1
Artem Pyatkin 1
Nira Shafrir 1
Mukesh Mohania 1
Waihong Chan 1
Dany Azriel 1
Lan Liu 1
Stefano Leonardi 1
Wingkai Hon 1
Yevgen Voronenko 1
Huahuai Chern 1
Michael Goodrich 1
Pascal Klaue 1
Elisabeth Lubbecke 1
Rebecca Wright 1
Martin Jaggi 1
Sören Laue 1
Natalie Shapira 1
Amnon Ta-Shma 1
Michael Schapira 1
Barna Saha 1
Gaia Nicosia 1
Leonard Schulman 1
Anna Lubiw 1
Wolfgang Slany 1
Doratha Vinkemeier 1
Jing Wang 1
Linus Hamilton 1
Richard Peng 1
Sumeet Khurana 1
Soumojit Sarkar 1
Sofya Raskhodnikova 1
George Christodoulou 1
Arkadiusz Socała 1
Bryan Wilkinson 1
Gelin Zhou 1
Ofer Neiman 1
Ran Duan 1
Robby Lampert 1
Mihai P&acaron;trascu 1
Wiebke Höhn 1
Noa Avigdor-Elgrabli 1
Tsunghsi Tsai 1
Virginia Vassilevska 1
Elliot Anshelevich 1
Rolf Fagerberg 1
Michiel Smid 1
ChiaChi Yeh 1
Cunquan Zhang 1
Dahlia Malkhi 1
Avery Miller 1
Burkhard Monien 1
Paul LaFollette 1
Rajneesh Hegde 1
Keren Censor-Hillel 1
Yahav Nussbaum 1
William Evans 1
Ran Mendelson 1
Reut Levi 1
Jeff Erickson 1
Virginia Williams 1
Reuven Cohen 1
David Woodruff 1
Friedrich Eisenbrand 1
Alantha Newman 1
Ioannis Emiris 1
Kyle Fox 1
Gramoz Goranci 1
Miguel Mosteiro 1
Mariusz Rokicki 1
Hiro Ito 1
Amin Sayedi-Roshkhar 1
Qin Zhang 1
Sylvain Guillemot 1
Panos Giannopoulos 1
Nicholas Pippenger 1
Xin Han 1
Rajeev Motwani 1
Liadan O'Callaghan 1
Randeep Bhatia 1
Nitish Korula 1
Amit Bhosle 1
Christoph Dürr 1
Vikraman Arvind 1
Mark Ward 1
Konstantin Andreev 1
Charles Garrod 1
Jason McCullough 1
Pranjal Awasthi 1
Yongwook Choi 1
Tao Jiang 1
Venkatesan Chakaravarthy 1
Matthias Englert 1
Andreas Wiese 1
Shuchi Chawla 1
Amitabh Sinha 1
András Benczúr 1
Dorothea Wagner 1
Liam Mencel 1
Barry O'Sullivan 1
Igor Razgon 1
Clemens Heuberger 1
SiuWing Cheng 1
Jurek Czyzowicz 1
Lukáš Poláček 1
Claire Mathieu 1
Ning Chen 1
Funda Ergün 1
Mohammad Khani 1
Marcel Silva 1
Rishi Saket 1
Yuan Zhou 1
Rezaul Chowdhury 1
Sophie Spirkl 1
Saber Fadaee 1
Fabrizio Frati 1
N Narayanaswamy 1
Benjamin Doerr 1
Georgios Amanatidis 1
Sebastian Krinninger 1
Elaine Shi 1
Arturo Gonzalez-Gutierrez 1
Shahar Fattal 1
Owen Kaser 1
Claire Kenyon 1
Emden Gansner 1
Jim Pugh 1
Hsueh Lu 1
Anna Gilbert 1
Charles Tresser 1
Kaimin Chung 1
Salil Vadhan 1
Marco Molinaro 1
Jin Zhang 1
Giuseppe Paleologo 1
Fabian Kuhn 1
Vinayaka Pandit 1

Affiliation Paper Counts
University of Bristol 1
California State University Northridge 1
Sun Yat-Sen University 1
Italian National Research Council 1
State University of New York College at Oneonta 1
Johannes Kepler University Linz 1
University of Durham 1
Meiji University 1
Medical University of South Carolina 1
National Taiwan Ocean University 1
University of California, Santa Cruz 1
Shanghai Jiaotong University 1
University College Cork 1
University of Tokyo 1
Rensselaer Polytechnic Institute 1
Indian Institute of Technology, Madras 1
Netanya Academic College 1
Lawrence Livermore National Laboratory 1
Microsoft Corporation 1
University of Melbourne 1
DePaul University 1
Stevens Institute of Technology 1
Kwansei Gakuin University 1
Institute for Advanced Studies 1
University of Illinois at Chicago 1
Oracle Corporation 1
University of Quebec in Montreal 1
Sant'Anna School of Advanced Studies 1
University of Eastern Piedmont Amedeo Avogadro, Alessandria 1
University of Leoben 1
Siemens AG 1
Ludwig Maximilian University of Munich 1
University of Miami 1
Commonwealth Scientific and Industrial Research Organization 1
The University of Georgia 1
Wesleyan University Middletown 1
Cisco Systems 1
University of Milan 1
Pavol Jozef safarik University in Kosice 1
California Institute of Technology 1
Utah State University 1
Michigan State University 1
Korea Advanced Institute of Science & Technology 1
University of Wisconsin Madison 1
University of Verona 1
University of Electro-Communications 1
Alexandria University 1
Sobolev Institute of Mathematics of Siberian Branch of the RAS 1
Google Switzerland GmbH 1
Amazon.com, Inc. 1
NEC Deutschland GmbH 1
Istituto di Scienza e Tecnologie dell'Informazione A. Faedo 1
ORT Braude - College of Engineering 1
Microsoft Research Cambridge 1
Microsoft Research India 1
VMware, Inc 1
Universite Grenoble Alpes 1
Laboratoire d'Analyse et Modelisation de Systemes pour l'Aide a la Decision 1
CSIRO Data61 1
Leonard N. Stern School of Business 1
SRI International 1
Harvey Mudd College 1
Emory University 1
Universite Pierre et Marie Curie 1
University of Glasgow 1
University of Stellenbosch 1
Center for Communications Research 1
National Technical University of Athens 1
Toyohashi University of Technology 1
Vanderbilt University 1
Zhejiang University 1
IBM Tokyo Research Laboratory 1
NASA Ames Research Center 1
Iowa State University 1
Dalian University of Technology 1
University of G. d'Annunzio Chieti and Pescara 1
J. Craig Venter Institute 1
Ecole Normale Superieure de Lyon 1
Los Alamos National Laboratory 1
University of Western Macedonia 1
National Institutes of Health, Bethesda 1
The University of North Carolina at Charlotte 1
University of Missouri-Kansas City 1
International Institute of Information Technology Bangalore 1
Sandia National Laboratories, New Mexico 1
Laboratoire d'Informatique, de Robotique et de Microelectronique de Montpellier LIRMM 1
Malmo University 1
University of Sao Paulo 1
CNRS Centre National de la Recherche Scientifique 1
Vrije Universiteit Amsterdam 1
Hong Kong Polytechnic University 1
Birkbeck University of London 1
University of California , Merced 1
Linkoping University 1
University of Colorado at Denver 1
Apple Computer 1
Kyushu University 1
Illinois Wesleyan University 1
BRICS Basic Research in Computer Science 1
National Chiao Tung University Taiwan 1
Lubeck University 1
Duquesne University 1
Indian Institute of Technology, Bombay 1
University of Tsukuba 1
Hong Kong Baptist University 1
University of California, Davis 1
Dalle Molle Institute for Artificial Intelligence 1
Federal University of Parana 1
Imperial College London 1
Florida International University 1
University of Witwatersrand 1
Yonsei University 1
Holon Institute of Technology 1
University of New Brunswick 1
University of Tubingen 1
Aegean University 1
George Mason University 1
Maastricht University 1
Boston University 1
University of Wisconsin Milwaukee 1
Saint Petersburg Department of Steklov Institute of Mathematics, Russian Academy of Sciences 1
Brandenburg University of Technology Cottbus 1
National Research University Higher School of Economics, Moscow 1
Hewlett-Packard Inc. 1
University of Texas at San Antonio 2
University of Rostock 2
Mentor Graphics Corporation 2
North Carolina State University 2
Instituto Superior Tecnico 2
National Taiwan University 2
University of Primorska 2
Technical University in Braunschweig 2
Tohoku University 2
University of Dayton 2
University of Kaiserslautern 2
University of Arizona 2
King's College London 2
Center for Mathematics and Computer Science - Amsterdam 2
University of Trier 2
City University of Hong Kong 2
University of Denver 2
University of Guelph 2
Universite de Picardie Jules Verne 2
University of L'Aquila 2
Athens University of Economics and Business 2
Graz University of Technology 2
Royal Holloway University of London 2
West Virginia University 2
University of Notre Dame 2
Kasetsart University 2
Georgetown University 2
University of Iowa 2
Universite Paris-Sud XI 2
Eotvos Lorand University 2
IBM Haifa Labs 2
University of Oxford 2
Universite Paul Verlaine - Metz 2
St. Louis University 2
Universite d'Orleans 2
Temple University 2
Free University of Berlin 2
University of Cambridge 2
Tata Institute of Fundamental Research 2
University of Nevada, Las Vegas 2
Universite de Caen Basse Normandie 2
Pontifical Catholic University of Rio de Janeiro 2
Indian Institute of Technology, Delhi 2
Saarland University 2
University of Puerto Rico 2
Universidad de la Republica 2
Microsoft Research Asia 2
Ecole Normale Superieure 3
Pennsylvania State University 3
Royal Institute of Technology 3
University of Helsinki 3
Ohio State University 3
Uppsala University 3
Goethe University Frankfurt 3
University of Texas at Dallas 3
Universite Paris 13 3
Harvard University 3
University of Texas-Pan American 3
IBM Research 3
The Interdisciplinary Center Herzliya 3
University of Texas at Austin 3
INRIA Institut National de Rechereche en Informatique et en Automatique 3
Oregon State University 3
Ecole Polytechnique 3
Seoul National University 3
Dalhousie University 3
National University of Singapore 3
University of Connecticut 3
New Jersey Institute of Technology 3
Brooklyn College 3
Tsinghua University 3
University of Utah 3
University of Freiburg 3
University of Sydney 3
Laboratoire d'Informatique de l'Ecole Polytechnique 3
University of Chicago 3
University of Aarhus 3
Shandong University 3
University of Ljubljana 3
Academy of Sciences of the Czech Republic (Avcr.Cz) 3
York University Canada 3
University of Iceland 3
Toyota Technological Institute at Chicago 3
King Abdullah University of Science and Technology 3
Universite de Bordeaux 3
Aix Marseille Universite 3
Aalto University 3
University of Colorado at Boulder 4
Helsinki Institute for Information Technology 4
University of Michigan 4
Chinese University of Hong Kong 4
London School of Economics and Political Science 4
University of Victoria 4
IBM India Research Laboratory 4
Arizona State University 4
University of Ioannina 4
Johns Hopkins University 4
Yale University 4
Nanyang Technological University 4
City University of New York 4
University of Salerno 4
Northwestern University 4
Universitat Politecnica de Catalunya 4
Roma Tre University 4
Indian Institute of Science, Bangalore 4
INRIA Lorraine 4
National Tsing Hua University 4
University of Southern Denmark 4
Georgia Institute of Technology 4
Texas A and M University 4
University of Twente 4
Virginia Tech 4
Research Organization of Information and Systems National Institute of Informatics 4
University of Southern California 4
Karlsruhe Institute of Technology, Campus South 4
Budapest University of Technology and Economics 4
University at Buffalo, State University of New York 4
TU Dortmund University 4
University of New Mexico 4
Intertrust Technologies Corporation 4
University of Montpellier 4
Illinois Institute of Technology 5
Purdue University 5
University of Kiel 5
AT&T Inc. 5
University of Massachusetts Amherst 5
University of Washington, Seattle 5
Academia Sinica Taiwan 5
Nokia Bell Labs 5
Indian Institute of Technology, Kanpur 5
Computer and Automation Research Institute Hungarian Academy of Sciences 5
Hungarian Academy of Sciences 5
University of California, Riverside 5
McMaster University 5
Reykjavik University 5
Universite Libre de Bruxelles 6
Humboldt University of Berlin 6
MIT Computer Science and Artificial Intelligence Laboratory 6
Cornell University 6
The University of British Columbia 6
Dartmouth College 6
Kyoto University 6
University of Pittsburgh 6
Charles University 6
Simon Fraser University 6
IT University of Copenhagen 6
New York University 6
University of Vienna 6
Technical University of Ilmenau 6
Columbia University 6
University of California, San Diego 6
Karlsruhe Institute of Technology 6
Utrecht University 7
IBM Almaden Research Center 7
University of Wroclaw 7
University of Roma Tor Vergata 7
University of Athens 7
University of California, Santa Barbara 7
University of Patras 7
University of Leicester 7
Yahoo Research Labs 7
McGill University 8
University of California, Irvine 8
Technical University of Denmark 8
Carleton University 8
University of Quebec in Outaouais 8
University of Liverpool 8
Open University of Israel 8
Stony Brook University 8
University of California, Los Angeles 8
Sharif University of Technology 8
University of Copenhagen 8
NYU Tandon School of Engineering 8
University of Illinois at Urbana-Champaign 9
University of Illinois 9
University of Pennsylvania 9
University of Bonn 9
Hebrew University of Jerusalem 9
Vienna University of Technology 9
University of Paderborn 9
The University of Warwick 9
Lund University 9
Friedrich Schiller University Jena 9
Rutgers, The State University of New Jersey 9
Universite Paris 7- Denis Diderot 10
Universidad de Chile 10
RWTH Aachen University 10
University of Toronto 10
University of California, Berkeley 10
University Michigan Ann Arbor 10
University of Pisa 10
Brown University 11
University of Warsaw 11
Swiss Federal Institute of Technology, Zurich 11
Princeton University 13
Duke University 13
Eindhoven University of Technology 13
Hong Kong University of Science and Technology 14
Technical University of Berlin 14
University of Alberta 14
Rutgers University-Camden campus 15
Swiss Federal Institute of Technology, Lausanne 15
University of Roma La Sapienza 15
University of Haifa 18
AT&T Laboratories Florham Park 18
IBM Thomas J. Watson Research Center 18
Google Inc. 19
Microsoft Research 19
The University of Hong Kong 20
Institute of Mathematical Sciences India 20
Stanford University 23
Weizmann Institute of Science Israel 23
Max Planck Institute for Informatics 26
Ben-Gurion University of the Negev 26
Bar-Ilan University 27
Massachusetts Institute of Technology 27
University of Maryland 28
University of Bergen 28
Carnegie Mellon University 29
Technion - Israel Institute of Technology 33
University of Waterloo 36
Tel Aviv University 75

ACM Transactions on Algorithms (TALG)
Archive


2018
Volume 14 Issue 2, May 2018  Issue-in-Progress
Volume 14 Issue 1, January 2018

2017
Volume 13 Issue 4, December 2017
Volume 13 Issue 3, August 2017
Volume 13 Issue 2, May 2017 Special Issue on SODA'15 and Regular Papers

2016
Volume 13 Issue 1, December 2016
Volume 12 Issue 4, September 2016
Volume 12 Issue 3, June 2016
Volume 12 Issue 2, February 2016
Volume 12 Issue 1, February 2016 Special Issue on SODA'12 and Regular Papers

2015
Volume 11 Issue 4, June 2015
Volume 11 Issue 3, January 2015

2014
Volume 11 Issue 2, November 2014
Volume 11 Issue 1, October 2014
Volume 10 Issue 4, August 2014
Volume 10 Issue 3, June 2014
Volume 10 Issue 2, February 2014
Volume 10 Issue 1, January 2014

2013
Volume 9 Issue 4, September 2013
Volume 9 Issue 3, June 2013 Special Issue on SODA'11
Volume 9 Issue 2, March 2013

2012
Volume 9 Issue 1, December 2012
Volume 8 Issue 4, September 2012
Volume 8 Issue 3, July 2012
Volume 8 Issue 2, April 2012
Volume 8 Issue 1, January 2012

2011
Volume 7 Issue 4, September 2011
Volume 7 Issue 3, July 2011
Volume 7 Issue 2, March 2011

2010
Volume 7 Issue 1, November 2010
Volume 6 Issue 4, August 2010
Volume 6 Issue 3, June 2010
Volume 6 Issue 2, March 2010

2009
Volume 6 Issue 1, December 2009
Volume 5 Issue 4, October 2009
Volume 5 Issue 3, July 2009
Volume 5 Issue 2, March 2009

2008
Volume 5 Issue 1, November 2008
Volume 4 Issue 4, August 2008
Volume 4 Issue 3, June 2008
Volume 4 Issue 2, May 2008
Volume 4 Issue 1, March 2008

2007
Volume 3 Issue 4, November 2007
Volume 3 Issue 3, August 2007
Volume 3 Issue 2, May 2007
Volume 3 Issue 1, February 2007

2006
Volume 2 Issue 4, October 2006
Volume 2 Issue 3, July 2006
Volume 2 Issue 2, April 2006
Volume 2 Issue 1, January 2006

2005
Volume 1 Issue 2, October 2005
Volume 1 Issue 1, July 2005
 
All ACM Journals | See Full Journal Index

Search TALG
enter search term and/or author name