ACM Transactions on

Algorithms (TALG)

Latest Articles

The Parametric Closure Problem

We define the parametric closure problem, in which the input is a partially ordered set whose elements have linearly varying weights and the goal is to compute the sequence of minimum-weight downsets of the partial order as the weights vary. We give polynomial time solutions to many important special cases of this problem including semiorders,... (more)

Independence and Efficient Domination on P6-free Graphs

In the Maximum Weight Independent Set problem, the input is a graph G, every vertex has a non-negative integer weight, and the task is to find a set S... (more)

Kernels for (Connected) Dominating Set on Graphs with Excluded Topological Minors

Linear Time Parameterized Algorithms for Subset Feedback Vertex Set


In Memoriam: David S. Johnson

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

Selection and Sorting in the "Restore" Model

We consider the classical selection and sorting problems in a model where the initial permutation of the input has to be restored after completing the computation. While the requirement of the restoration is stringent compared to the classical versions of the problems, this model is more relaxed than a read-only memory (ROM) where the input elements are not allowed to be moved within the input array. We fi rst show that for a sequence of n integers, selection ( finding the median or more generally the k-th smallest element for a given k) can be done in O(n) time using O(lg n) words. In contrast, no linear-time selection algorithm is known which uses polylogarithmic space in ROM. For sorting n integers in this model, we fi rst present an O(n lg n)-time algorithm using O(lg n) words. When the universe size U is polynomial in n, we give a faster O(n)-time algorithm (analogous to radix sort) which uses O(n^eps) words of extra space for an arbitrarily small constant eps > 0. More generally, we show how to match the time bound of any word-RAM integer-sorting algorithms using O(n^eps) words of extra space. In sharp contrast, there is an (n^2/S)-time lower bound for integer sorting using O(S) space in ROM. For indivisible input elements, we prove the same lower bound for sorting in our model. En route, we develop linear-time in-place algorithms to extract leading bits of the input and to compress and decompress strings with low entropy.

Improved Deterministic Algorithms for Linear Programming in Low Dimensions

Chazelle and Matou\v sek [\emph{J. Algorithms}, 1996] presented a derandomization of Clarkson's sampling-based algorithm [\emph{J. ACM}, 1995] for solving linear programs with $n$ constraints and $d$ variables in $d^{(7+o(1))d}n$ deterministic time. The time bound can be improved to $d^{(5+o(1))d}n$ with subsequent work by Br\"onnimann, Chazelle, and Matou\v sek [\emph{SIAM J. Comput.}, 1999]. We first point out a much simpler derandomization of Clarkson's algorithm that avoids $\eps$-approximations and runs in $d^{(3+o(1))d}n$ time. We then describe a few additional ideas that eventually improve the deterministic time bound to $d^{(1/2+o(1))d}n$.

CoveringLSH: Locality-sensitive Hashing without False Negatives

We consider a new construction of locality-sensitive hash functions for Hamming space that is covering in the sense that is it guaranteed to produce a collision for every pair of vectors within a given radius r. The construction is efficient in the sense that the expected number of hash collisions between vectors at distance cr, for a given c>1, comes close to that of the best possible data independent LSH without the covering guarantee, namely, the seminal LSH construction of Indyk and Motwani (STOC '98). The efficiency of the new construction essentially matches their bound when the search radius is not too large --- e.g., when cr = o(log(n)/log log n), where n is the number of points in the data set, and when cr = log(n)/k where k is an integer constant. In general, it differs by at most a factor ln(4) in the exponent of the time bounds. As a consequence, LSH-based similarity search in Hamming space can avoid the problem of false negatives at little or no cost in efficiency.

Approximation Algorithms for Minimum-Load k-Facility Location

We consider the minimum-load k-facility location (MLKFL) problem: give a set F of facilities, a set C of clients, and an integer k\geq 0, and a distance function d(f,j). The goal is to open a set F'\subseteq F of k facilities, and assign each client j to a facility f(j)\in F so as to minimize \max_{f\in F}\sum_{j\in C:f(j)=f}d(f,j). This problem was studied under the name of min-max star cover in {EGK+03,AHL06}, who gave bicriteria approximation algorithms for when F=C. MLKFL is rather poorly understood, and only an $O(k)$-approximation is currently known even for line metrics. Our main result is a PTAS for MLKFL on line metrics. Complementing this, we prove that MLKFL is strongly NP-hard on line metrics. We also devise a QPTAS for it on tree metrics. MLKFL turns out to be surprisingly challenging even on line metrics; we show that: (a) even a configuration-style LP has a bad integrality gap; and (b) a multi-swap local-search heuristic has a bad locality gap. Our PTAS for line metrics consists of two main ingredients. First, we prove existence of a near-optimal solution possessing some nice properties. A novel aspect of this proof is that we first move to a mixed-integer LP (MILP), and argue that a MILP-solution minimizing a certain potential function possesses the desired structure, and then use a rounding algorithm for the generalized-assignment problem to ``transfer'' this structure to the rounded integer solution. We then show how to find a solution having these structural properties using DP.

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|

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.

Efficient computation of middle levels Gray codes

For any integer $n\geq 1$ a \emph{middle levels Gray code} is a cyclic listing of all bitstrings of length $2n+1$ that have either $n$ or $n+1$ entries equal to 1 such that any two consecutive bitstrings in the list differ in exactly one bit. The question whether such a Gray code exists for every $n\geq 1$ has been the subject of intensive research during the last 30 years, and has been answered affirmatively only recently [T.~Mütze. Proof of the middle levels conjecture. \textit{arXiv:1404.4442}, 2014]. In this work we provide the first efficient algorithm to compute a middle levels Gray code. For a given bitstring, our algorithm computes the next $\ell$ bitstrings in the Gray code in time $\cO(n\ell(1+\frac{n}{\ell}))$, which is $\cO(n)$ on average per bitstring provided that $\ell=\Omega(n)$.

Deterministic Truncation of Linear Matroids

Let $M=(E, \mathcal{I})$ be a matroid of rank $n$. A {\em $k$-truncation} of $M$ is a matroid {$M'=(E,{\mathcal I}')$} such that for any $A\subseteq E$, $A\in {\mathcal2 I}'$ if and only if $|A|\leq k$ and $A\in \I$. Given a linear representation, $A$, of $M$ we consider the problem of finding a linear representation, $A_k$, of the $k$-truncation of $M$. A common way to compute $A_k$ is to multiply the matrix $A$ with a random $k\times n$ matrix, yielding a simple randomized algorithm. So a natural question is whether we can compute $A_k$ {\em deterministically}. In this paper we settle this question for matrices over any field in which the field operations can be done efficiently. This includes any finite field and the field of rational numbers ($\mathbb Q$). Our algorithms are based on the properties of the classical Wronskian determinant, and the folded Wronskian determinant, which was recently introduced by Guruswami and Kopparty~[\,{\em FOCS, 2013; COMBINATORICA 2016}\,], and Forbes and Shpilka~[\,{\em STOC, 2012}\,]. Our main conceptual contribution in this paper is to show that the Wronskian determinant can also be used to obtain a representation of the truncation of a linear matroid in deterministic polynomial time. Finally, we use our results to derandomize several parameterized algorithms, including an algorithm for computing {\sc $\ell$-Matroid Parity}, to which several problems, such as {\sc $\ell$-Matroid Intersection}, can be reduced.

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

Randomized embeddings with slack, and high-dimensional Approximate Nearest Neighbor

The approximate nearest neighbor problem ($\epsilon$-ANN) in high dimensional Euclidean space has been mainly addressed by Locality Sensitive Hashing (LSH), which has polynomial dependence in the dimension, sublinear query time, but subquadratic space requirement. In this paper, we introduce a new definition of ``low-quality'' embeddings for metric spaces. It requires that, for some query point $q$, there exists an approximate nearest neighbor among the pre-images of the $k>1$ approximate nearest neighbors in the target space. Focusing on Euclidean spaces, we employ random projections in order to reduce the original problem to one in a space of dimension inversely proportional to $k$. The $k$ approximate nearest neighbors can be efficiently retrieved by a data structure such as BBD-trees. The same approach is applied to the problem of computing an approximate near neighbor, where we obtain a data structure requiring linear space, and query time in $O(d n^{\rho})$, for $\rho\approx 1-\epsilon^2/\log(1/\epsilon)$. This directly implies a solution for $\epsilon$-ANN, while achieving a better exponent in the query time than the method based on BBD-trees. Better bounds are obtained in the case of doubling subsets of $\ell_2$, by combining our method with $r$-nets. We implement our method in C++, and present experimental results in dimension up to $500$ and $10^6$ points, which show that performance is better than predicted by the analysis. In addition, we compare our ANN approach to E2LSH, which implements LSH, and we show that the theoretical advantages of each method are reflected on their actual performance.

Incremental Exact Min-Cut in Poly-logarithmic Amortized Update Time

We present a deterministic incremental algorithm for \textit{exactly} maintaining the size of a minimum cut with $\widetilde{O}(1)$ amortized time per edge insertion and $O(1)$ query time. This result partially answers an open question posed by Thorup [Combinatorica 2007]. It also stays in sharp contrast to a polynomial conditional lower-bound for the fully-dynamic weighted minimum cut problem. Our algorithm is obtained by combining a recent sparsification technique of Kawarabayashi and Thorup [STOC 2015] and an exact incremental algorithm of Henzinger [J. of Algorithm 1997]. We also study space-efficient incremental algorithms for the minimum cut problem. Concretely, we show that there exists an ${O}(n\log n/\varepsilon^2)$ space Monte-Carlo algorithm that can process a stream of edge insertions starting from an empty graph, and with high probability, the algorithm maintains a $(1+\varepsilon)$-approximation to the minimum cut. The algorithm has $\widetilde{O}(1)$ amortized update-time and constant query-time.

Computing 2-Walks in Polynomial Time

A 2-walk of a graph is a walk visiting every vertex at least once and at most twice. By generalizing decompositions of Tutte and Thomassen, Gao, Richter and Yu proved that every 3-connected planar graph contains a closed 2-walk such that all vertices visited twice are contained in 3-separators. This seminal result generalizes Tutte's theorem that every 4-connected planar graph is Hamiltonian as well as Barnette's theorem that every 3-connected planar graph has a spanning tree with maximum degree at most 3. The algorithmic challenge of finding such a closed 2-walk is to overcome big overlapping subgraphs in the decomposition, which are also inherent in Tutte's and Thomassen's decompositions. We solve this problem by extending the decomposition of Gao, Richter and Yu in such a way that all pieces, in which the graph is decomposed into, are edge-disjoint. This implies the first polynomial-time algorithm that computes the closed 2-walk mentioned above.

Distributed Online and Stochastic Queuing on a Multiple Access Channel

We consider the problems of online and stochastic packet queuing in a distributed system of n nodes with queues, where the communication between the nodes is done via a multiple access channel. In the online setting, in each round, an arbitrary number of packets can be injected into the system, each to an arbitrary node's queue. Two measures of performance are considered: the total number of packets in the system, called the total load, and the maximum queue size, called the maximum load. We develop a deterministic distributed algorithm that is asymptotically optimal with respect to both complexity measures, in a competitive way. More precisely, the total load of our algorithm is bigger than the total load of any other algorithm, including centralized online solutions, by only an additive term of O(n^2), while the maximum queue size of our algorithm is at most n times bigger than the maximum queue size of any other algorithm, with an extra additive O(n). The optimality for both measures is justified by proving the corresponding lower bounds, which also separates nearly exponentially distributed solutions from the centralized ones. Next, we show that our algorithm is also stochastically stable for any expected injection rate smaller or equal to 1. This is the first solution to the stochastic queuing problem on a multiple access channel that achieves such stability for the (highest possible) rate equal to 1.

Perfect phylogenies via branchings in acyclic digraphs and a generalization of Dilworth's theorem

Motivated by applications in cancer genomics and following the work of Hajirasouliha and Raphael (WABI 2014), Hujdurovi et al. (IEEE TCBB, to appear) introduced the minimum conflict-free row split (MCRS) problem: split each row of a given binary matrix into a bitwise OR of a set of rows so that the resulting matrix corresponds to a perfect phylogeny and has the minimum possible number of rows among all matrices with this property. Hajirasouliha and Raphael also proposed the study of a similar problem, in which the task is to minimize the number of distinct rows of the resulting matrix. Hujdurovi et al. proved that both problems are NP-hard, gave a related characterization of transitively orientable graphs, and proposed a polynomial-time heuristic algorithm for the MCRS problem based on coloring cocomparability graphs. We give new, more transparent formulations of the two problems, showing that the problems are equivalent to two optimization problems on branchings in a derived directed acyclic graph. Building on these formulations, we obtain new results on the two problems, including: (i) a strengthening of the heuristic by Hujdurovi et al. via a new min-max result in digraphs generalizing Dilworth's theorem, which may be of independent interest, (ii) APX-hardness results for both problems, (iii) approximation algorithms, and (iv) exponential-time algorithms solving the two problems to optimality faster than the naïve brute-force approach. Our work relates to several well studied notions in combinatorial optimization: chain partitions in partially ordered sets, laminar hypergraphs, and (classical and weighted) colorings of graphs.

Exact Algorithms for Terrain Guarding

Given a 1.5-dimensional terrain $T$, also known as an $x$-monotone polygonal chain, the {\sc Terrain Guarding} problem seeks a set of points of minimum size on $T$ that {\em guards} all of the points on $T$. Here, we say that a point $p$ guards a point $q$ if no point of the line segment $\overline{pq}$ is strictly below $T$. The {\sc Terrain Guarding} problem has been extensively studied for over 20 years. In 2005 it was already established that this problem admits a constant-factor approximation algorithm [SODA 2005]. However, only in 2010 King and Krohn [SODA 2010] finally showed that {\sc Terrain Guarding} is NP-hard. In spite of the remarkable developments in approximation algorithms for {\sc Terrain Guarding}, next to nothing is known about its parameterized complexity. In particular, the most intriguing open questions in this direction ask whether it admits a subexponential-time algorithm and whether it is fixed-parameter tractable. In this paper, we answer the first question affirmatively by developing an $n^{O(\sqrt{k})}$-time algorithm for both {\sc Discrete Terrain Guarding} and {\sc Continuous Terrain Guarding}. We also make non-trivial progress with respect to the second question: we show that {\sc Discrete Orthogonal Terrain Guarding}, a well-studied special case of {\sc Terrain Guarding}, is fixed-parameter tractable.

Known Algorithms on Graphs of Bounded Treewidth are Probably Optimal

We obtain a number of lower bounds on the running time of algorithms solving problems on graphs of bounded treewidth. We prove the results under the Strong Exponential Time Hypothesis of Impagliazzo and Paturi. In particular, assuming that SAT cannot be solved in (2-\epsilon)^{n}m^{O(1)} time, we show that for any e > 0; {\sc Independent Set} cannot be solved in (2-e)^{tw(G)}|V(G)|^{O(1)} time, {\sc Dominating Set} cannot be solved in (3-e)^{tw(G)}|V(G)|^{O(1)} time, {\sc Max Cut} cannot be solved in (2-e)^{tw(G)}|V(G)|^{O(1)} time, {\sc Odd Cycle Transversal} cannot be solved in (3-e)^{tw(G)}|V(G)|^{O(1)} time, For any qe 3, q-{\sc Coloring} cannot be solved in (q-e)^{tw(G)}|V(G)|^{O(1)} time, {\sc Partition Into Triangles} cannot be solved in (2-e)^{tw(G)}|V(G)|^{O(1)} time. Our lower bounds match the running times for the best known algorithms for the problems, up to the e in the base.

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.

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.

Analyzing Node-Weighted Oblivious Matching Problem via Continuous LP with Jump Discontinuity

We prove the first non-trivial performance ratio strictly above 0.5 for the weighted Ranking algorithm on the oblivious matching problem where nodes in a general graph can have arbitrary weights. We have discovered a new structural property of the ranking algorithm: if a node has two unmatched neighbors, then it will still be matched even when its rank is demoted to the bottom. This property allows us to form LP constraints for both the weighted and the unweighted versions of the problem. Using a new class of continuous LP, we prove that the ratio for the weighted case is at least 0.501512, and improve the ratio for the unweighted case to 0.526823 (from the previous best 0.523166 in SODA 2014). Unlike previous continuous LP in which the primal solution must be continuous everywhere, our new continuous LP framework allows the monotone component of the primal function to have jump discontinuities, and the other primal components to take non-conventional forms such as the Dirac delta function.

The Alternating Stock Size Problem and the Gasoline Puzzle

Given a set S of integers whose sum is zero, consider the problem of finding a permutation of these integers such that: (i) all prefixes of the ordering are non-negative, and (ii) the maximum value of a prefix sum is minimized. Kellerer et al. referred to this problem as the stock size problem and showed that it can be approximated to within 3/2. They also showed that an approximation ratio of 2 can be achieved via several simple algorithms. We consider a related problem, which we call the alternating stock size problem, where the numbers of positive and negative integers in the input set S are equal. The problem is the same as above, but we are additionally required to alternate the positive and negative numbers in the output ordering. This problem also has several simple 2-approximations. We show that it can be approximated to within 1.79. Then we show that this problem is closely related to an optimization version of the gasoline puzzle due to Lovasz, in which we want to minimize the size of the gas tank necessary to go around the track. We present a 2-approximation for this problem, using a natural linear programming relaxation whose feasible solutions are doubly stochastic matrices. Our novel rounding algorithm is based on a transformation that yields another doubly stochastic matrix with special properties, from which we can extract a suitable permutation.

Computing the Gromov-Hausdorff Distance for Metric Trees

The Gromov-Hausdorff (GH) distance is a natural way to measure distance between two metric spaces. We prove that it is NP-hard to approximate the Gromov-Hausdorff distance better than a factor of 3 for geodesic metrics on a pair of trees. We complement this result by providing a polynomial time O(min{n, (rn)})-approximation algorithm for computing the GH distance between a pair of metric trees, where r is the ratio of the longest edge length in both trees to the shortest edge length. For metric trees with unit length edges, this yields an O(n)-approximation algorithm.


Publication Years 2005-2018
Publication Count 593
Citation Count 3876
Available for Download 593
Downloads (6 weeks) 1984
Downloads (12 Months) 16545
Downloads (cumulative) 228164
Average downloads per article 385
Average citations per article 7
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 S 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)
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 J 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
Mohammadtaghi Hajiaghayi 12
Guy Kortsarz 11
Dániel Marx 11
Robert Tarjan 10
Saket Saurabh 10
Daniel Lokshtanov 9
Uri Zwick 9
Erik Demaine 8
Haim Kaplan 8
Gonzalo Navarro 7
Magnús Halldórsson 7
Pankaj Agarwal 7
David Peleg 7
Mikkel Thorup 7
Zeev Nutov 7
Samir Khuller 7
Maxim Sviridenko 7
Anupam Gupta 7
Ke Yi 6
Rohit Khandekar 6
Fedor Fomin 6
Andrzej Pelc 6
Moshe Lewenstein 6
Micha Sharir 6
Viswanath Nagarajan 6
Noga Alon 6
Adi Rosén 5
David Eppstein 5
Chandra Chekuri 5
Kirk Pruhs 5
Hadas Shachnai 5
Raphael Yuster 5
Joseph Naor 5
Inge Gørtz 5
Timothy Chan 5
Venkatesh Raman 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
Nikhil Bansal 5
Sariel Har-Peled 5
Thore Husfeldt 4
Telikepalli Kavitha 4
Glencora Borradaile 4
Loukas Georgiadis 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
Guy Even 4
Fabrizio Grandoni 4
Sudipto Guha 4
Amin Saberi 4
Martín Farach-Colton 4
Susanne Albers 4
Paolo Ferragina 4
Ignaz Rutter 4
Asaf Levin 4
Kurt Mehlhorn 4
Andreas Björklund 3
Svante Janson 3
Andrew McGregor 3
Dror Rawitz 3
Artur Czumaj 3
Michael Bender 3
Alberto Marchetti-Spaccamela 3
Surender Baswana 3
Berthold Vöcking 3
Yuval Emek 3
Daniel Berend 3
Harald Räcke 3
Stephen Alstrup 3
David Harris 3
Edward Reingold 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
George Karakostas 3
Shai Gutner 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
Sergio Cabello 3
Kazuo Iwama 3
Marek Chrobak 3
T Chan 3
Hsienkuei Hwang 3
Amit Chakrabarti 3
Rajiv Gandhi 3
Stefan Kratsch 3
Danny Segev 3
Zoya Svitkina 3
Chaitanya Swamy 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
Carmit Hazay 2
Bundit Laekhanukit 2
Thomas Sauerwald 2
Petteri Kaski 2
Amr Elmasry 2
Lisa Fleischer 2
Rina Panigrahy 2
An Zhu 2
Vijaya Ramachandran 2
Lisa Zhang 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
Anne Driemel 2
Tami Tamir 2
Djamal Belazzougui 2
László Végh 2
Adrian Vetta 2
Cyril Gavoille 2
Yuli Ye 2
Seth Gilbert 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
Yoann Dieudonné 2
Dekel Tsur 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
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
Sungjin Im 2
Merav Parter 2
Rossano Venturini 2
Hiroki Yanagisawa 2
James Munro 2
Tobias Jacobs 2
Siddhartha Sen 2
Alfredo Viola 2
Conrado Martínez 2
Don Coppersmith 2
Atri Rudra 2
Zachary Friggstad 2
Joe Sawada 2
Joseph Leung 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
Vijay Kumar 2
Hans Bodlaender 2
Adam Meyerson 2
Yishay Mansour 2
Joan Feigenbaum 2
Shuichi Miyazaki 2
Theis Rauhe 2
Serge Gaspers 2
Teofilo Gonzalez 2
Roy Schwartz 2
Jérémy Barbay 2
Milan Ružić 2
Martin Strauss 2
Magnus Wahlström 2
Andréa Richa 2
Antoine Vigneron 2
Leen Stougie 2
Claire Mathieu 2
Dimitris Fotakis 2
Yury Makarychev 2
Hamid Nazerzadeh 2
Matthew Andrews 2
Michael Drmota 2
Bodo Manthey 2
Michele Flammini 2
R Sritharan 2
Helmut Prodinger 2
Alexandr Andoni 2
Dilys Thomas 2
Eduardo Laber 2
Shi Li 2
Siuwing Cheng 2
Konstantinos Panagiotou 2
Jie Gao 2
Ulrich Meyer 2
MohammadTaghi Hajiaghayi 2
Christophe Paul 2
Petr Kolman 2
Holeung Chan 2
Iftah Gamzu 2
Kunihiko Sadakane 2
Dina Sokol 2
Robert Krauthgamer 2
Somnath Sikdar 2
Ioannis Koutis 2
Jesper Nederlof 2
Piotr Indyk 2
Danny Hermelin 2
Sándor Fekete 2
Jeremy Fineman 2
Benjamin Raichel 2
Heiko Röglin 2
Angelika Steger 2
Shanghua Teng 2
Jon Feldman 2
Anastasios Sidiropoulos 2
Mingyang Kao 2
Mikko Koivisto 2
Ignasi Sau 2
Christos Kaklamanis 2
Klaus Jansen 2
Martin Skutella 2
Nicole Megow 2
Martin Aumüller 2
Łukasz Kowalik 2
Tomás Feder 2
Himanshu Gupta 1
Jelani Nelson 1
Poshen Loh 1
Joseph Mitchell 1
Valentin Polishchuk 1
Jukka Suomela 1
Ittai Abraham 1
Marc Van Kreveld 1
Ran Raz 1
Vitaly Feldman 1
Alexander Langer 1
Michael Kapralov 1
Keren Censor 1
Cristiane Sato 1
Rajesh Chitnis 1
Mohammadamin Fazli 1
Sina Sadeghabad 1
Dannyziyi Chen 1
MohammadAli Safari 1
Jan Kratochvíl 1
Richard Cole 1
Frank Ruskey 1
Shay Kutten 1
Gagan Aggarwal 1
Shimon Shahar 1
Hisao Tamaki 1
Hung Yu 1
Mahdi Cheraghchi 1
Vladlen Koltun 1
Gilad Tsur 1
Avner Magen 1
Karsten Tiemann 1
Tomasz Nowicki 1
Thomas Pensyl 1
Robert Ganian 1
Sandeep Sen 1
Justus Schwartz 1
Ulrich Faigle 1
Bojan Mohar 1
Reid Andersen 1
Valerie King 1
Nishanth Chandran 1
Mohammad Safari 1
Jens Vygen 1
Shakhar Smorodinsky 1
Mihai Bǎdoiu 1
Constantinos Daskalakis 1
Thomas Rothvoß 1
Yusuke Kobayashi 1
David Fernández-Baca 1
Sebastian Böcker 1
Rohan Fernandes 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
Nikos Karanikolas 1
Alessandro Panconesi 1
Jaikumar Radhakrishnan 1
Balaji Raghavachari 1
Piyush Kurur 1
Julien Clément 1
Pierre Nicodème 1
Mordecai Golin 1
Guy Louchard 1
Alexey Stepanov 1
Ge Nong 1
Sivan Toledo 1
Tomasz Radzik 1
Markus Püschel 1
M Paal 1
Lene Favrholdt 1
Per Austrin 1
Konstantinos Georgiou 1
Edith Cohen 1
Nick Duffield 1
Carsten Lund 1
Hu Zhang 1
Irit Katriel 1
Alexander Golovnev 1
Ryan Williams 1
Johannes Fischer 1
Erich Kaltofen 1
Nikhil Devanur 1
Stefan Hougardy 1
Micah Adler 1
Alex Levin 1
Martin Hoefer 1
Benjamin Aminof 1
Orna Kupferman 1
Stéphan Thomassé 1
David Kim 1
Stanislav Živný 1
Yi Wu 1
Prasad Raghavendra 1
Guillaume Moroz 1
Matúš Mihaľák 1
Jérémie Chalopin 1
Yann Disser 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
Jiongxin Jin 1
Mankit Lau 1
Michael Etscheid 1
Niv Buchbinder 1
Steve Oudot 1
Deepak Ajwani 1
Rafail Ostrovsky 1
Takeshi Tokuyama 1
Tim Nieberg 1
Nir Ailon 1
Rogers Mathew 1
Siddhartha Sen 1
Jianer Chen 1
Songjian Lu 1
Fenghui Zhang 1
Anke Truß 1
Roberto De Prisco 1
Frank Staals 1
Sandy Irani 1
Wojciech Jawor 1
Tali Kaufman 1
Eric Chen 1
Zohar Yakhini 1
Reinhard Kutzelnigg 1
Petteri Kaski 1
Xiaotie Deng 1
Sharon Marko 1
Anne Condon 1
Christian Knauer 1
Arlindo Oliveira 1
Shlomo Moran 1
Wingkin Sung 1
David Pritchard 1
Howard Karloff 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
Mathieu Liedloff 1
Ioan Todinca 1
Lapkei Lee 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
Aaron Jaggard 1
Saurabh Ray 1
Srinivasan Parthasarathy 1
Jian Li 1
Devorah Kletenik 1
Alexander Wolff 1
Georg Baier 1
Ondřej Pangrác 1
Bernhard Von Stengel 1
Marcelo Mydlarz 1
F Shepherd 1
Assaf Naor 1
Tamás Fleiner 1
Benjamin Moseley 1
Yngve Villanger 1
Ronald Graham 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
Yongbin Ou 1
Retsef Levi 1
Patchrawat Uthaisombut 1
Ittai Abraham 1
Noam Nisan 1
Keren Cohavi 1
Archontia Giannopoulou 1
Daniel Rockmore 1
Robert Irving 1
Markus Nebel 1
Josef Widder 1
Christian Wulff-Nilsen 1
Stefanie Gerke 1
Britta Peis 1
Yinyu Ye 1
Benjamin Armbruster 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
Singhoi Sze 1
Vladimir Braverman 1
Matteo Frigo 1
Kedar Dhamdhere 1
Sandeep Shukla 1
Anil Maheshwari 1
Renars Gailis 1
Jessica Chang 1
Luís Russo 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
László Babai 1
Pedro Felzenszwalb 1
Benjamin Rossman 1
Prudence Wong 1
Daniel Golovin 1
Yochai Twitto 1
Sambuddha Roy 1
Lusheng Wang 1
Éric De Verdière 1
Alexander Schrijver 1
Xiaohui Zhang 1
Amitabh Chaudhary 1
David Mount 1
Siavosh Benabbas 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
Hoyee Cheung 1
Nicole Immorlica 1
Vahab Mirrokni 1
Li Ning 1
Madhav Marathe 1
Christian Konrad 1
Benjamin Sach 1
Rahul Garg 1
Alexander Hall 1
Heiko Schilling 1
Michael Spriggs 1
Daming Zhu 1
Richard Ladner 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
Monika Henzinger 1
Boaz Patt-Shamir 1
Adam Buchsbaum 1
Shuxin Nie 1
Herman Haverkort 1
Biingfeng Wang 1
Iam Roditty 1
Bart Jansen 1
Shahar Dobzinski 1
Stefan Schmid 1
Fahad Panolan 1
James Korsh 1
Yumei Huo 1
David Cashman 1
Omer Reingold 1
Rajiv Raman 1
Hyungchan An 1
Bartosz Rybicki 1
Olivier Bodini 1
Ankur Gupta 1
Johannes Blömer 1
Vishal Sanwalani 1
Spyros Kontogiannis 1
Paul Spirakis 1
Amit Sahai 1
Akiko Suzuki 1
T Jayram 1
Johann Hurink 1
Edo Liberty 1
Balaji Venkatachalam 1
Roei Tov 1
Manan Sanghi 1
Damien Stehlé 1
Charles Leiserson 1
Harald Prokop 1
Vincenzo Auletta 1
Oren Melamud 1
Andrei Krokhin 1
Günter Rote 1
Paul Bonsma 1
Asaf Shapira 1
J Munro 1
Yoshiharu Kohayakawa 1
Aaron Archer 1
Antonios Antoniadis 1
Angelo Fanelli 1
Florian Diedrich 1
Noam Solomon 1
Emo Welzl 1
Michael Goldwasser 1
Bin Fu 1
Amitabha Bagchi 1
Jeremy Spinrad 1
Andrew Goldberg 1
Christian Duncan 1
Tal Malkin 1
Fei Li 1
Yajun Wang 1
Javad Ebrahimi 1
Avivit Levy 1
David Steurer 1
Dominique Poulalhon 1
Kaiman Leung 1
Guy Blelloch 1
Yoshio Okamoto 1
Tsvi Kopelowitz 1
Adrian Dumitrescu 1
Michael Langberg 1
Panagiotis Kanellopoulos 1
Therese Biedl 1
Matthew Katz 1
Eleanor Rieffel 1
Dawn Song 1
Ryan Williams 1
Eyal Gordon 1
Cecilia Procopiuc 1
Rachid Guerraoui 1
Chidambaram Annamalai 1
Rajsekar Manokaran 1
Zvi Galil* 1
Jens Gramm 1
Rolf Niedermeier 1
Michael Pinedo 1
Martin Wahlén 1
Thomas Hansen 1
Evangelos Kranakis 1
Danny Krizanc 1
Azarakhsh Malekian 1
Sriram Pemmaraju 1
Mohsen Ghaffari 1
Kashyap Dixit 1
Comandur Seshadhri 1
Richard Geary 1
Jeffrey Vitter 1
René Meier 1
Sebastian Wild 1
Ralph Neininger 1
Yixin Cao 1
Artur Jež 1
Marcel Ackermann 1
David Shmoys 1
Jens Maßberg 1
Markus Bläser 1
Leana Golubchik 1
Yang Liu 1
David Wood 1
Sridhar Ramachandran 1
Ojas Parekh 1
Yoav Giora 1
Giuseppe Persiano 1
Bernd Gärtner 1
Hsinhao Su 1
Eyal Even-Dar 1
Moni Naor 1
Udi Wieder 1
Jianxing Feng 1
Rephael Wenger 1
Katarína Cechlárová 1
Henning Fernau 1
Ariel Levavi 1
Maarten Löffler 1
Mikkel Thorup 1
Neva Cherniavsky 1
Daniel Binkele-Raible 1
Miklós Ajtai 1
Martin Grohe 1
Bruce Bobier 1
Elias Koutsoupias 1
Karl Wimmer 1
Ayelet Butman 1
Justin Ward 1
Jacques Yuster 1
Tomáš Tichý 1
Rajesh Gupta 1
Tom Leighton 1
Robert Kleinberg 1
Gauri Shah 1
Vincent Berry 1
Ilan Newman 1
Keke Chen 1
Yoav Katz 1
Bruno Salvy 1
Yong Zhang 1
Gopal Pandurangan 1
Ning Chen 1
Vida Dujmović 1
Christian Scheideler 1
Till Tantau 1
Frédérique Bassino 1
Serge Plotkin 1
Jacob Holm 1
Wolfgang Bein 1
Joseph Chan 1
Andreas Brandstädt 1
Zheng Liu 1
Jyrki Katajainen 1
Sundar Vishwanathan 1
Mark Pedigo 1
William Aiello 1
Noa Lewenstein 1
Sen Zhang 1
Avraham Ben-Aroya 1
Sunil Arya 1
Theocharis Malamatos 1
Andrew Shallue 1
Luigi Laura 1
Maxim Babenko 1
Wuzhou Zhang 1
Tal Wagner 1
C Subramanian 1
Guy Kortsarz 1
Joachim Giesen 1
Éric Fusy 1
Wei Hu 1
Ron Adany 1
Elad Haramaty 1
Sanjiv Kapoor 1
Carola Wenk 1
Hristo Djidjev 1
Stephan Held 1
Zhiyi Huang 1
Dan Rubenstein 1
JöRg Thuswaldner 1
Shiri Chechik 1
Piotr Berman 1
Stavros Kolliopoulos 1
Eunjung Kim 1
Pekka Parviainen 1
Rinat Avraham 1
Haitao Wang 1
Michael Dom 1
Guyslain Naves 1
Tobias Friedrich 1
Joachim Gudmundsson 1
Giri Narasimhan 1
Gianni Franceschini 1
Mark De Berg 1
Yefim Dinitz 1
Alexander Shvartsman 1
Qianping Gu 1
Tzuchin Lin 1
Yi Li 1
Aadhar Jain 1
Mohammad Salavatipour 1
Dany Breslauer 1
Christian Scheideler 1
Christos Kalaitzis 1
Yossi Richter 1
Dana Moshkovitz 1
Jiong Guo 1
Nina Taslaman 1
Chaiwah Wu 1
Ashkan Norouzi-Fard 1
Deeparnab Chakrabarty 1
George Giakkoupis 1
Madhav Jha 1
Khoa Trinh 1
Stefan Szeider 1
David Kirkpatrick 1
Bernadette Charron-Bost 1
Piotr Sankowski 1
Yue Wang 1
Tobias Friedrich 1
Ryan Moriarty 1
Dorit Hochbaum 1
Robert Schweller 1
Bruce Reed 1
Quang Bui 1
Robert Carr 1
Shayan Oveisgharan 1
Paolo Penna 1
Madhu Sudan 1
Prosenjit Bose 1
Ron Pinter 1
Arie Matsliah 1
Toshihiro Fujito 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
Arash Asadpour 1
Philippe Baptiste 1
Ariel Procaccia 1
Luca Moscardelli 1
Lars Prädel 1
Rolf Fagerberg 1
Lawrence Larmore 1
Rami Cohen 1
Dany Azriel 1
Gorjan Alagic 1
Lan Liu 1
Eric Torng 1
Artem Pyatkin 1
Nira Shafrir 1
Mukesh Mohania 1
Waihong Chan 1
Yevgen Voronenko 1
Huahuai Chern 1
Wingkai Hon 1
Stefano Leonardi 1
Michael Goodrich 1
Elisabeth Lubbecke 1
Pascal Klaue 1
Rebecca Wright 1
Martin Jaggi 1
Sören Laue 1
Natalie Shapira 1
Michael Schapira 1
Amnon Ta-Shma 1
Barna Saha 1
Gaia Nicosia 1
Leonard Schulman 1
Anna Lubiw 1
Ran Duan 1
Wolfgang Slany 1
Doratha Vinkemeier 1
Sumeet Khurana 1
Soumojit Sarkar 1
Linus Hamilton 1
Richard Peng 1
Sofya Raskhodnikova 1
Jing Wang 1
Robby Lampert 1
George Christodoulou 1
Arkadiusz Socała 1
Bryan Wilkinson 1
Gelin Zhou 1
Mihai P&acaron;trascu 1
Ofer Neiman 1
Wiebke Höhn 1
Noa Avigdor-Elgrabli 1
Tsunghsi Tsai 1
Virginia Vassilevska 1
Elliot Anshelevich 1
Michiel Smid 1
Cunquan Zhang 1
ChiaChi Yeh 1
Dahlia Malkhi 1
Avery Miller 1
Paul LaFollette 1
Rajneesh Hegde 1
Burkhard Monien 1
Keren Censor-Hillel 1
Yahav Nussbaum 1
Ran Mendelson 1
William Evans 1
Reut Levi 1
Virginia Williams 1
Jeff Erickson 1
Reuven Cohen 1
David Woodruff 1
Friedrich Eisenbrand 1
Mariusz Rokicki 1
Miguel Mosteiro 1
Hiro Ito 1
Amin Sayedi-Roshkhar 1
Qin Zhang 1
Sylvain Guillemot 1
Panos Giannopoulos 1
Xin Han 1
Nicholas Pippenger 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
Tao Jiang 1
Jason McCullough 1
Venkatesan Chakaravarthy 1
Vinayaka Pandit 1
Pranjal Awasthi 1
Yongwook Choi 1
Matthias Englert 1
Andreas Wiese 1
Shuchi Chawla 1
András Benczúr 1
Amitabh Sinha 1
Liam Mencel 1
Dorothea Wagner 1
Barry O'Sullivan 1
Igor Razgon 1
Sophie Spirkl 1
Rezaul Chowdhury 1
Clemens Heuberger 1
SiuWing Cheng 1
Jurek Czyzowicz 1
Lukáš Poláček 1
Ning Chen 1
Claire Mathieu 1
Funda Ergün 1
Mohammad Khani 1
Marcel Silva 1
Rishi Saket 1
Yuan Zhou 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
Jin Zhang 1
Kaimin Chung 1
Salil Vadhan 1
Giuseppe Paleologo 1
Charles Tresser 1
Marco Molinaro 1
Fabian Kuhn 1
Jarosław Byrka 1
Luca Foschini 1
Piotr Krysta 1
Jennifer Welch 1
Matthias Függer 1
Matt DeVos 1
John Carlsson 1
Yusu Wang 1
Leonidas Guibas 1
Louis Ibarra 1
David Ilcinkas 1
Panagiotis Cheilaris 1
Jakub Łącki 1
Dömötör Pálvölgyi 1
Bogdan Chlebus 1
Moses Charikar 1
Alex Scott 1
Phong Nguyêñ 1
Venkatesh Natarajan 1
Yijie Han 1
Hiroshi Fujiwara 1
Michael Krivelevich 1
Matthew Maxel 1
Eldar Fischer 1
Ying Xu 1
Gruia Călinescu 1
Martin Pál 1
Uriel Feige 1
Fabrizio Luccio 1
Xiaotie Deng 1
Juanjo Rué 1
Sébastien Collette 1
Marcelo De Carvalho 1
Kristian Lichtenberg 1
David Hay 1
Kinsum Mak 1
Xin Chen 1
Claus Jensen 1
Steven Skiena 1
Sangil Oum 1
Renato Werneck 1
Leszek Gąsieniec 1
Michael Fuchs 1
Manuel Kauers 1
Giovanni Manzini 1
Ryan Hayward 1
Yusuke Kobayashi 1
Ruben Van Der Zwaan 1
Maciej Kurowski 1
Stephen Kobourov 1
Amir Sapir 1
Kobbi Nissim 1
Christian Sommer 1
Christina Fragouli 1
Alexander Kulikov 1
Ivan Mihajlin 1
Ramamohan Paturi 1
Hjalte VildhØj 1
Csaba Tóth 1
Atlas IV 1
Ekkehard Köhler 1
Donglin Xia 1
Mark Petrick 1
Erik Van Leeuwen 1
George Yuhasz 1
David Eppstein 1
Shaofeng Jiang 1

Affiliation Paper Counts
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
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 Electro-Communications 1
Alexandria University 1
Sobolev Institute of Mathematics of Siberian Branch of the RAS 1
Google Switzerland GmbH 1, 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
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
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
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 Bristol 1
California State University Northridge 1
University of Texas at San Antonio 2
Ohio State University 2
University of Rostock 2
Mentor Graphics Corporation 2
North Carolina State University 2
Instituto Superior Tecnico 2
National Taiwan University 2
Technical University in Braunschweig 2
Tohoku University 2
University of Dayton 2
University of Texas at Dallas 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
Helsinki Institute for Information Technology 3
Pennsylvania State University 3
Royal Institute of Technology 3
University of Helsinki 3
London School of Economics and Political Science 3
Uppsala University 3
Goethe University Frankfurt 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
University of Michigan 4
Chinese University of Hong Kong 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
Computer and Automation Research Institute Hungarian Academy of Sciences 4
University of Vienna 4
Virginia Tech 4
University of Athens 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
Hungarian Academy of Sciences 5
University of California, Riverside 5
Technical University of Ilmenau 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
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 California, Santa Barbara 7
University of Copenhagen 7
University of Patras 7
University of Leicester 7
Yahoo Research Labs 7
McGill University 8
University of Illinois 8
University of California, Irvine 8
University of Bonn 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
NYU Tandon School of Engineering 8
University of Illinois at Urbana-Champaign 9
University of Pennsylvania 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
Swiss Federal Institute of Technology, Zurich 10
University of Pisa 10
University of Alberta 10
Duke University 11
Brown University 11
University of Warsaw 11
Eindhoven University of Technology 12
Princeton University 13
Technical University of Berlin 13
Hong Kong University of Science and Technology 14
Rutgers University-Camden campus 15
Swiss Federal Institute of Technology, Lausanne 15
University of Roma La Sapienza 15
Institute of Mathematical Sciences India 17
University of Haifa 18
The University of Hong Kong 18
AT&T Laboratories Florham Park 18
IBM Thomas J. Watson Research Center 18
Google Inc. 19
Microsoft Research 19
University of Bergen 22
Stanford University 23
Weizmann Institute of Science Israel 23
Max Planck Institute for Informatics 25
Ben-Gurion University of the Negev 25
Bar-Ilan University 27
Massachusetts Institute of Technology 27
University of Maryland 28
Carnegie Mellon University 29
University of Waterloo 33
Technion - Israel Institute of Technology 33
Tel Aviv University 75

ACM Transactions on Algorithms (TALG)

Volume 14 Issue 1, January 2018

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

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

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

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

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

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

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

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

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

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

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

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

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