ACM DL

ACM Transactions on

Algorithms (TALG)

Menu
Latest Articles

Selection and Sorting in the “Restore” Model

Known Algorithms on Graphs of Bounded Treewidth Are Probably Optimal

Deterministic Truncation of Linear Matroids

Efficient Computation of Middle Levels Gray Codes

Approximation Algorithms for Minimum-Load k-Facility Location

Incremental Exact Min-Cut in Polylogarithmic Amortized Update Time

Randomized Embeddings with Slack and High-Dimensional Approximate Nearest Neighbor

The Alternating Stock Size Problem and the Gasoline Puzzle

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

Distributed Online and Stochastic Queueing on a Multiple Access Channel

Computing 2-Walks in Polynomial Time

NEWS

In Memoriam: David S. Johnson

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

About TALG

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

read more

Approximation Guarantees for the Minimum Linear Arrangement Problem by Higher Eigenvalues

Batched Point Location in SINR Diagrams via Algebraic Tools

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

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

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

Conditional Lower Bounds for All-Pairs Max-Flow

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

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.

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

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

Subexponential parameterized algorithm for Interval Completion

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

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.

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 g n on the alphabet [1..d] is the minimum number of insertions, and swaps of pairs of adjacent symbols, converting S into L. Contrarily to other correction distances, computing it is NP-Hard in the size d of the alphabet. We describe an algorithm computing this distance in time within O(d2 nm gd-1), where for each a[1..d] there are na occurrences of a in S, ma occurrences of a in L, and where g=maxa[1..d] min {na,ma-na} measures the difficulty of the instance. The difficulty g is bounded by above by various terms, such as the length n of the shortest string S, and by the maximum number of occurrences of a single character in S. Those results illustrate how, in many cases, the correction distance between two strings can be easier to compute than in the worst case scenario.

Graph Reconstruction and Verification

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

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

Beating Approximation Factor Two for Weighted Tree Augmentation with Bounded Costs

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

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

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

Near-Optimal Light Spanners

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

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.

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.

Editorial: ACM-SIAM Symposium on Discrete Algorithms (SODA) 2016 Special Issue

Bibliometrics

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

First Name Last Name Paper Counts
Saket Saurabh 13
Mohammadtaghi Hajiaghayi 12
Dániel Marx 12
Guy Kortsarz 11
Daniel Lokshtanov 11
Robert Tarjan 10
Uri Zwick 9
Pankaj Agarwal 8
Erik Demaine 8
Mikkel Thorup 8
Haim Kaplan 8
David Peleg 7
Magnús Halldórsson 7
Anupam Gupta 7
Zeev Nutov 7
Gonzalo Navarro 7
Maxim Sviridenko 7
Fedor Fomin 7
Ke Yi 7
Samir Khuller 7
Rohit Khandekar 6
Andrzej Pelc 6
Moshe Lewenstein 6
Micha Sharir 6
Venkatesh Raman 6
Viswanath Nagarajan 6
Noga Alon 6
Adi Rosén 5
Chandra Chekuri 5
David Eppstein 5
Kirk Pruhs 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
Harold Gabow 4
Ola Svensson 4
Boris Aronov 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
Joseph Cheriyan 3
Yuval Rabani 3
James Munro 3
Surender Baswana 3
Andreas Björklund 3
Daniel Berend 3
Andrew McGregor 3
Dariusz Kowalski 3
Dror Rawitz 3
Artur Czumaj 3
Michael Bender 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
Gabriel Scalosub 3
Amol Deshpande 3
George Karakostas 3
Kenichi Kawarabayashi 3
Aravind Srinivasan 3
Baruch Awerbuch 3
Shai Gutner 3
Wojciech Szpankowski 3
John Iacono 3
Jeff Edmonds 3
Amos Korman 3
Laurent Alonso 3
Marek Chrobak 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
Dimitrios Michail 3
Ramamoorthi Ravi 3
Philip Bille 3
Shay Mozes 3
Lisa Hellerstein 3
Morteza Zadimoghaddam 3
Konstantin Makarychev 3
Rajeev Raman 3
Amr Elmasry 2
Marcin Pilipczuk 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
Kunihiko Sadakane 2
Robert Krauthgamer 2
MohammadTaghi Hajiaghayi 2
Djamal Belazzougui 2
Adrian Vetta 2
Antoine Vigneron 2
Serge Gaspers 2
Monika Henzinger 2
Matthew Andrews 2
Claire Mathieu 2
Leen Stougie 2
Yury Makarychev 2
Milan Ružić 2
Fahad Panolan 2
Michele Flammini 2
Joan Feigenbaum 2
John Hershberger 2
Adam Meyerson 2
Michael Dinitz 2
Alexander Russell 2
Yishay Mansour 2
Shuichi Miyazaki 2
Goran Konjevod 2
Suresh Venkatasubramanian 2
Ramakrishna Thurimella 2
Dekel Tsur 2
Yoann Dieudonné 2
Vincenzo Bonifaci 2
Theis Rauhe 2
Kenneth Clarkson 2
Sungjin Im 2
Holger Dell 2
Danupon Nanongkai 2
Cristopher Moore 2
Katarzyna Paluch 2
Gregory Sorkin 2
Merav Parter 2
Hiroki Yanagisawa 2
Rossano Venturini 2
Christoph Ambühl 2
Jochen Könemann 2
Ravishankar Krishnaswamy 2
Conrado Martínez 2
HoLeung Chan 2
Hans Bodlaender 2
Vijay Kumar 2
Alfredo Viola 2
Don Coppersmith 2
Atri Rudra 2
Venkatesan Guruswami 2
Mohammad Salavatipour 2
Joseph Leung 2
Camil Demetrescu 2
Alex Kesselman 2
Peter Korteweg 2
Irene Finocchi 2
Siddhartha Sen 2
Clifford Stein 2
MohammadHossein Bateni 2
Stefan Langerman 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
Lisa Fleischer 2
Rina Panigrahy 2
An Zhu 2
Veli Mäkinen 2
Subhash Suri 2
James Aspnes 2
Anne Driemel 2
Petteri Kaski 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
Dimitris Fotakis 2
Jérémy Barbay 2
R Sritharan 2
Dilys Thomas 2
Petr Kolman 2
László Végh 2
Ioannis Koutis 2
Christophe Paul 2
Somnath Sikdar 2
Dina Sokol 2
Konstantinos Panagiotou 2
Holeung Chan 2
Iftah Gamzu 2
Eduardo Laber 2
Jesper Nederlof 2
Shi Li 2
Siuwing Cheng 2
Yusu Wang 2
Jie Gao 2
Ulrich Meyer 2
Mikko Koivisto 2
Ignasi Sau 2
Christos Kaklamanis 2
Klaus Jansen 2
Martin Aumüller 2
Sándor Fekete 2
Jeremy Fineman 2
Benjamin Raichel 2
Piotr Indyk 2
Angelika Steger 2
Martin Skutella 2
Jon Feldman 2
Shanghua Teng 2
Danny Hermelin 2
Mingyang Kao 2
Tomás Feder 2
Nicole Megow 2
Yuli Ye 2
Łukasz Kowalik 2
Cyril Gavoille 2
Jiří Sgall 2
Mohammad Mahdian 2
Martin Dietzfelbinger 2
Thomas Bläsius 2
Seth Gilbert 2
Julián Mestre 2
Luca Becchetti 2
Avinatan Hassidim 2
Bruce Maggs 2
Dieter Kratsch 2
Geevarghese Philip 2
Jittat Fakcharoenphol 2
Nir Ailon 1
Rafail Ostrovsky 1
Takeshi Tokuyama 1
Tim Nieberg 1
Gad Landau 1
Petra Berenbrink 1
Jérémie Chalopin 1
Yann Disser 1
Matúš Mihaľák 1
Vít Jelínek 1
Jeff Phillips 1
Erel Segal-Halevi 1
Ron Levy 1
Bastian Pochon 1
Alexander Wolff 1
Georg Baier 1
Ondřej Pangrác 1
Daniel Lemire 1
Srinivasan Parthasarathy 1
Saurabh Ray 1
Jian Li 1
Devorah Kletenik 1
Wei Chen 1
Estrella Eisenberg 1
Christian Knauer 1
Arlindo Oliveira 1
Shlomo Moran 1
Wingkin Sung 1
Howard Karloff 1
David Pritchard 1
Guochuan Zhang 1
Vanbang Le 1
Alessandro Panconesi 1
Omid Madani 1
Arnaud Labourel 1
Anil Maheshwari 1
Hoyee Cheung 1
Li Ning 1
Yuval Ishai 1
Daniel Panario 1
Patchrawat Uthaisombut 1
Matthew Drescher 1
Yongbin Ou 1
Retsef Levi 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
Alon Efrat 1
Felix Reidl 1
Daniel Rockmore 1
Robert Irving 1
Daming Zhu 1
Richard Ladner 1
Josef Widder 1
Stefanie Gerke 1
Christian Wulff-Nilsen 1
Andrea Vitaletti 1
F Bruss 1
Benjamin Rossman 1
Prudence Wong 1
Markus Nebel 1
Daniel Golovin 1
László Babai 1
Pedro Felzenszwalb 1
Ari Freund 1
Valentina Ciriani 1
Shuheng Zhou 1
Nicholas Harvey 1
Huy Nguyeݱn 1
Vladimir Braverman 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
Haitao Wang 1
Michael Goodrich 1
Sofya Raskhodnikova 1
Rinat Avraham 1
Elisabeth Lubbecke 1
Pascal Klaue 1
Joachim Gudmundsson 1
Giri Narasimhan 1
Gianni Franceschini 1
Mark De Berg 1
Gaia Nicosia 1
Leonard Schulman 1
Nira Shafrir 1
Mukesh Mohania 1
Waihong Chan 1
Barna Saha 1
Martin Jaggi 1
Sören Laue 1
Natalie Shapira 1
Zdeněk Dvořák 1
Robin Thomas 1
Michèle Soria 1
Brigitte Vallee 1
Hingfung Ting 1
Lan Liu 1
Eric Torng 1
Artem Pyatkin 1
Robby Lampert 1
George Christodoulou 1
Alexander Izsak 1
Dany Azriel 1
SiuWing Cheng 1
Jurek Czyzowicz 1
Qin Zhang 1
Virginia Vassilevska 1
ChiaChi Yeh 1
Cunquan Zhang 1
Dahlia Malkhi 1
Shuchi Chawla 1
Amitabh Sinha 1
András Benczúr 1
Lukáš Poláček 1
Paul LaFollette 1
Ran Mendelson 1
William Evans 1
Tsunghsi Tsai 1
Archontia Giannopoulou 1
Jared Saia 1
Norbert Zeh 1
Valentina Damerow 1
Keren Cohavi 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
Omrit Filtser 1
Shayan Ehsani 1
Abbas Mehrabian 1
Morteza Saghafian 1
Peter Widmayer 1
Patrizio Angelini 1
Siavosh Benabbas 1
Nikos Parotsidis 1
Olaf Maurer 1
Christos Levcopoulos 1
Alexander Hall 1
Heiko Schilling 1
Sambuddha Roy 1
Lusheng Wang 1
Éric De Verdière 1
Alexander Schrijver 1
Xiaohui Zhang 1
Madhav Marathe 1
Christian Konrad 1
Benjamin Sach 1
Rahul Garg 1
Łukasz Jeż 1
Jay Sethuraman 1
Satish Rao 1
Arie Koster 1
Jessica Chang 1
Renars Gailis 1
Luís Russo 1
Frederic Dorn 1
Sagi Snir 1
Yochai Twitto 1
Mark Ward 1
Sophie Spirkl 1
Rezaul Chowdhury 1
Reut Levi 1
Konstantin Andreev 1
Charles Garrod 1
Amin Sayedi-Roshkhar 1
Rajeev Motwani 1
Liadan O'Callaghan 1
Randeep Bhatia 1
Amit Bhosle 1
Sylvain Guillemot 1
Mohammad Khani 1
Marcel Silva 1
Rishi Saket 1
Yuan Zhou 1
Miguel Mosteiro 1
Hiro Ito 1
Keren Censor-Hillel 1
Yahav Nussbaum 1
Burkhard Monien 1
Alantha Newman 1
Ioannis Emiris 1
Kyle Fox 1
Gramoz Goranci 1
Clemens Heuberger 1
Jeff Erickson 1
Virginia Williams 1
Nitish Korula 1
Vikraman Arvind 1
Christoph Dürr 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
Wiebke Höhn 1
Noa Avigdor-Elgrabli 1
Matthias Englert 1
Andreas Wiese 1
Michiel Smid 1
Elliot Anshelevich 1
Daniel Binkele-Raible 1
Alon Shalita 1
Annamária Kovács 1
Cenk Sahinalp 1
Henning Fernau 1
Roei Tov 1
Oren Melamud 1
Andrei Krokhin 1
Stefan Schmid 1
Antonios Antoniadis 1
Kaiman Leung 1
Christian Duncan 1
Tal Malkin 1
Boaz Patt-Shamir 1
Iam Roditty 1
Biingfeng Wang 1
Vincenzo Auletta 1
Guy Blelloch 1
David Steurer 1
Dominique Poulalhon 1
Miklós Ajtai 1
Ariel Levavi 1
Maarten Löffler 1
James Korsh 1
Yumei Huo 1
Ankur Gupta 1
Takuro Fukunaga 1
Evangelos Markakis 1
Hsinhao Su 1
Eyal Even-Dar 1
Moni Naor 1
Udi Wieder 1
Jianxing Feng 1
Rephael Wenger 1
Yoshiharu Kohayakawa 1
Aaron Archer 1
Justin Ward 1
Karl Wimmer 1
Balaji Venkatachalam 1
Damien Stehlé 1
Yufei Tao 1
Hyungchan An 1
Bartosz Rybicki 1
Olivier Bodini 1
Rajiv Raman 1
David Cashman 1
Omer Reingold 1
Yongwook Choi 1
Venkatesan Chakaravarthy 1
Vinayaka Pandit 1
Pranjal Awasthi 1
Liam Mencel 1
Dorothea Wagner 1
Panos Giannopoulos 1
Xin Han 1
Tao Jiang 1
Jason McCullough 1
Claire Mathieu 1
Ning Chen 1
Funda Ergün 1
Nicholas Pippenger 1
Eldar Fischer 1
Jin Zhang 1
Xiaotie Deng 1
Juanjo Rué 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
Vitaly Feldman 1
Poshen Loh 1
Joseph Mitchell 1
Valentin Polishchuk 1
Jukka Suomela 1
Ittai Abraham 1
Marc Van Kreveld 1
Alexander Langer 1
Luca Foschini 1
Piotr Krysta 1
Georgios Amanatidis 1
Sebastian Krinninger 1
Elaine Shi 1
David Eppstein 1
Erik Van Leeuwen 1
Andreas Schmid 1
Ioannis Psarros 1
Jerri Nummenpalo 1
Marcin Bienkowski 1
Katarína Cechlárová 1
Johannes Blömer 1
Vishal Sanwalani 1
Angelo Fanelli 1
Manan Sanghi 1
Florian Diedrich 1
Bart Jansen 1
Shahar Dobzinski 1
Charles Leiserson 1
Harald Prokop 1
Therese Biedl 1
Bernd Gärtner 1
Spyros Kontogiannis 1
Paul Spirakis 1
Amit Sahai 1
Akiko Suzuki 1
Johann Hurink 1
T Jayram 1
Edo Liberty 1
Amitabha Bagchi 1
Mikkel Thorup 1
Martin Grohe 1
Shantanu Das 1
Giuseppe Di Battista 1
Maurizio Patrignani 1
Andrew Goldberg 1
Shuxin Nie 1
Adam Buchsbaum 1
Herman Haverkort 1
Michael Langberg 1
Panagiotis Kanellopoulos 1
Jeremy Spinrad 1
Bin Fu 1
Yoshio Okamoto 1
Tsvi Kopelowitz 1
Adrian Dumitrescu 1
Fei Li 1
Javad Ebrahimi 1
Yajun Wang 1
Avivit Levy 1
Günter Rote 1
Paul Bonsma 1
Jennifer Welch 1
Shaofeng Jiang 1
Himanshu Gupta 1
Matthias Függer 1
David Hay 1
Jelani Nelson 1
Ran Raz 1
Kinsum Mak 1
Moses Charikar 1
Venkatesh Natarajan 1
Fabrizio Luccio 1
Ying Xu 1
Cristiane Sato 1
Alex Scott 1
Phong Nguyêñ 1
Benjamin Doerr 1
N Narayanaswamy 1
Fabian Kuhn 1
Jarosław Byrka 1
Marco Molinaro 1
Giuseppe Paleologo 1
Charles Tresser 1
Kaimin Chung 1
Salil Vadhan 1
Timothy Chan 1
Matt DeVos 1
John Carlsson 1
Leonidas Guibas 1
Martin Pál 1
Sébastien Collette 1
Uriel Feige 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
Michael Fuchs 1
Manuel Kauers 1
Giovanni Manzini 1
Saber Fadaee 1
Fabrizio Frati 1
Michael Goldwasser 1
Asaf Shapira 1
J Munro 1
Noam Solomon 1
Emo Welzl 1
Neva Cherniavsky 1
Bruce Bobier 1
Elias Koutsoupias 1
Ayelet Butman 1
Stavros Kolliopoulos 1
Ilan Newman 1
Rajsekar Manokaran 1
Martin Wahlén 1
Zvi Galil* 1
Ning Chen 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
Shiri Chechik 1
Eunjung Kim 1
Richard Geary 1
Jeffrey Vitter 1
René Meier 1
Eleanor Rieffel 1
Dawn Song 1
Stephan Held 1
Zhiyi Huang 1
Yixin Cao 1
Artur Jež 1
Wolfgang Bein 1
Joseph Chan 1
Sebastian Wild 1
Ralph Neininger 1
Ojas Parekh 1
Yoav Giora 1
Gopal Pandurangan 1
Keke Chen 1
Yoav Katz 1
Vincent Berry 1
Pekka Parviainen 1
Jim Pugh 1
Yusuke Kobayashi 1
Ruben Van Der Zwaan 1
Emden Gansner 1
Claire Kenyon 1
Atlas IV 1
Ryan Hayward 1
Owen Kaser 1
Ekkehard Köhler 1
Renato Werneck 1
Leszek Gąsieniec 1
Alexander Kulikov 1
Ivan Mihajlin 1
Ramamohan Paturi 1
Hjalte VildhØj 1
Csaba Tóth 1
Donglin Xia 1
Christina Fragouli 1
Christian Sommer 1
Gruia Călinescu 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
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
Alex Levin 1
Frank Staals 1
Vladlen Koltun 1
Sandeep Sen 1
Nikhil Devanur 1
Comandur Seshadhri 1
David Wood 1
Leana Golubchik 1
Kashyap Dixit 1
Mohsen Ghaffari 1
Sriram Pemmaraju 1
Azarakhsh Malekian 1
Evangelos Kranakis 1
Danny Krizanc 1
Johanna Seif 1
Dan Rubenstein 1
JöRg Thuswaldner 1
Marcel Ackermann 1
Vida Dujmović 1
Christian Scheideler 1
Till Tantau 1
Frédérique Bassino 1
Jens Gramm 1
Rolf Niedermeier 1
Michael Pinedo 1
Chidambaram Annamalai 1
Thomas Hansen 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
Matthew Katz 1
Andrew Shallue 1
Maxim Babenko 1
Wuzhou Zhang 1
Luigi Laura 1
Tal Wagner 1
Cecilia Procopiuc 1
Rachid Guerraoui 1
Hristo Djidjev 1
Carola Wenk 1
Noa Lewenstein 1
Avraham Ben-Aroya 1
Sen Zhang 1
Wei Hu 1
Ron Adany 1
Elad Haramaty 1
Greg Little 1
Justus Schwartz 1
Mordecai Golin 1
Guy Louchard 1
François Nicolas 1
Stanislav Živný 1
David Kim 1
Prasad Raghavendra 1
Yi Wu 1
Guillaume Moroz 1
Rohan Fernandes 1
David Fernández-Baca 1
Richard Cole 1
Thomas Pensyl 1
Robert Ganian 1
Karsten Tiemann 1
Tomasz Nowicki 1
Avner Magen 1
Sara Ahmadian 1
Babak Behsaz 1
Pranabendu Misra 1
Tomasz Jurdziński 1
Meirav Zehavi 1
Stefan Hougardy 1
Micah Adler 1
Bojan Mohar 1
Ulrich Faigle 1
Reid Andersen 1
Valerie King 1
Piyush Kurur 1
Alessandro Panconesi 1
Jaikumar Radhakrishnan 1
Julien Clément 1
Pierre Nicodème 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
Bruno Salvy 1
Sanjiv Kapoor 1
Guy Kortsarz 1
Joachim Giesen 1
Yong Zhang 1
Andreas Brandstädt 1
Zheng Liu 1
Mark Pedigo 1
Jyrki Katajainen 1
Sundar Vishwanathan 1
William Aiello 1
Sumeet Khurana 1
Soumojit Sarkar 1
Jing Wang 1
Dorit Hochbaum 1
Ron Pinter 1
Arie Matsliah 1
Toshihiro Fujito 1
Prosenjit Bose 1
Nina Taslaman 1
Dany Breslauer 1
Christian Scheideler 1
Ariel Procaccia 1
Amnon Ta-Shma 1
Michael Schapira 1
Rebecca Wright 1
Yefim Dinitz 1
Alexander Shvartsman 1
Qianping Gu 1
Tzuchin Lin 1
Paolo Penna 1
Madhu Sudan 1
Linus Hamilton 1
Richard Peng 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
Robert Carr 1
Shayan Oveisgharan 1
Renato Carmo 1
Rajesh Chitnis 1
Markus Püschel 1
Lene Favrholdt 1
Martin Hoefer 1
Mohammadamin Fazli 1
Sina Sadeghabad 1
MohammadAli Safari 1
Dannyziyi Chen 1
Jan Kratochvíl 1
Per Austrin 1
Konstantinos Georgiou 1
Edith Cohen 1
Nick Duffield 1
Carsten Lund 1
Sivan Toledo 1
Ge Nong 1
Tomasz Radzik 1
Alexander Golovnev 1
Ryan Williams 1
Johannes Fischer 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
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
Ronald Graham 1
Peter Rossmanith 1
Shmuel Safra 1
Gelin Zhou 1
Ningning Wu 1
Arkadiusz Socała 1
Bryan Wilkinson 1
Ofer Neiman 1
Mihai P&acaron;trascu 1
Bruce Reed 1
Guyslain Naves 1
Tobias Friedrich 1
Michael Dom 1
Ashkan Norouzi-Fard 1
Deeparnab Chakrabarty 1
Madhav Jha 1
George Giakkoupis 1
Khoa Trinh 1
Stefan Szeider 1
Chaiwah Wu 1
Torsten Mütze 1
Miroslaw Korzeniowski 1
Alexandru Tomescu 1
Jens Schmidt 1
Pradeesha Ashok 1
Sudeshna Kolay 1
Zhewei Wei 1
Wolfgang Slany 1
Doratha Vinkemeier 1
Yue Wang 1
Arash Asadpour 1
Philippe Baptiste 1
Jiong Guo 1
Yi Li 1
Aadhar Jain 1
Robert Schweller 1
Luca Moscardelli 1
Lars Prädel 1
Christos Kalaitzis 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
Guojun Li 1
Marcelo Mydlarz 1
Niv Buchbinder 1
Afshin Nikzad 1
T Chan 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
Eli Upfal 1
Sharon Marko 1
Xiaotie Deng 1
Anne Condon 1
Aravindan Vijayaraghavan 1
Axel Bacher 1
Tsunghsi Tsai 1
Michael Etscheid 1
Jiongxin Jin 1
Mankit Lau 1
Martin Gairing 1
Kasturi Varadarajan 1
Amin Jorati 1
Evangelos Anagnostopoulos 1
Abhinandan Nath 1
Xiaowei Wu 1
Ademir Hujdurović 1
Martin Milanič 1
Romeo Rizzi 1
Tamás Fleiner 1
Steve Oudot 1
Friedhelm Heide 1
Hyunchul Lee 1
Ulrich Schwarz 1
Christian Glacet 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

Affiliation Paper Counts
University of Durham 1
University College Cork 1
Boston University 1
Aegean University 1
University of G. d'Annunzio Chieti and Pescara 1
Universite Pierre et Marie Curie 1
Netanya Academic College 1
National Taiwan Ocean University 1
University of Eastern Piedmont Amedeo Avogadro, Alessandria 1
Laboratoire d'Analyse et Modelisation de Systemes pour l'Aide a la Decision 1
University of Tubingen 1
Federal University of Parana 1
Wroclaw University of Science and Technology 1
University of Missouri-Kansas City 1
Birkbeck University of London 1
Hong Kong Polytechnic University 1
National Technical University of Athens 1
Vrije Universiteit Amsterdam 1
Hong Kong Baptist University 1
University of Wisconsin Madison 1
St. Petersburg Department of V.A. Steklov Institute of Mathematics of the Russian Academy of Sciences 1
University of Electro-Communications 1
Linkoping University 1
SRI International 1
University of Glasgow 1
University of Melbourne 1
Iowa State University 1
Cisco Systems 1
Kwansei Gakuin University 1
University of Leoben 1
Dalian University of Technology 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
The University of North Carolina at Charlotte 1
NASA Ames Research Center 1
University of California, Santa Cruz 1
University of Miami 1
International Institute of Information Technology Bangalore 1
University of Colorado at Denver 1
The University of Georgia 1
Duquesne University 1
Ludwig Maximilian University of Munich 1
National Institutes of Health, Bethesda 1
NEC Deutschland GmbH 1
Utah State University 1
Yonsei University 1
Microsoft Research Cambridge 1
Sandia National Laboratories, New Mexico 1
University of Sao Paulo 1
Illinois Wesleyan University 1
University of Stellenbosch 1
University of Quebec in Montreal 1
Meiji University 1
Wesleyan University Middletown 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
University of Bristol 1
Emory University 1
University of Milan 1
National Research University Higher School of Economics, Moscow 1
University of California, Merced 1
Center for Communications Research 1
Oracle Corporation 1
University of New Brunswick 1
Rensselaer Polytechnic Institute 1
Ecole Normale Superieure de Lyon 1
Institute for Advanced Studies 1
Istituto di Scienza e Tecnologie dell'Informazione A. Faedo 1
ORT Braude - College of Engineering 1
Siemens AG 1
Brandenburg University of Technology Cottbus 1
Malmo University 1
Laboratoire d'Informatique de l'Ecole Polytechnique 1
Lubeck University 1
Indian Institute of Technology, Bombay 1
Johannes Kepler University Linz 1
VMware, Inc 1
Leonard N. Stern School of Business 1
University of California, Davis 1
Commonwealth Scientific and Industrial Research Organization 1
Imperial College London 1
Italian National Research Council 1
University of Tsukuba 1
Microsoft Research India 1
Apple Computer 1
Universite Grenoble Alpes 1
Medical University of South Carolina 1
Toyohashi University of Technology 1
California Institute of Technology 1
University of Witwatersrand 1
Pavol Jozef safarik University in Kosice 1
DePaul University 1
J. Craig Venter Institute 1
California State University Northridge 1
Indian Institute of Technology, Madras 1
Alexandria University 1
University of Tokyo 1
Amazon.com, Inc. 1
Maastricht University 1
BRICS Basic Research in Computer Science 1
George Mason University 1
CNRS Centre National de la Recherche Scientifique 1
CSIRO Data61 1
University of Illinois at Chicago 1
University of Verona 1
Los Alamos National Laboratory 1
Google Switzerland GmbH 1
Dalle Molle Institute for Artificial Intelligence 1
IBM Tokyo Research Laboratory 1
Harvey Mudd College 1
Zhejiang University 1
Shanghai Jiaotong University 1
Michigan State University 1
Vanderbilt University 1
University of Wisconsin Milwaukee 1
Lawrence Livermore National Laboratory 1
Stevens Institute of Technology 1
Florida International University 1
University of Cambridge 2
University of Kaiserslautern 2
Universite Paris-Sud XI 2
Royal Holloway University of London 2
Saarland University 2
Instituto Superior Tecnico 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
University of Notre Dame 2
Athens University of Economics and Business 2
Georgetown University 2
Pontifical Catholic University of Rio de Janeiro 2
IBM Haifa Labs 2
Mentor Graphics Corporation 2
Microsoft Research Asia 2
National Taiwan University 2
University of Primorska 2
St. Louis University 2
Indian Institute of Technology, Delhi 2
Tata Institute of Fundamental Research 2
University of L'Aquila 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
Free University of Berlin 2
University of Puerto Rico 2
University of Denver 2
Technische Universitat Braunschweig 2
Tohoku University 2
Temple University 2
University of Guelph 2
University of Trier 2
West Virginia University 2
Center for Mathematics and Computer Science - Amsterdam 2
Kasetsart University 2
Graz University of Technology 2
Universite de Lorraine 2
University of Aarhus 3
Universite de Bordeaux 3
Harvard University 3
University of Texas-Pan American 3
University of Chicago 3
Royal Institute of Technology 3
Oregon State University 3
Dalhousie University 3
Aix Marseille Universite 3
The Interdisciplinary Center Herzliya 3
Tsinghua University 3
University of Texas at Dallas 3
The University of Sydney 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
Brooklyn College 3
University of Ljubljana 3
University of Freiburg 3
Uppsala University 3
University of Texas at Austin 3
York University Canada 3
King Abdullah University of Science and Technology 3
National University of Singapore 3
University of Helsinki 3
Toyota Technological Institute at Chicago 3
Goethe University Frankfurt 3
New Jersey Institute of Technology 3
Aalto University 3
Pennsylvania State University 3
TU Dortmund University 4
Budapest University of Technology and Economics 4
Universitat Politecnica de Catalunya 4
INRIA Lorraine 4
National Tsing Hua University 4
Karlsruhe Institute of Technology, Campus South 4
Johns Hopkins University 4
Roma Tre University 4
University of Colorado at Boulder 4
University at Buffalo, State University of New York 4
Arizona State University 4
University of Ioannina 4
University of Twente 4
University of Montpellier 4
City University of New York 4
University of Southern Denmark 4
University of Southern California 4
University of Michigan 4
Helsinki Institute for Information Technology 4
Research Organization of Information and Systems National Institute of Informatics 4
Nanyang Technological University 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
University of Victoria 4
University of Salerno 4
Chinese University of Hong Kong 4
Nokia Bell Labs 5
Illinois Institute of Technology 5
University of Massachusetts Amherst 5
Computer and Automation Research Institute Hungarian Academy of Sciences 5
University of Kiel 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
Columbia University 6
Simon Fraser University 6
IT University of Copenhagen 6
Kyoto University 6
Charles University 6
Cornell University 6
Humboldt University of Berlin 6
Universite Libre de Bruxelles 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
Yahoo Research Labs 7
University of Athens 7
University of California, Santa Barbara 7
University of Patras 7
University of Roma Tor Vergata 7
Technical University of Denmark 8
McGill University 8
University of Quebec in Outaouais 8
Carleton University 8
Open University of Israel 8
University of California, Los Angeles 8
NYU Tandon School of Engineering 8
Sharif University of Technology 8
Stony Brook University 8
University of California, Irvine 8
University of Copenhagen 8
Hebrew University of Jerusalem 9
Rutgers, The State University of New Jersey 9
University of Liverpool 9
University of Illinois at Urbana-Champaign 9
University of Wroclaw 9
University of Bonn 9
University of Pennsylvania 9
University of Illinois 9
The University of Warwick 9
Vienna University of Technology 9
Lund University 9
University of California, Berkeley 9
Friedrich Schiller University Jena 9
University of Paderborn 9
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
University of Warsaw 11
Brown University 11
Swiss Federal Institute of Technology, Zurich 11
Duke University 13
Princeton University 13
Eindhoven University of Technology 13
Hong Kong University of Science and Technology 14
University of Alberta 14
Technical University of Berlin 14
Rutgers University-Camden campus 15
Swiss Federal Institute of Technology, Lausanne 15
University of Roma La Sapienza 15
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 20
Stanford University 23
Weizmann Institute of Science Israel 23
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
University of Bergen 28
Carnegie Mellon University 29
Technion - Israel Institute of Technology 33
University of Waterloo 36
Tel Aviv University 75

ACM Transactions on Algorithms (TALG)
Archive


2018
Volume 14 Issue 2, June 2018
Volume 14 Issue 1, January 2018

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

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

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

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

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

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

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

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

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

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

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

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

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

Search TALG
enter search term and/or author name