Keynote Speakers

Daniel Delling, Apple Inc.

Thursday, September 7, 13:30–14:30, HS 1

Title: Route planning in transportation networks – from research to practice

Abstract: The last 15 years have seen astonishing progress in the performance of shortest path algorithms for transportation networks. In particular, for road networks, modern algorithms can be up to seven orders of magnitude faster than standard solutions. Since these algorithms enable several new applications, many of them have found their way into systems serving hundreds of millions of users every day. This talk highlights key techniques, discusses their impact on the industry, and provides an outlook on upcoming challenges.

Biography: Daniel Delling is a researcher and architect at Apple Inc. in Cupertino, USA. His research focuses on the design, analysis, and implementation of efficient algorithms and data structures. Before joining Apple, he received his PhD from the Karlsruhe Institute of Technology and was a Researcher at Microsoft Research Silicon Valley.

Babak Falsafi, EcoCloud and EPFL

Tuesday, September 5, 13:30–14:30, HS 1

Title: The clouds have taken over, but algorithms are here to save the day

Abstract: Cloud providers are building infrastructure at unprecedented speeds. We have witnessed the emergence of data-centric information technology in almost every aspect of our life from commerce, healthcare, entertainment, governance to scientific discovery. The demand for processing, communicating and storing data has grown faster than conventional growth in digital platforms. Meanwhile the conventional silicon technologies we have relied on for the past several decades leading to the exponential growth in IT have slowed down. In light of this increase in demand on data-centric IT and the diminishing returns in platform scalability, our future increasingly relies on algorithms to save the day and enable a continued growth in IT. In this talk, I will motivate the grand challenges in scaling digital platforms and data-centric technologies, then present opportunities for hand-in-hand collaboration of algorithms and platforms.

Biography: Babak is Professor in the School of Computer and Communication Sciences and the founding director of the EcoCloud research center at EPFL. He has worked on server architecture for quite some time and has had contributions to several industrial platforms including the WildFire/WildCat family of multiprocessors by Sun Microsystems (now Oracle), memory system technologies for IBM BlueGene/P and Q, and server evaluation methodologies in use by AMD, HP and Google (PerfKit). His recent work on scale-out server processor design lays the foundation for Cavium ThunderX. He is a fellow of ACM and IEEE.

Slides of Babak Falsafi’s keynote talk can be found here.

Jie Gao, Stony Brook University

Friday, September 8, 9:00–10:00, HS 1

Title: New challenges in distributed sensing, processing and query of spatial data

Abstract: The vision of networked sensors in a ubiquitous manner has motivated the development of new algorithms on distributed sensing, processing and query of spatially and temporally separated data in the past 15 years. As smart sensing continues to spread in everyday living space, new challenges in the frontier of data privacy emerge. In this talk I would like to discuss new problems and solutions on distributed sensing and processing of location and trajectory data, which protect personally sensitive information.

Biography: Jie Gao is an Associate Professor at Computer Science department, Stony Brook University. She received BS from the special class for the gifted young program at University of Science and Technology of China in 1999 and Ph.D in computer science from Computer Science department, Stanford University in 2004. She received NSF Career award in 2006, IMC best paper award in 2008 and multiple awards at Stony Brook CS department on Excellence in Research. She has published over 120 papers on sensor/wireless networks, computational geometry and social network analysis. She has served on the editorial board of IEEE Transactions on Automation Science and Engineering and currently serves on the editorial board of ACM Transactions on Sensor Networks and Journal of Discrete Algorithms.

Fabrizio Grandoni, University of Lugano

Wednesday, September 6, 9:00–10:00, HS 1

Title: A measure and conquer approach for the analysis of exact algorithms

Abstract: Branch-and-reduce is one of the most common techniques to design exact (exponential-time) algorithms for NP-hard problems. The basic idea is to branch on a collection of “smaller” subproblems which are solved recursively. The traditional way to upper bound the running time of such algorithms is to lower bound the decrease of the “size” of each subproblem with respect to the original one. Here the size of a subproblem is traditionally measured according to the target parameter in terms of which one wishes to express the final running time (e.g., the number of nodes or edges in the input graph, the number of clauses in a CNF formula, etc.). The basic idea behind the Measure and Conquer technique is to use a non-standard measure of subproblems size, in order to implicitly exploit configurations where an “expensive” branching step leads to a “simpler” collection of subproblems. A smartly designed measure can lead to a dramatic reduction of the running time bound (without changing the algorithm!). In this talk I will illustrate Measure and Conquer with a few examples coming from my past work on this topic and from some more recent developments.

The talk is based on the paper A measure and conquer approach for the analysis of exact algorithms by Fedor V. Fomin, Fabrizio Grandoni, and Dieter Kratsch who won the EATCS-IPEC Nerode Prize 2017.

Biography: Fabrizio Grandoni received a Ph.D. in Computer Science from the University of Rome Tor Vergata in 2004. Currently he is a Research Professor at IDSIA, University of Lugano. Grandoni’s research is focused on the design and theoretical analysis of algorithms and data structures. In 2010 his work on Steiner tree approximation received the Best STOC Paper Award. In 2011 he was the recipient of an ERC Starting Grant.

David Mount, University of Maryland

Wednesday, September 6, 13:30–14:30, HS 1

Title: Approximation algorithms for geometric proximity problems

Abstract: I will present an overview of recent developments in the design of efficient approximation algorithms for geometric proximity problems. These include polytope membership, nearest neighbor searching, Euclidean minimum spanning trees, low-complexity polytope approximation, and coresets. I will discuss how new sampling techniques arising from classical concepts such as Delone sets, Macbeath regions, and the Hilbert geometry have led to a number of new results, which are simple, general, implementable, and provably close to optimal.

Biography: David Mount is a professor in the Department of Computer Science at the University of Maryland with a joint appointment at the University’s Institute for Advanced Computer Studies (UMIACS). He received his Ph.D. from Purdue University in Computer Science in 1983, and started at the University of Maryland in 1984. In 2001 he was a visiting professor at the Hong Kong University of Science and Technology.
He has written over 150 research publications on algorithms for geometric problems, particularly problems with applications in image processing, pattern recognition, information retrieval, and computer graphics. He currently serves on the editorial boards of a number of journals, including ACM Transactions on Spatial Algorithms and Systems, ACM Trans. on Mathematical Software, Computational Geometry: Theory and Applications, International Journal of Computational Geometry & Applications. He was the conference chair for the 24th Annual Symposium on Computational Geometry in 2008. He has served on the program committees of many of the major conferences in his area, and he served as the program committee co-chair for the 19th ACM Symposium on Computational Geometry in 2003 and the Fourth Workshop on Algorithm Engineering and Experiments in 2002. He is currently serving on the Computational Geometry Steering Committee.

Kirk Pruhs, University of Pittsburgh

Thursday, September 7, 9:00–10:00, HS 1

Title: The Itinerant List Update Problem

Abstract: I will introduce a variation of the online List Update Problem, which we call the Itinerant List Update Problem (ILU). The main difference between ILU and the standard list update problem is that in ILU the read head is not required to return to a home position between accesses. The motivation for considering ILU arises from track management within Domain Wall Memory (DWM), a promising new memory technology. I will explain DWM technology, discuss how ILU differs algorithmically from the standard list update problem, and explain what we know about the offline and online versions of ILU. This is joint work with Neil Olver, Kevin Schewior, Rene Sitters and Leen Stougie.

Biography: Kirk Pruhs is a professor of Computer Science at the University of Pittsburgh. He received a BS in Mathematics and Computer Science from Iowa State University and a PhD in Computer Science from the University of Wisconsin-Madison. His research interests include algorithmic problems related to green computing, fair allocation, resource management, and scheduling.

David Woodruff, Carnegie Mellon University*

Monday, September 4, 13:30–14:30, HS 1

Title: Sketching for geometric problems

Abstract: I will give an overview of the technique of sketching, or randomized data dimensionality reduction, and its applications to fundamental geometric problems such as projection (regression) onto flats and more general objects, as well as low rank approximation and clustering applications.

Biography: David Woodruff is an associate professor at Carnegie Mellon University. Until recently* he has been at IBM Almaden Research Center from August, 2007- August, 2017, which he joined after completing his Ph.D. at MIT in theoretical computer science.  His research interests include communication complexity, data stream algorithms, machine learning, numerical linear algebra, sketching, and sparse recovery. He is the recipient of the 2014 Presburger Award and Best Paper Awards at STOC 2013 and PODS 2010. At IBM he was a member of the Academy of Technology and a Master Inventor.

*(Before August 30, 2017): David Woodruff joined IBM Almaden Research Center in 2007 right after completing his Ph.D. at MIT in theoretical computer science. He has been at IBM Almaden ever since. His research interests include communication complexity, data stream algorithms, machine learning, numerical linear algebra, sketching, and sparse recovery. He is the recipient of the 2014 Presburger Award and Best Paper Awards at STOC 2013 and PODS 2010. At IBM he is a member of the Academy of Technology and a Master Inventor.

Fabrizio Grandoni, Jie Gao, David Mount, Daniel Delling.

Daniel Delling, Stefan Szeider, David Woodruff, Christian Sohler, Babak Falsafi, David Mount, Martin Nöllenburg.