ACM DL

ACM Transactions on

Algorithms (TALG)

Menu
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)

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
Scaling Algorithms for Weighted Matching in General Graphs

We present a new scaling algorithm for maximum (or minimum) weight perfect matching on general, edge weighted graphs. Our algorithm runs in $O(m\sqrt{n}\log(nN))$ time, $O(m\sqrt{n})$ per scale, which matches the running time of the best cardinality matching algorithms on sparse graphs. Here $m,n,$ and $N$ bound the number of edges, vertices, and magnitude of any integer edge weight. Our result improves on a 25-year old algorithm of Gabow and Tarjan, which runs in $O(m\sqrt{n\log n\alpha(m,n)} \log(nN))$ time.

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.

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

Cache-oblivious Buffer Heap and Cache-efficient Computation of Shortest Paths in Graphs

We present the buffer heap, a cache-oblivious priority queue that supports Delete-Min, Delete and a hybrid Insert/Decrease-Key operation in $\Oh{\frac{1}{B}\log_{2}{\frac{N}{M}}}$ amortized cache-misses, where $M$ and $B$ are the (unknown) cache-size and block-size, respectively, and $N$ is the number of elements in the queue. We introduce the notion of a slim data structure which captures the situation when only a limited portion of the cache which we call a slim cache, is available to the data structure to retain data between data structural operations. We show that a buffer heap automatically adapts to such an environment and supports all operations in $\Oh{\frac{1}{\lam}+\frac{1}{B}\log_{2}{\frac{N}{\lam}}}$ amortized cache-misses each when the slim cache size is $\lam$. Our results provide substantial improvements over known trivial cache performance bounds for cache-oblivious priority queues with Decrease-Keys. Using the buffer heap we present cache-oblivious implementations of Dijkstra's SSSP algorithm for undirected and directed graphs with non-negative real edge-weights. On a graph with $n$ vertices and $m$ edges, our algorithm for the undirected case incurs $\Oh{n+\frac{m}{B}\log_{2}{\frac{n}{M}}}$ cache-misses and for the directed case causes $\Oh{\left(n+\frac{m}{B}\right)\cdot\log_{2}{\frac{n}{B}}}$ cache-misses. These results give the first non-trivial cache-oblivious bounds for the SSSP problem on general graphs. For the APSP problem on weighted undirected graphs, we incorporate slim buffer heaps into multi-buffer-heaps and use these to improve the cache-aware cache complexity. We also present a simple cache-oblivious APSP algorithm for unweighted undirected graphs that incurs $O(\frac{mn}{B}\log_{M/B}\frac{n}{B})$ cache-misses. This matches the cache-aware bound and is a substantial improvement over the previous cache oblivious bound for the problem.

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.

Fault Tolerant Approximate BFS Structures

This paper addresses the problem of designing a {\em fault-tolerant} $(\alpha, \beta)$ approximate BFS structure (or {\em FT-ABFS structure} for short), namely, a subgraph $H$ of the network $G$ such that subsequent to the failure of some subset $F$ of edges or vertices, the surviving part %$H'$ of $H$ still contains an \emph{approximate} BFS spanning tree for (the surviving part of) $G$, satisfying $\dist(s,v,H\setminus F) \leq \alpha \cdot \dist(s,v,G\setminus F)+\beta$ for every $v \in V$. In SODA'14, we considered {\em multiplicative} $(\alpha,0)$ FT-ABFS structures resilient to a failure of a \emph{single} edge and presented an algorithm that given an $n$-vertex unweighted undirected graph $G$ and a source $s$ constructs a $(3,0)$ FT-ABFS structure rooted at $s$ with at most $4n$ edges (improving by an $O(\log n)$ factor on the near-tight result of \cite{BS10} for the special case of edge failures). Assuming at most $f$ edge failures, for constant integer $f>1$, we prove that there exists a (poly-time constructible) $(3(f+1), (f+1) \log n)$ FT-ABFS structure with $O(f n)$ edges. %%resilient to the failure of up to $f$ edges. We then consider {\em additive} $(1,\beta)$ FT-ABFS structures and demonstrate an interesting dichotomy between multiplicative and additive spanners. In contrast to the linear size of $(\alpha,0)$ FT-ABFS structures, we show that for every $\beta \in [1, O(\log n)]$ there exists an $n$-vertex graph $G$ with a source $s$ for which any $(1,\beta)$ FT-ABFS structure rooted at $s$ has $\Omega(n^{1+\epsilon(\beta)})$ edges, for some function $\epsilon(\beta) \in (0,1)$.

Sublinear-Time Maintenance of Breadth-First Spanning Trees in Partially Dynamic Networks

We study the problem of maintaining a breadth-first spanning tree (BFS tree) in partially dynamic distributed networks modeling a sequence of either failures or additions of communication links (but not both). We show deterministic (1+[)-approximation algorithms whose amortized time (over some number of link changes) is sublinear in D, the maximum diameter of the network. Our technique also leads to a deterministic (1+[)-approximate incremental algorithm for single-source shortest paths (SSSP) in the sequential (usual RAM) model. Prior to our work, the state of the art was the classic exact algorithm of Even and Shiloach [1981] that is optimal under some assumptions [Roditty and Zwick 2011; Henzinger et al. 2015]. Our result is the first to show that, in the incremental setting, this bound can be beaten in certain cases if a small approximation is allowed.

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.

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

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.

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.

Primal Dual Gives Almost Optimal Energy Efficient Online Algorithms

We consider the problem of online scheduling of jobs on unrelated machines with dynamic speed scaling to minimize the sum of energy and weighted flow time. We give an algorithm with an almost optimal competitive ratio for arbitrary power functions. (No earlier results handled arbitrary power functions for unrelated machines.) For power functions of the form f(s) = s^± for some constant ± > 1, we get a competitive ratio of O(±/log ±), improving upon a previous competitive ratio of O(±^2) by [Anand et al. 2012], along with a matching lower bound of ©(±/log ±). Further, in the resource augmentation model, with a 1+µ speed up, we give a 2(1/µ+1) competitive algorithm, with essentially the same techniques, improving the bound of 1 + O(1/µ^2) by [Gupta et al. 2010] and matching the bound of [Anand et al. 2012] for the special case of fixed speed unrelated machines. Unlike the previous results most of which used an amortized local competitiveness argument or dual fitting methods, we use a primal-dual method, which is useful not only to analyze the algorithms but also to design the algorithm itself.

Distributed Private Data Analysis: Lower Bounds and Practical Constructions

We consider a distributed private data analysis setting, where multiple parties each hold some sensitive data; and they wish to run a protocol to learn some aggregate statistics over the distributed dataset, while protecting each user's privacy. As an initial effort, we consider a distributed summation problem. We first show a lower bound, i.e., under information-theoretic differential privacy, any multi-party protocol with a small number of messages must have large additive error. We then show that by adopting a computational differential privacy notion, one can circumvent this lower-bound, and design practical protocols for the periodic distributed summation problem. Our construction has several desirable features. First, it works in the client-server model, and requires no peer-to-peer communication among the clients. Second, our protocol is fault tolerant, and can output meaningful statistics even when a subset of the participants fail to respond. Our constructions guarantee the privacy of honest parties even when a fraction of the participants may be compromised and colluding. In addition, we propose a new distributed noise addition mechanism that guarantees small total error.

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.

Reducing Curse of Dimensionality: Improved PTAS for TSP (with Neighborhoods) in Doubling Metrics

We consider the Traveling Salesman Problem with Neighborhoods (TSPN) in doubling metrics. The goal is to find a shortest tour that visits each of a given collection of subsets (regions or neighborhoods) in the underlying metric space. We give a randomized polynomial time approximation scheme (PTAS) when the regions are fat weakly disjoint. This notion of regions was first defined when a QPTAS was given for the problem in [SODA 2010: Chan and Elbassioni]. We combine the techniques in the previous work, together with the recent PTAS for TSP [STOC 2012: Bartal, Gottlieb and Krauthgamer] to achieve a PTAS for TSPN. However, several non-trivial technical hurdles need to be overcome for applying the PTAS framework to TSPN. (1) Heuristic to detect sparse instances. In the STOC 2012 paper, a minimum spanning tree heuristic is used to estimate the portion of an optimal tour within some ball. However, for TSPN, it is not known if an optimal tour would use points inside the ball to visit regions that intersect the ball. (2) Partially cut regions in the recursion. After a sparse ball is identified by the heuristic, the PTAS framework for TSP uses dynamic program to solve the instance restricted to the sparse ball, and recursively solve the remaining instance. However, for TSPN, it is an important issue to decide whether each region partially intersecting the sparse ball should be solved in the sparse instance or considered in the remaining instance.

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

We give the first linear kernels for Dominating Set and Connected Dominating Set problems on graphs excluding a fixed graph $H$ as a topological minor. Our results extend the known classes of graphs on which Dominating Set and Connected Dominating Set problems admit linear kernels. Prior to our work, it was known that these problems admit linear kernels on graphs excluding a fixed apex graph $H$ as a minor. Moreover, for Dominating Set, a kernel of size $k^{c(H)}$, where $c(H)$ is a constant depending on the size of $H$, follows from a more general result on the kernelization of Dominating Set on graphs of bounded degeneracy. Alon and Gutner asked explicitly, whether one can obtain a linear kernel for Dominating Set on $H$-minor free, graphs. We answer this question in affirmative and in fact prove a more general result. Our kernelization algorithm is based on a non-trivial combination of the following ingredients (a) the structural theorem of Grohe and Marx [STOC 2012] for graphs excluding a fixed graph $H$ as a topological subgraph; (b) A novel notion of protrusions, different that the one defined in [FOCS 2009]; and (c) Our results are based on a generic reduction rule producing an equivalent instance of the problem with treewidth $O(\sqrt{k})$. The application of this rule in a divide-and-conquer fashion together with new notion of protrusions brings us to linear kernels. We believe that the new notion of protrusion will be useful in many other algorithmic settings.

Linear Time Parameterized Algorithms for Subset Feedback Vertex Set

In the Subset Feedback Vertex Set (Subset FVS) problem, the input is a graph G on n vertices and m edges, a subset of vertices T, referred to as terminals, and an integer k. The objective is to determine whether there exists a set of at most k vertices intersecting every cycle that contains a terminal. The study of parameterized algorithms for this generalization of the Feedback Vertex Set problem has received significant attention over the last few years. In fact the parameterized complexity of this problem was open until 2011, when two groups independently showed that the problem is fixed parameter tractable (FPT). However, the existence of an FPT algorithm with a linear dependence on the input size has remained open. In this paper we design the first linear time parameterized algorithms for Subset FVS. More precisely, we obtain the following new algorithms for Subset FVS. " A randomized algorithm for Subset FVS running in time O(25.6^k · (n + m)). " A deterministic algorithm for Subset FVS running in time 2^{O(k log k)} · (n + m). In particular, the first algorithm obtains the best possible dependence on both the parameter as well as the input size, up to the constant in the exponent. Both of our algorithms are based on cut centrality, in the sense that solution vertices are likely to show up in minimum size cuts between vertices sampled from carefully chosen distributions.

Bibliometrics

Publication Years 2005-2017
Publication Count 584
Citation Count 3672
Available for Download 584
Downloads (6 weeks) 1780
Downloads (12 Months) 16571
Downloads (cumulative) 225594
Average downloads per article 386
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 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)
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
Uri Zwick 9
Erik Demaine 8
Haim Kaplan 8
Saket Saurabh 8
Gonzalo Navarro 7
Magnús Halldórsson 7
Pankaj Agarwal 7
Mikkel Thorup 7
Zeev Nutov 7
Samir Khuller 7
Daniel Lokshtanov 7
Maxim Sviridenko 7
Anupam Gupta 7
Ke Yi 6
Rohit Khandekar 6
David Peleg 6
Moshe Lewenstein 6
Andrzej Pelc 6
Micha Sharir 6
Viswanath Nagarajan 6
Noga Alon 6
Adi Rosén 5
David Eppstein 5
Chandra Chekuri 5
Fedor Fomin 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
Liam Roditty 5
Nikhil Bansal 5
Sariel Har-Peled 5
Thore Husfeldt 4
Telikepalli Kavitha 4
Glencora Borradaile 4
Loukas Georgiadis 4
Marek Cygan 4
Dana Ron 4
Harold Gabow 4
Ola Svensson 4
Boris Aronov 4
Srinivasa Satti 4
Meng He 4
Ashish Goel 4
Oren Weimann 4
Baruch Schieber 4
Guy Even 4
Fabrizio Grandoni 4
Sudipto Guha 4
Martín Farach-Colton 4
Mohammad Salavatipour 4
Susanne Albers 4
Paolo Ferragina 4
Ignaz Rutter 4
Seth Pettie 4
Asaf Levin 4
Kurt Mehlhorn 4
Stefan Kratsch 3
Danny Segev 3
Zoya Svitkina 3
Chaitanya Swamy 3
David Johnson 3
Allan Borodin 3
Refael Hassin 3
Philip Bille 3
Shay Mozes 3
Dimitrios Michail 3
Ramamoorthi Ravi 3
Amin Saberi 3
Yonatan Aumann 3
Yuval Rabani 3
Joseph Cheriyan 3
Konstantin Makarychev 3
Rajeev Raman 3
Morteza Zadimoghaddam 3
Dror Rawitz 3
Andrew McGregor 3
Lisa Hellerstein 3
Artur Czumaj 3
Michael Bender 3
Alberto Marchetti-Spaccamela 3
Surender Baswana 3
Berthold Vöcking 3
Yuval Emek 3
Daniel Berend 3
Svante Janson 3
Harald Räcke 3
Andreas Björklund 3
Stephen Alstrup 3
Edward Reingold 3
Rob Van Stee 3
Leah Epstein 3
Giuseppe Italiano 3
Amotz Bar-Noy 3
Sanjeev Khanna 3
Julia Chuzhoy 3
Dimitrios Thilikos 3
Bernhard Haeupler 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
M Ramanujan 3
Roberto Grossi 3
Laurent Alonso 3
Sergio Cabello 3
Kazuo Iwama 3
Marek Chrobak 3
Amit Chakrabarti 3
Rajiv Gandhi 3
Hsienkuei Hwang 3
Lisa Fleischer 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
Amr Elmasry 2
Anne Driemel 2
Tami Tamir 2
Petteri Kaski 2
Djamal Belazzougui 2
László Végh 2
Adrian Vetta 2
Dilys Thomas 2
Eduardo Laber 2
Shi Li 2
Luca Becchetti 2
Bruce Maggs 2
Dieter Kratsch 2
Martin Dietzfelbinger 2
Avinatan Hassidim 2
Łukasz Kowalik 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
Dariusz Kowalski 2
Holger Dell 2
Katarzyna Paluch 2
Cristopher Moore 2
Jochen Könemann 2
Christoph Ambühl 2
Ravishankar Krishnaswamy 2
Sungjin Im 2
Hiroki Yanagisawa 2
Rossano Venturini 2
James Munro 2
Tobias Jacobs 2
Siddhartha Sen 2
Conrado Martínez 2
Alfredo Viola 2
Don Coppersmith 2
Atri Rudra 2
David Harris 2
Zachary Friggstad 2
Joseph Leung 2
Joe Sawada 2
Peter Korteweg 2
Camil Demetrescu 2
Clifford Stein 2
Joan Boyar 2
Kamesh Munagala 2
HoLeung Chan 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
Thomas Sauerwald 2
Carmit Hazay 2
Bundit Laekhanukit 2
Rina Panigrahy 2
An Zhu 2
Joan Feigenbaum 2
Shuichi Miyazaki 2
Theis Rauhe 2
Teofilo Gonzalez 2
Roy Schwartz 2
Jérémy Barbay 2
Milan Ružić 2
Martin Strauss 2
Antoine Vigneron 2
Magnus Wahlström 2
Andréa Richa 2
Leen Stougie 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
Siuwing Cheng 2
Konstantinos Panagiotou 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
Robert Krauthgamer 2
Somnath Sikdar 2
Ioannis Koutis 2
Jesper Nederlof 2
Piotr Indyk 2
Sándor Fekete 2
Jeremy Fineman 2
Danny Hermelin 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
T Chan 2
Tomás Feder 2
Cyril Gavoille 2
Yuli Ye 2
Seth Gilbert 2
Julián Mestre 2
Mohammad Mahdian 2
Jiří Sgall 2
Mohammad Hajiaghayi 1
Bruce Kapron 1
David Kempe 1
Jared Saia 1
Benjamin Armbruster 1
Yinyu Ye 1
Paul Medvedev 1
Omkant Pandey 1
Matteo Frigo 1
Singhoi Sze 1
Walter Kern 1
Paweł Gawrychowski 1
Vladimir Braverman 1
Kedar Dhamdhere 1
Sandeep Shukla 1
Anil Maheshwari 1
Jessica Chang 1
Luís Russo 1
Frederic Dorn 1
Renars Gailis 1
Sagi Snir 1
Ari Freund 1
Valentina Ciriani 1
Norbert Zeh 1
Valentina Damerow 1
Andrea Vitaletti 1
Raja Jothi 1
F Bruss 1
Benjamin Rossman 1
Prudence Wong 1
Daniel Golovin 1
László Babai 1
Pedro Felzenszwalb 1
Yochai Twitto 1
Sambuddha Roy 1
Lusheng Wang 1
Eric De Verdiere 1
Alexander Schrijver 1
Xiaohui Zhang 1
Amitabh Chaudhary 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
Nicole Immorlica 1
Vahab Mirrokni 1
Hoyee Cheung 1
Li Ning 1
Christian Konrad 1
David Mount 1
Madhav Marathe 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
Boaz Patt-Shamir 1
Shuxin Nie 1
Adam Buchsbaum 1
Herman Haverkort 1
Iam Roditty 1
Biingfeng Wang 1
Bart Jansen 1
Fahad Panolan 1
Shahar Dobzinski 1
Yumei Huo 1
James Korsh 1
Stefan Schmid 1
David Cashman 1
Omer Reingold 1
Rajiv Raman 1
Bartosz Rybicki 1
Hyungchan An 1
Olivier Bodini 1
Ankur Gupta 1
Johannes Blömer 1
Vishal Sanwalani 1
Amit Sahai 1
Akiko Suzuki 1
Spyros Kontogiannis 1
Paul Spirakis 1
Edo Liberty 1
Roei Tov 1
Manan Sanghi 1
Balaji Venkatachalam 1
Charles Leiserson 1
Harald Prokop 1
Johann Hurink 1
Damien Stehlé 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
Serge Gaspers 1
Noam Solomon 1
Michael Goldwasser 1
Emo Welzl 1
Bin Fu 1
Jeremy Spinrad 1
Amitabha Bagchi 1
Christian Duncan 1
Tal Malkin 1
Fei Li 1
Yajun Wang 1
Avivit Levy 1
Guy Blelloch 1
David Steurer 1
Dominique Poulalhon 1
Kaiman Leung 1
Matthew Katz 1
Ryan Williams 1
Eyal Gordon 1
Cecilia Procopiuc 1
Rachid Guerraoui 1
Chidambaram Annamalai 1
Jens Gramm 1
Rolf Niedermeier 1
Thomas Hansen 1
Michael Pinedo 1
Rajsekar Manokaran 1
Martin Wahlén 1
Zvi Galil* 1
Evangelos Kranakis 1
Andrew Goldberg 1
Javad Ebrahimi 1
Yoshio Okamoto 1
Tsvi Kopelowitz 1
Adrian Dumitrescu 1
Michael Langberg 1
Panagiotis Kanellopoulos 1
Therese Biedl 1
Bernd Gärtner 1
Eyal Even-Dar 1
Moni Naor 1
Udi Wieder 1
Jianxing Feng 1
Rephael Wenger 1
Katarína Cechlárová 1
Takuro Fukunaga 1
Daniel Binkele-Raible 1
Henning Fernau 1
Miklós Ajtai 1
Ariel Levavi 1
Mikkel Thorup 1
Martin Grohe 1
Neva Cherniavsky 1
Bruce Bobier 1
Elias Koutsoupias 1
Ayelet Butman 1
Maarten Löffler 1
Justin Ward 1
Karl Wimmer 1
Danny Krizanc 1
Sriram Pemmaraju 1
Azarakhsh Malekian 1
Kashyap Dixit 1
Comandur Seshadhri 1
Mohsen Ghaffari 1
Richard Geary 1
Jeffrey Vitter 1
René Meier 1
Sebastian Wild 1
Ralph Neininger 1
Yixin Cao 1
Marcel Ackermann 1
Artur Jež 1
Markus Bläser 1
David Shmoys 1
Jens Maßberg 1
T Jayram 1
Gregory Sorkin 1
David Wood 1
Sridhar Ramachandran 1
Yang Liu 1
Ojas Parekh 1
Leana Golubchik 1
Yoav Giora 1
Rajesh Gupta 1
Jacques Yuster 1
Tomáš Tichý 1
Robert Kleinberg 1
Tom Leighton 1
Gauri Shah 1
Giuseppe Persiano 1
Ilan Newman 1
Keke Chen 1
Yoav Katz 1
Vincent Berry 1
Bruno Salvy 1
Yong Zhang 1
Ning Chen 1
Gopal Pandurangan 1
Vida Dujmović 1
Christian Scheideler 1
Till Tantau 1
Serge Plotkin 1
Jacob Holm 1
Frédérique Bassino 1
Wolfgang Bein 1
Andreas Brandstädt 1
Joseph Chan 1
Zheng Liu 1
Mark Pedigo 1
Jyrki Katajainen 1
Sundar Vishwanathan 1
William Aiello 1
Noa Lewenstein 1
Sen Zhang 1
Avraham Ben-Aroya 1
Andrew Shallue 1
Maxim Babenko 1
Wuzhou Zhang 1
Luigi Laura 1
Merav Parter 1
Tal Wagner 1
C Subramanian 1
Guy Kortsarz 1
Joachim Giesen 1
Éric Fusy 1
Danupon Nanongkai 1
Wei Hu 1
Sunil Arya 1
Theocharis Malamatos 1
Ron Adany 1
Elad Haramaty 1
Sanjiv Kapoor 1
Carola Wenk 1
Hristo Djidjev 1
Dan Rubenstein 1
JöRg Thuswaldner 1
Stavros Kolliopoulos 1
Shiri Chechik 1
Piotr Berman 1
Eunjung Kim 1
Pekka Parviainen 1
Rinat Avraham 1
Haitao Wang 1
Tobias Friedrich 1
Guyslain Naves 1
Michael Dom 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
Christos Kalaitzis 1
Yossi Richter 1
Jiong Guo 1
Dana Moshkovitz 1
Dany Breslauer 1
Christian Scheideler 1
Nina Taslaman 1
Chaiwah Wu 1
Deeparnab Chakrabarty 1
Madhav Jha 1
George Giakkoupis 1
Khoa Trinh 1
Ashkan Norouzi-Fard 1
Stefan Szeider 1
David Kirkpatrick 1
Bernadette Charron-Bost 1
Piotr Sankowski 1
Yue Wang 1
Tobias Friedrich 1
Ryan Moriarty 1
Robert Schweller 1
Bruce Reed 1
Quang Bui 1
Robert Carr 1
Dorit Hochbaum 1
Shayan Oveisgharan 1
Paolo Penna 1
Madhu Sudan 1
Ron Pinter 1
Arie Matsliah 1
Prosenjit Bose 1
Toshihiro Fujito 1
Guojun Li 1
Ningning Wu 1
Michèle Soria 1
Brigitte Vallee 1
Zdeněk Dvořák 1
Robin Thomas 1
Alexander Izsak 1
Hingfung Ting 1
Renato Carmo 1
Ariel Procaccia 1
Arash Asadpour 1
Luca Moscardelli 1
Lars Prädel 1
Philippe Baptiste 1
Rolf Fagerberg 1
Lawrence Larmore 1
Rami Cohen 1
Gorjan Alagic 1
Dany Azriel 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
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
Sumeet Khurana 1
Soumojit Sarkar 1
Jing Wang 1
Linus Hamilton 1
Richard Peng 1
Sofya Raskhodnikova 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
Virginia Vassilevska 1
Elliot Anshelevich 1
Michiel Smid 1
Vijaya Ramachandran 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
Jeff Erickson 1
Virginia Williams 1
Reuven Cohen 1
Reut Levi 1
David Woodruff 1
Friedrich Eisenbrand 1
Miguel Mosteiro 1
Hiro Ito 1
Mariusz Rokicki 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
Amit Bhosle 1
Nitish Korula 1
Vikraman Arvind 1
Christoph Dürr 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
Amitabh Sinha 1
András Benczúr 1
Shuchi Chawla 1
Liam Mencel 1
Dorothea Wagner 1
Barry O'Sullivan 1
Igor Razgon 1
Clemens Heuberger 1
Tsunghsi Tsai 1
SiuWing Cheng 1
Jurek Czyzowicz 1
Lukáš Poláček 1
Ning Chen 1
Claire Mathieu 1
Funda Ergün 1
Marcel Silva 1
Rishi Saket 1
Mohammad Khani 1
Yuan Zhou 1
Saber Fadaee 1
Fabrizio Frati 1
Benjamin Doerr 1
N Narayanaswamy 1
Arturo Gonzalez-Gutierrez 1
Shahar Fattal 1
Claire Kenyon 1
Owen Kaser 1
Emden Gansner 1
Jim Pugh 1
Hsueh Lu 1
Anna Gilbert 1
Jin Zhang 1
Giuseppe Paleologo 1
Charles Tresser 1
Kaimin Chung 1
Salil Vadhan 1
Marco Molinaro 1
Fabian Kuhn 1
Jarosław Byrka 1
Luca Foschini 1
Piotr Krysta 1
Matthias Függer 1
Jennifer Welch 1
Matt DeVos 1
Yusu Wang 1
Leonidas Guibas 1
John Carlsson 1
David Ilcinkas 1
Louis Ibarra 1
Panagiotis Cheilaris 1
Jakub Łącki 1
Dömötör Pálvölgyi 1
Alex Scott 1
Bogdan Chlebus 1
Moses Charikar 1
Venkatesh Natarajan 1
Phong Nguyêñ 1
Hiroshi Fujiwara 1
Matthew Maxel 1
Michael Krivelevich 1
Yijie Han 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
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
Maciej Kurowski 1
Stephen Kobourov 1
Amir Sapir 1
Kobbi Nissim 1
Christian Sommer 1
Alexander Kulikov 1
Ivan Mihajlin 1
Christina Fragouli 1
Ruben Van Der Zwaan 1
Ramamohan Paturi 1
Hjalte VildhØj 1
Csaba Tóth 1
Donglin Xia 1
Atlas IV 1
Ekkehard Köhler 1
Mark Petrick 1
George Yuhasz 1
Himanshu Gupta 1
David Eppstein 1
Erik Van Leeuwen 1
Vitaly Feldman 1
Jelani Nelson 1
Poshen Loh 1
Joseph Mitchell 1
Valentin Polishchuk 1
Jukka Suomela 1
Ittai Abraham 1
Ran Raz 1
Michael Kapralov 1
Keren Censor 1
Marc Van Kreveld 1
Alexander Langer 1
Cristiane Sato 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
Shimon Shahar 1
Hisao Tamaki 1
Hung Yu 1
Mahdi Cheraghchi 1
Vladlen Koltun 1
Gilad Tsur 1
Tomasz Nowicki 1
Avner Magen 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
Shakhar Smorodinsky 1
Mihai Bǎdoiu 1
Jens Vygen 1
Constantinos Daskalakis 1
Thomas Rothvoß 1
Yusuke Kobayashi 1
Rohan Fernandes 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
Nikos Karanikolas 1
Piyush Kurur 1
Alessandro Panconesi 1
Jaikumar Radhakrishnan 1
Julien Clément 1
Pierre Nicodème 1
Balaji Raghavachari 1
Mordecai Golin 1
Guy Louchard 1
Alexey Stepanov 1
Ge Nong 1
Tomasz Radzik 1
Markus Püschel 1
Sivan Toledo 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
Alexander Golovnev 1
Irit Katriel 1
Ryan Williams 1
Johannes Fischer 1
Erich Kaltofen 1
Stefan Hougardy 1
Micah Adler 1
Alex Levin 1
Martin Hoefer 1
Benjamin Aminof 1
Orna Kupferman 1
Stéphan Thomassé 1
Frank Staals 1
Stanislav Živný 1
David Kim 1
Prasad Raghavendra 1
Yi Wu 1
Guillaume Moroz 1
Jérémie Chalopin 1
Yann Disser 1
Matúš Mihaľák 1
Vít Jelínek 1
Aaron Williams 1
Krishnaram Kenthapadi 1
Daniel Lemire 1
Ron Levy 1
Bastian Pochon 1
Gerhard Woeginger 1
Hyunchul Lee 1
Christian Glacet 1
Shmuel Safra 1
Martin Gairing 1
Kasturi Varadarajan 1
Tsunghsi Tsai 1
Axel Bacher 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
Nir Ailon 1
Rogers Mathew 1
Siddhartha Sen 1
Jianer Chen 1
Songjian Lu 1
Fenghui Zhang 1
Anke Truß 1
Tim Nieberg 1
Roberto De Prisco 1
Sandy Irani 1
Wojciech Jawor 1
Tali Kaufman 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
Howard Karloff 1
Arlindo Oliveira 1
Shlomo Moran 1
Wingkin Sung 1
David Pritchard 1
Guochuan Zhang 1
Eli Upfal 1
Ulrich Schwarz 1
Friedhelm Heide 1
Andrea Ribichini 1
Amalia Duch 1
Yan Zhang 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
Jian Li 1
Devorah Kletenik 1
Srinivasan Parthasarathy 1
Alexander Wolff 1
Georg Baier 1
Ondřej Pangrác 1
Bernhard Von Stengel 1
Marcelo Mydlarz 1
Assaf Naor 1
F Shepherd 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
Matthew Drescher 1
Daniel Panario 1
Christos Levcopoulos 1
Yongbin Ou 1
Retsef Levi 1
Patchrawat Uthaisombut 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

Affiliation Paper Counts
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
University of Vienna 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
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
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
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
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
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
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
University of Texas at Austin 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
Sun Yat-Sen University 1
Italian National Research Council 1
London School of Economics and Political Science 2
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
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
Tsinghua 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
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
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
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
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
Cornell University 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
University of Bonn 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
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
University of California, Berkeley 9
University Michigan Ann Arbor 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
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
The University of Hong Kong 14
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
University of Bergen 16
Institute of Mathematical Sciences India 17
University of Haifa 18
AT&T Laboratories Florham Park 18
IBM Thomas J. Watson Research Center 18
Microsoft Research 18
Google Inc. 19
Stanford University 21
Weizmann Institute of Science Israel 21
Max Planck Institute for Informatics 25
Ben-Gurion University of the Negev 25
Bar-Ilan University 27
University of Maryland 27
Massachusetts Institute of Technology 27
Carnegie Mellon University 28
University of Waterloo 33
Technion - Israel Institute of Technology 33
Tel Aviv University 75

ACM Transactions on Algorithms (TALG)
Archive


2017
Volume 14 Issue 1, December 2017  Issue-in-Progress
Volume 13 Issue 4, December 2017  Issue-in-Progress
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