ACM DL

ACM Transactions on

Algorithms (TALG)

Menu
Latest Articles

Graph Reconstruction and Verification

How efficiently can we find an unknown graph using distance or shortest path queries between its vertices? We assume that the unknown graph G is connected, unweighted, and has bounded degree. In the reconstruction problem, the goal is to find the graph G. In the verification problem, we are given a hypothetical graph Ĝ and want to check... (more)

Batched Point Location in SINR Diagrams via Algebraic Tools

The SINR (Signal to Interference plus Noise Ratio) model for the quality of wireless connections has been the subject of extensive recent study. It... (more)

Adaptive Computation of the Swap-Insert Correction Distance

The Swap-Insert Correction distance from a string S of length n to another string L of length m ≥ n on the alphabet [1‥σ] is... (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

Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues

Conditional Lower Bounds for All-Pairs Max-Flow

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

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

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

Dynamic Time Warping and Geometric Edit Distance: Breaking the Quadratic Barrier

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

An Efficient Representation for Filtrations of Simplicial Complexes

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

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

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

Distribution-free Junta Testing

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

Online Submodular Maximization with Free Disposal

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

Network Sparsification for Steiner Problems on Planar and Bounded-Genus Graphs

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

Windrose Planarity: Embedding Graphs with Direction-Constrained Edges

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

Packing Groups of Items into Multiple Knapsacks

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

An Efficient Algorithm for Computing High-Quality Paths amid Polygonal Obstacles

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

Stream Sampling Framework and Application for Frequency Cap Statistics

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

Deterministic parallel algorithms for fooling polylogarithmic juntas and the Lovász Local Lemma

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

A Mazing 2+$\epsilon$ Approximation for Unsplittable Flow on a Path

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

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

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

Streaming Algorithms for Estimating the Matching Size in Planar Graphs and Beyond

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

An Optimal Algorithm for l_1-Heavy Hitters in Insertion Streams and Related Problems

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

Even Delta-Matroids and the Complexity of Planar Boolean CSPs

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

Bibliometrics

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

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

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

Search TALG
enter search term and/or author name