Abstracts (as of April 2013 ):

Since the meet with the long-expected power wall'' in 2005, hardware manufacturers have been developing multicore/parallel computers that can host multiple of cores or processors in a single machine. Current multicore computers feature as many an several dozens of processors. In the near future, the numbers are expected to grow to hundreds and even thousands. To harness the power of multicore computers, nearly any parallel programming systems rely on a load-balancing algorithm that can efficiently distribute parallel tasks among available processors. Many such load-balancing algorithms have been developed over the several decades. Unfortunately, all existing algorithms rely on synchronization operations, such as memory fences (barriers) and atomic read-write operations (e.g., compare and swap) for controlling access to shared, concurrent data structures. Since such operations require agreement between multiple processors, they tend to be expensive and can lead to serialization of parallel computations, thus, limiting scalability. In this talk, I present a load-balancing algorithm that requires no atomic read-modify-write operations and no memory fences on modern hardware such as Intel's multicore chips. The algorithm eliminates synchronization by relying on asynchronous messages (exchanged via memory) and by taking advantage of some unique properties of hardware shared memory systems, e.g., the ability to drop messages (via overriding).

For decades practitioners have recognized the desirability of algorithms that adapt as the availability of RAM changes. There exists a theoretical framework for designing algorithms that adapt to these memory fluctuations, but the last decade and a half has seen essentially no theoretical followup work. We prove that a general class of cache-oblivious algorithms (but not all of them) are optimally cache-adaptive.
Joint work with Roozbeh Ebrahimi, Jeremy T. Fineman, Golnaz Ghasemiesfeh, Rob Johnson, and Samuel McCauley.

A New Perspective on Vertex Connectivity

Vertex and edge connectivity are fundamental graph-theoretic concepts, as they give measures for flows and robustness. While there is extensive knowledge in the literature about edge connectivity, using the essential tool of edge-disjoint spanning trees, much less is known about vertex connectivity, mainly due to the exponential number of vertex cuts, as opposed to the polynomial number of edge cuts. In this talk I will present new results that propose CDS (connected dominating set) partitions and packings as tools that help us argue about the vertex connectivity of graphs. I will show algorithms for obtaining an optimal CDS packing of size Omega(k/logn) and a CDS partition of size Omega(k/log^5n) in k-vertex connected graphs. Our results also apply to analyzing vertex connectivity under random vertex sampling, showing an almost optimal bound of \tilde{Omega}(kp^2) for the vertex connectivity of a graph whose vertexes are sampled with probability p from a k-vertex connected graph. Finally, I will discuss applications to the throughput of store-and-forward broadcast algorithms.
Based on joint work with Mohsen Ghaffari and Fabian Kuhn.

Customizable Route Planning in Road Networks

In this talk, I will present the latest version of our customizable route planning engine. It can compute exact shortest paths in continental road networks (with tens of millions of road segments) and is able to incorporate realistic turn costs, custom height and weight restrictions, personal preferences, and traffic in real time. Moreover, it can efficiently answer extended queries such as computing distance tables or best points-of-interest, which are important building blocks for advanced map applications.
Joint work with Andrew Goldberg, Thomas Pajor, and Renato Werneck

Algorithmic challenges in dynamic program analysis

Dynamic program analysis encompasses the development of tools and techniques for analyzing computer software by gathering information from programs at runtime. Relevant applications include performance profi ling, debugging, intrusion detection, and program understanding. Optimizing the performance of dynamic analysis tools is of fundamental importance for their effective deployment and usability, and poses many algorithmic challenges. The highly data-intensive nature of the problem has several consequences. First, since analysis routines are typically inlined with program execution, analyzed programs may be substantially slowed down. Second, tools must be able to analyze huge streams of low-level events generated by a program at typical rates of several megabytes per second. Dealing with such problems requires a genuine combination of application-oriented research and innovative contributions in algorithm engineering and general algorithmic techniques. In this talk I plan to discuss examples of algorithmic problems arising in this speci c application domain and to show how results in algorithmic theory can be applied to the design and implementation of analysis tools. I will also address examples of how novel analysis methodologies can help algorithm engineers tune the performance of their code.

Efficient Fetch-and-Increment

A Fetch-and-Increment object stores a non-negative integer and supports a single operation, FI, that returns the value of the object and increments it. Such objects are used in many asynchronous shared memory algorithms, such as renaming, mutual exclusion, and barrier synchronization. We present the first implementation of a wait-free Fetch-and-Increment object from registers and LL/SC objects that has poly-logarithmic step complexity and polynomial space complexity, using logarithmic sized words.
This work is joint with Vijaya Ramachandran and Philipp Woelfel and appeared at DISC 2012.

Streaming algorithms where order matters

In most streaming problems, we strive to compute statistical properties of the input stream. In such cases, we are mostly interested in the frequency of objects in the stream rather then when they appear. In this talk, we will make a case for algorithms computing functions on streams where the order of elements in the stream matter. This includes the (almost entire) string algorithms literature, as well as part of the online algorithms area.

TBA

Finding Dominators in Interprocedural Flowgraphs

The computation of dominators in a flowgraph has applications in diverse areas including program optimization and code generation, constraint programming, circuit testing, and theoretical biology. Efficient algorithms for this problem operate in the intraprocedural case where all flowgraph paths are valid. In the interprocedural case, which appears in the setting of whole-program analysis and optimization, however, there are path constraints that have to be taken into account. As a result, the most efficient algorithms for computing dominators cannot handle the interprocedural case. Unlike the intraprocedural dominators problem, the transitive reduction of the interprocedural dominance relation is not a tree but a directed acyclic graph. In this talk we discuss efficient algorithms for computing the interprocedural dominance relation.

Highway Dimension: From Practice to Theory and Back

Computing driving directions has motivated many shortest path heuristics that answer queries on continental-scale networks, with tens of millions of intersections, in real time. The underlying algorithms are highly practical and intuitive, but until recently there was no theoretical explanation of their practical performance. We review some of these algorithms and give the first theoretical analysis for them on a non-trivial class of networks. For our analysis, we introduce the notion of highway dimension. The analysis gives good bounds for networks with low highway dimension. Our analysis explores an unexpected relationship to VC-dimension, which leads to better algorithms. We also show that the hub labeling algorithm achieves a better theoretical time bound. This motivates a heuristic implementation of this algorithm. Our experimenters show that the implementation outperforms the fastest previous codes, validating the theoretical prediction. Compared to the SODA 2010 and ICALP 2011 papers, this talk contains new results, including an improved definition of highway dimension that is a strengthening of the doubling dimension, improved bounds, and a new analysis of the transit node algorithm.
Joint work with Ittai Abraham, Daniel Delling, Amos Fiat, and Renato Werneck

Height-Partitioning of AVL Trees

We introduce and discuss the notion of height partitioning for an AVL tree in order to maintain it as a collection of linked complete binary trees: its tree topology and insertion algorithm are preserved, while the deletions are weak (logically mark as deleted and periodically rebuild). We describe how AVL trees can simultaneously attain several properties in this way: better memory allocation, space-efficient representation, cache obliviousness, and dynamization of static data structures. We show how to dynamically maintain the height partitioning of an AVL tree in logarithmic amortized time and constant average time per update. As a byproduct of our analysis, we can amortize with the same bounds, the cost of rebuilding the whole subtree of the critical node after performing its rotation(s), thus overcoming some limitations of exponential potential functions.
Joint work with M. Amani, A. Bernasconi, and L. Pagli.

Breaking the O(n m) Barrier for Buechi Games and Maximal End-Component Decomposition

Computing the winning set for Buechi Games and computing the maximal end-component decomposition in graphs are central problems in computer aided verification. We present a simple technique that gives O(n^2)-time algorithms for both problems, improving a running time bound from 1991.
This is joint work with Krishnendu Chatterjee.

The Power and Limitations of Static Binary Search Trees with Lazy Finger

A static binary search tree where every search starts from where the previous one ends (lazy finger) is considered. Such a search method is more powerful than that of the classic optimal static trees, where every search starts from the root (root finger), and less powerful than when rotations are allowed---where finding the best rotation based tree is the topic of the dynamic optimality conjecture of Sleator and Tarjan. The runtime of the classic root-finger tree can be expressed in terms of the entropy of the distribution of the searches, but we show that this is not the case for the optimal lazy finger tree. A non-entropy based asymptotically-tight expression for the runtime of the optimal lazy finger trees is derived, and a dynamic programming-based method is presented to compute the optimal tree.
This is joint work with Prosenjit Bose, Karim Douïeb, Stefan Langerman.

Incremental cycle detection

In the incremental cycle detection problem we maintain a directed acyclic graph under insertions of arcs and would like to detect the first insertion that closes a directed cycle. I will describe a new technique for solving this problem.

Dynamic Graph Connectivity in Polynomial Expected Worst Case Time

The dynamic graph connectivity problem is the following: given a graph on a fixed set of n nodes which is undergoing a sequence of edge insertions and deletions, answer queries of the form Q(a,b): "Is there a path between nodes a and b?" While data structures for this problem with polylogarithmic amortized time per operation have been known since the mid-1990's, these data structures have Theta(n) worst case time. In fact, no previously known solution has worst case time per operation which is o(n^{1/2}). In this talk I'll explain a solution with worst case times O(log^4 n) per edge insertion, O(log^5 n) per edge deletion, and O(log n/log log n) per query. The answer to each query is correct if the answer is yes" and is correct with high probability if the answer is no".
This work is joint with Bruce Kapron and Ben Mountjoy.

TBA

Lasserre hierarchies of relaxations, applied to knapsack

Succinct data structures for representing equivalence classes

Given a partition of an n element set into equivalence classes, we consider time-space trade-off for representing it to support the query that asks whether two given elements are in the same equivalence class. This has various applications including for testing whether two vertices are in the same connected component in an undirected graph or in the same strongly connected component in a directed graph. We consider the problem in several situations.
- First we examine the problem of labeling nodes so that with no additional information, we can determine whether two labels come from the same class. A tight bound on the range of labels is determined.
- Next we consider the issue of labeling schemes where we assign distinct labels from the range 1,..,n, and determine the additional space necessary to respond to equivalence class queries.
- Efficient algorithms for responding to queries under this minimal label model are presented.
- Finally we discuss updating the labels after a sequence of class union operations.
This is joint work with Moshe Lewenstein and Venkatesh Raman

Multimodal Route Planning - An Overview

This talk gives an overview of recent approaches to location-to-location route planning for multimodal networks consisting of schedule-based public transit, (unrestricted) walking, driving, and cycling. We discuss modeling issues arising with each mode of transportation including specialties like in bicycle rental systems. We review recent algorithmic approaches to the problem such as preprocessing techniques that enable fast queries for interactive applications and conclude by discussing several open challenges.

Maintaining strongly connected components

We consider the problem of maintaining the strongly connected components (SCCs) of an $n$-nodes and $m$-edges directed graph that undergoes a sequence of edge deletions. Recently, in SODA 2011, {\L}\k{a}cki presented a deterministic algorithm that preprocess the graph in $O(mn)$ time and creates a data structure that maintains the SCCs of a graph under edge deletions with a total update time of $O(mn)$. The data structure answers strong connectivity queries in $O(1)$ time. The worst case update time after a single edge deletion might be as large as $O(mn)$. In this paper we reduce the preprocessing time and the worst case update time of {\L}\k{a}cki's data structure from $O(mn)$ to $O(m \log n)$. The query time and the total update time remain unchanged.

Byzantine Agreement in Polynomial Expected Time

How can we build a reliable system out of unreliable parts? Byzantine agreement is fundamental to addressing this question. The Byzantine agreement problem is to devise an algorithm so that n agents, each with a private input can agree on a single common output that is equal to some agent's input. In the classic Byzantine agreement problem, communication is via asynchronous message-passing and the adversary is adaptive with full information. In particular, the adversary can adaptively determine which processors to corrupt and what strategy these processors should use as the algorithm proceeds; the scheduling of the delivery of messages is set by the adversary, so that the delays are unpredictable to the algorithm; and the adversary knows the states of all processors at any time, and is assumed to be computationally unbounded. Such an adversary is also known as strong. We present a polynomial expected time algorithm to solve asynchronous Byzantine Agreement with a strong adversary that controls up to a constant fraction of the processors. This is the fi rst improvement in running time for this problem since Ben-Or's exponential expected time solution in 1983. Our algorithm is designed so that in order to thwart it, corrupted agents must engage in statistically deviant behavior that is detectable by individual agents. This suggests a new paradigm for secure distributed computing: the design of algorithms that force an attacker into behavior that is statistically deviant in a way that is computationally detectable.

TBA

(Recursive) Cycle Separators in Planar Graphs

Divide-and-conquer algorithms for planar graphs usually exploit separators, pioneered in seminal work of Lipton and Tarjan. Many of the more recent planar graph algorithms (such as those for min cut, max flow, shortest paths with negative lengths, or distance oracles) use a more elaborate "combine" phase, exploiting non-crossing properties. To run this combine phase efficiently, the separator is required to correspond to a Jordan curve (as opposed to an arbitrary set of points). Many recent planar graph algorithms therefore use Miller's cycle separator algorithm, generally as a black box. We shall discuss a new (and arguably simpler) cycle separator algorithm, its implementations (both theoretical and in actual code), and its application in a new algorithm that computes recursive cycle separator decompositions in linear time.
Joint work with Philip N. Klein and Shay Mozes (STOC 2013), and Eli Fox-Epstein, Shay Mozes, and Phitchaya Mangpo Phothilimthana, (ALENEX 2013)

Disjoint Set Union With Randomized Linking

A classic result in the analysis of data structures is that path compression with linking by rank solves the disjoint set union problem in almost-constant amortized time per operation. Recent experiments suggest that in practice, a naïve linking method works just as well if not better than linking by rank, in spite of being theoretically inferior. How can this be? New work of Ashish Goal, Sanjjev Khanna, Mikhail Kapralov, and the speaker shows that randomized linking is as efficient as linking by rank. This result provides theory that matches the experiments, since the experiments implicitly do randomized linking as a result of the way the inputs are generated.

Approximating the graph diameter

I'll present efficient algorithms for approximating the diameter of a directed or undirected graph with nonnegative weights. The running time of the algorithms on sparse graphs with n vertices and n^{1+o(1)} edges is O(n^{2-eps}) for constant eps>0, that is they are polynomially faster than any algorithm computing distance estimates for all pairs of nodes. The first algorithm runs in \tilde{O}(m\sqrt n} expected time for graphs with n vertices and m edges and returns an estimate E for the diameter D that satisfies D\geq E\geq 2D/3-W where W is the largest distance in the graph. The second algorithm is deterministic and runs in \tilde{O}(mn^{2/3} log W) time and returns an estimate E with D\geq E\geq 2D/3 when the weights are integers. I'll also give evidence that these algorithms are optimal in the following sense: if there is an algorithm that runs in O(n^{2-eps}) time for some constant eps>0 on all undirected unweighted graphs with n^{1+o(1)} edges that returns an estimate E with D\geq E\geq (2/3+\delta)D for some constant \delta>0, then the Strong Exponential Time Hypothesis of Impagliazzo, Paturi and Zane is false.
Based on joint work with Liam Roditty and Shiri Chechik.

Search-Space Size in Contraction Hierarchies

Contraction hierarchies are a speed-up technique to improve the performance of shortest-path computations, which works very well in practice. Despite convincing practical results, there is still a lack of theoretical explanation for this behavior. In this talk, we present a theoretical framework for studying search space sizes in contraction hierarchies. We prove the first bounds on the size of search spaces that depend solely on structural parameters of the input graph, that is, they are independent of the edge lengths. To achieve this, we establish a connection with the well-studied elimination game. Our bounds apply to graphs with treewidth k, and to any minor-closed class of graphs that admits small separators. For trees, we show that the maximum search space size can be minimized efficiently, and the average size can be approximated efficiently within a factor of 2. We show that, under a worst-case assumption on the edge lengths, our bounds are comparable to the recent results of Abraham et al. (ICALP'11), whose analysis depends also on the edge lengths. As a side result, we link their notion of highway dimension (a parameter that is conjectured to be small, but is unknown for all practical instances) with the notion of pathwidth. This is the first relation of highway dimension with a well-known graph parameter.
This is joint work with Reinhard Bauer, Tobias Columbus and Ignaz Rutter.

An Exact Combinatorial Algorithm for Graph Bisection

We present a novel exact algorithm for the minimum graph bisection problem, whose goal is to partition a graph into two equally-sized cells while minimizing the number of edges between them. Our algorithm is based on the branch-and-bound framework and, unlike most previous approaches, it is fully combinatorial. Besides introducing stronger lower bounds, we propose a new decomposition technique that contracts entire regions of the graph without losing optimality guarantees. In practice, our algorithm works particularly well on instances with relatively small minimum bisections, solving large real-world graphs (with tens of thousands to more than a million vertices) to optimality.
Joint work with Daniel Delling, Daniel Fleischman , Andrew Goldberg, and Ilya Razenshteyn.

A forward-backward single-source shortest paths algorithm

We describe a new forward-backward variant of Dijkstra's and Spira's Single-Source Shortest Paths (SSSP) algorithms. While essentially all SSSP algorithms only scan edges forward, the new algorithm scans some edges backward. The new algorithm assumes that edges in the out-going and incoming adjacency lists of the vertices appear in non-decreasing order of weight. The running time of the algorithm on a complete directed graph on $n$ vertices with independent exponential edge weights is $O(n)$, with very high probability. This improves on the previously best result of $O(n\log n)$, which is best possible if only forward scans are allowed, exhibiting an interesting separation between forward-only and forward-backward SSSP algorithms.
Joint work with David Wilson.