Download the above schedule as a .pdf.
Following is a list of confirmed speakers. Apart from these, 20 German and 10 Indian students would make presentations of 15 minutes each.
 Ravindran Balaraman [Biography]
Ravi is an associate professor at the Department of Computer Science and Engineering at the Indian Institute of Technology Madras. He completed Ph.D. at the Department of Computer Science, University of Massachusetts, Amherst. He worked with Prof. Andrew G. Barto on an algebraic framework for abstraction in Reinforcement Learning.
His current research interests span the broader area of machine learning, ranging from Spatiotemporal Abstractions in Reinforcement Learning to social network analysis and Data/Text Mining. Much of the work in his group is directed toward understanding interactions and learning from them.
IIT Madras, India

 Chiranjib Bhattacharyya [Biography]
IISc Bangalore, India
Learning Probabilistic Topic models  A SVD based approach
Discovering topics from large text corpora is an important problem in Text
Analytics. Recently there has been interest in designing algorithms
which can provably recover Topics from a finite number of samples. It is
widely believed that Singular Value Decomposition(SVD) based Algorithms
cannot guarantee recovery of topics.
In this talk we will discuss some recent results which shows that SVD
based algorithms can recover Topics if the data
satisfies some assumptions. We will present empirical evidence in support
of our assumption and also show that
the proposed SVD based procedure outperforms the state of the art.

 Venkatesan Chakaravarthy [Biography]
Venkatesan Chakaravarthy is a member of the high performance computing group
at IBM Research  India. Broadly, he is interested in theoretical computer
science and its applications to areas such as database systems and high
performance computing. His current research focuses on approximation
algorithms for scheduling problems, and developing scalable
algorithms and implementations for graph theoretic problems on
distributed platforms such as IBM BlueGene systems.
IBM Research, India
Scalable Graph Analytics: Single Source Shortest Path and Subgraph Couting
We shall discuss two graph theoretic problems, single source shortest path and
subgraph counting, from the perspective of developing high performance
algorithms for large distributed memory systems.
In the singlesource shortest path problem,
the goal is to find the shortest paths from a source vertex
to all other vertices in a given edge weighted graph.
We describe a parallel algorithm, derived from the BellmanFord and $\Delta$stepping
algorithms. The algorithm employs various pruning techniques such
as edge classification and directionoptimization to reduce internode communication traffic.
Furthermore, load balancing strategies are used to handle higherdegree vertices.
In the largest tested configuration, a synthetic RMAT graph with 250 billion vertices and
four trillion edges on a BlueGene/Q system with half a million cores,
the implementation achieved a processing rate of three Trillion Edges Per Second (TTEPS),
a four orders of magnitude improvement over the best published results.
In the subgraph counting problem, the goal is to count the number of
occurrences of a small query (say, less than 10 nodes) in a large data graph
(millions of vertices). Many important special cases (e.g. triangles, trees,
$4$ and $5$ node queries) have received significant attention.
Color coding has been proposed as a general and powerful algorithmic technique
for subgraph counting. The technique has been shown to be effective in several
applications, but scalable distributed implementations are only known for
the special case of tree queries (i.e. queries of treewidth one).
We describe the first efficient distributed implementation
for color coding that goes beyond tree queries: our
algorithm applies to any query graph of treewidth 2.
The algorithm structures the computation to work around
high degree vertices in the data graph, and achieves good
runtime and scalability on a diverse collection of data and query graph pairs.

 Prasad Deshpande [Biography]
Prasad M. Deshpande is the CTO and Cofounder of Iqlect, a startup in the area of real time analytics. Prior to this, he was a Senior Technical Staff Member and Manager at IBM Research  India. His areas of expertise lie in data management, specifically data integration, OLAP, data mining and text analytics. He received a B. Tech in Computer Science and Engineering from IIT, Bombay and M.S. and Ph.D. degrees in Database Systems from the University of Wisconsin, Madison. He is an ACM Distinguished Scientist and was a member of the IBM Academy of Technology. His current focus is in the areas of big data and real time analytics. He has more than 40 publications in reputed conferences and journals and 14 patents issued. He has served on the Program Committees of many conferences, as a PC member and PC CoChair.
IBM Research Bangalore, India
Discovering Big Data
Data discovery deals with the problem of discovering useful data from a proliferation of different types and sources of data. Businesses are looking for rapidly available, differentiating insights gleaned from sources such as proprietary databases, social media, and commercially and publicly available datasets. However, a major block to using such datasets is that the schema and semantics of these datasets is not known beforehand. Further, the data could be various types such as structured, unstructured or semistructured. The exact analysis to be run on the data is also not known beforehand. There is a need to support adhoc selfservice analytics on such large collections of data. To achieve this, it is necessary to catalog, curate and govern these assets so they can be found, understood and reused by the enterprise. In this talk, I will describe the BRIDGE data discovery system that we built at IBM to automatically discover rich relationships between different data assets and enriches the metadata so that the right datasets can be found when required. Further, I will also touch upon some real time scenarios where we may need to discover changing characteristics of streaming data.

 Sumit Ganguly [Biography]
Sumit Ganguly completed his B.Tech from IIT Kanpur in 1987 and MS and PhD from the University of Texas at Austin in 1992. He was an Assistant Professor in Computer Science at Rutgers University for a few years before joining IIT Kanpur in 1997. He has worked in parallel and deductive database systems, query optimization and now works in data stream algorithms.
IIT Kanpur, India
Estimating High Frequency Moments of Data Streams
In the data streaming model, data in the form of a large (and possibly interminable) sequence of updates of the form (i,v) arrive at a server, where, i denotes an item from a domain of possible items (IP addresses, pairs of IPs, etc.) which is abstracted as {1,2, …, n} and v is the change in the frequency of i. The frequency is an ndimensional vector f whose ith coordinate at an instant is the sum of the changes to the frequency of i made by the updates that have arrived till this instant. This model is known as the turnstile model for data streaming. In this model, an algorithm may use sublinear memory to store a summary of the data. The data is also processed as it arrives, i.e., in an online fashion. A query on the data stream may be answered by only using the summary data stored.
This model is useful for rapid prediction and monitoring applications. An influential problem in this area is the estimation of the p th frequency moment F_p defined as the pth power of the absolute value of the frequencies (i.e., \norm{f}_p^p). The estimation problem is to compute an estimate \hat{F}_p for Fp that is within a multiplicative factor of (1 \pm \epsilon) of Fp with confidence 7/8, where, \epsilon is a given parameter. The problem has been studied substantially in the literature. We present a summary of the developments and present a recent algorithm.
For $0 < \epsilon \le 1$, the algorithm uses space $O( n^{12/p} \epsilon^{2} +
n^{12/p} \epsilon^{4/p} \log (n))$ words. This improves over the current bound of $O(n^{12/p} \epsilon^{24/p} \log (n))$ words by Andoni et. al. in \cite{ako:arxiv10}. Our space upper bound matches the lower bound of Li and Woodruff \cite{liwood:random13} for $\epsilon = (\log (n))^{\Omega(1)}$ and the lowerbound of Andoni et. al. \cite{anpw:icalp13} for $\epsilon = \Omega(1)$.

 George Karypis [Biography]
George Karypis is an ADC Chair of Digital Technology Professor at the Department of Computer Science & Engineering at the University of Minnesota, Twin Cities. His research interests spans the areas of data mining, high performance computing, information retrieval, collaborative filtering, bioinformatics, cheminformatics, and scientific computing. His research has resulted in the development of software libraries for serial and parallel graph partitioning (METIS and ParMETIS), hypergraph partitioning (hMETIS), for parallel Cholesky factorization (PSPASES), for collaborative filteringbased recommendation algorithms (SUGGEST), clustering high dimensional datasets (CLUTO), finding frequent patterns in diverse datasets (PAFI), and for protein secondary structure prediction (YASSPP). He has coauthored over 250 papers on these topics and two books (“Introduction to Protein Structure Prediction: Methods and Algorithms” (Wiley, 2010) and “Introduction to Parallel Computing” (Publ. Addison Wesley, 2003, 2nd edition)). In addition, he is serving on the program committees of many conferences and workshops on these topics, and on the editorial boards of the IEEE Transactions on Knowledge and Data Engineering, ACM Transactions on Knowledge Discovery from Data, Data Mining and Knowledge Discovery, Social Network Analysis and Data Mining Journal, International Journal of Data Mining and Bioinformatics, the journal on Current Proteomics, Advances in Bioinformatics, and Biomedicine and Biotechnology.
University of Minnesota, USA
Recent Advances in Recommender Systems and Future Directions
Recommender systems are designed to identify the items that a user will like or find useful based on the user’s prior preferences and activities. These systems have become ubiquitous and are an essential tool for information filtering and (e)commerce. Over the years, collaborative filtering, which derive these recommendations by leveraging past activities of groups of users, has emerged as the most prominent approach for solving this problem. Among the multitude of methods that have been developed, user and itembased nearestneighbor approaches are the simplest to understand and are easily extended to capture different user behavioral models and types of available information. However, in their classical forms, the performance of these methods is worse than latentspace approaches.
This talk presents an overview of recent methodological advances in developing nearestneighborbased recommender systems that have substantially improved their performance. The key components in these methods are: (i) the use of statistical learning to estimate from the data the desired useruser and itemitem similarity matrices, (ii) the use of lowerdimensional representations to handle issues associated with sparsity, (iii) the combination of neighborhood and latent space models, and (iv) the direct incorporation of auxiliary information during model estimation. The talk will provide illustrative examples for these methods in the context of itemitem nearestneighbor methods for rating prediction and TopN recommendation. In addition, the talk will present an overview of exciting new application areas of recommender systems along with the challenges and opportunities associated with them.

 Stefano Leonardi [Biography]
Stefano Leonardi is Full Professor of Computer Science at Sapienza University of Rome. His research focuses on online and approximation algorithms, web algorithmics and data mining, economics and computation. He is a Senior Research Fellow, Sapienza School for Advanced Studies, and won a Google Focused Award 2014 on Algorithms for largescale data analysis. He serves on the editorial board the ACM Transactions on Algorithms.
Sapienza University of Rome, Italy
Robust clustering and ranking for largescale datasets
This talk will present theoretical and experimental work on algorithms for robust clustering and ranking for largescale datasets. The first part of the talk will present algorithms for universal hierarchical clustering that are robust against outliers. The second part of the talk will present similarity ranking methods that can be efficiently composed at query time.

 Sachin Lodha [Biography]
Sachin Lodha is part of TCS’s Corporate Technology Office and works out TCS Innovation Labs  TRDDC, Pune. He has led and shaped TCS’s Data Privacy R&D Program right from its inception in early 2005.
Sachin Lodha graduated with a B.Tech. in Computer Science and Engineering from the Indian Institute of Technology, Bombay, in 1996 and received his Ph.D. in Computer Science from Rutgers University, USA, in 2002. Currently he is a member of TCS’s Corporate Technology Council, and also an ACM India Eminent Speaker.
TCS Innovation Labs Pune, India
How to DeIdentify Big Data
In today's hyper networked world with global data flows, almost all major business and technology trends, then be it Big Data, Cloud Computing, Mobility, BYOD, or Internet of Things, require deep privacy underpinnings. It has become increasingly apparent that unless people’s privacy requirements are holistically satisfied, neither the existing businesses would be able to sustain nor new ventures would take off.
In this talk we begin by observing that security and privacy are fundamentally different notions. While security paradigm assumes a clear separation between users and attackers, in privacy paradigm users are attackers too, depending on the use intent, and therefore security controls such as standard encryption based mechanisms do not suffice!
Further we discuss the major goal of data privacy research, that is, to find the right balance between the two extremes of fully disclosed and completely withheld data that preserves both data privacy and its utility, and thus enable data sharing.
We then deliberate on two major privacy frameworks, namely, differential privacy and kanonymity. We find that the kanonymity framework is more suitable for several big data contexts that we consider, but it requires us to make the right choice for k, to accurately identify quasiidentifiers, and to design efficient algorithms for making the given dataset kanonymous with minimal impact on data utility for the given application context. We will present some key results for the same.
Finally we close the talk with a brief overview of TCS Data Privacy Suite that provides efficient and scalable technology for achieving big data privacy.

 Ulrich Meyer [Biography]
Ulrich Meyer is a full professor of Algorithm Engineering at Goethe University Frankfurt. He obtained his Ph.D. in Computer Science from the Saarland University Saarbrücken in 2002. Before joining Goethe University in 2007 he was a Postdoc, Research Associate, and senior researcher (at the level of Associate Professor) at MaxPlanck Institute for Computer Science. He has also been a Visiting Assistant Professor at Duke University and a Guest Researcher at the Hungarian Academy of Sciences.
His main research area is algorithms for advanced models of computation (e.g. parallel computing and memory hierarchies) with a focus on graph algorithms.
He is currently coordinating the German Research Cluster on Algorithms for big data, funded by the German Research Foundation (DFG).
Goethe University Frankfurt am Main, Germany
Algorithm Engineering for large data sets – some examples.
Basic algorithmic research traditionally assumed some variant of the “von Neumann” model of computation with a single processor and uniform memory. However, more advanced models are by now
an important established part of algorithmic research because many of
the challenges in modern computer science have to do with communication, parallel computing, and memory hierarchies. Especially
in processing large data sets neglecting machine architecture easily becomes a major performancekiller.
In the talk I will review some of our research on graphalgorithms for data residing on secondary memory, and energyefficient sorting using solidstate disks.

 Henning Meyerhenke [Biography]
Henning Meyerhenke is an Assistant Professor (Juniorprofessor) at the Institute of Theoretical Informatics at Karlsruhe Institute of Technology, Germany, since October 2011. From October 2010 to September 2011 Henning was a postdoctoral researcher in Georgia Tech's College of Computing. Henning received his Diplom degree in Computer Science from FriedrichSchillerUniversity Jena, Germany, in 2004 and his Ph.D. (with highest distinction) in Computer Science from the University of Paderborn, Germany, in 2008. After his graduation he was a Research Scientist at NEC Laboratories Europe in Sankt Augustin, Germany, and a Postdoctoral Researcher at the University of Paderborn until September 2010.
His main research interests are in parallel algorithm engineering for massive data sets in three main application areas: Combinatorial scientific computing (graph partitioning, load balancing, multilevel methods), network analysis (community detection, network metrics in dynamic scenarios, NetworKit library), and in algorithmic problems with connection to the life sciences (such as sequence assembly). Recently Henning has acquired significant funding by DFG, BMBF, and MWK BadenWuerttemberg. Together with his coauthors, Henning received the Best Algorithms Paper Award at the 22nd IEEE International Parallel and Distributed Processing Symposium (IPDPS'08).
Karlsruher Institut für Technologie, Germany
Scalable algorithms for analyzing large networks with NetworKit
Complex networks are equally attractive and challenging targets for data mining. Novel algorithmic solutions, including parallelization, are required to handle data sets containing billions of connections. We present NetworKit, an opensource software toolkit for efficient graph algorithms and the analysis of such massive complex networks. NetworKit is a hybrid combining the performance of kernels written in C++ with a convenient Python frontend. The package targets sharedmemory platforms with OpenMP support.
A few algorithm classes from NetworKit will be presented in some detail, in particular algorithms for community detection and centrality computations. In comparison with related software, we propose NetworKit as a package geared towards large networks and satisfying three important criteria: High performance, interactive workflows, and integration into an ecosystem of tested tools for data analysis and scientific computation.

 Rajeev Raman [Biography]
After defending my PhD thesis in October 1991, I took up a Postdoctoral Fellowship in the Algorithms and Complexity Group at the MaxPlanckInstitut für Informatik, which is headed by Kurt Mehlhorn. In January 1993 I joined the University of Maryland Institute for Advanced Computer Studies, as a Research Associate working with Uzi Vishkin. Crossing the Atlantic yet again, I joined the Algorithm Design Group at King's College London in 1994. I have been at Leicester since January 2001 and was the Head of the Computer Science Department from 2003 through 2006.
I've been a visiting researcher at the MaxPlanckInstitut, Courant Institute, Rutgers, HKUST and Kyoto University.
University of Leicester, UK
Succinct Data Structures for Data Mining
We often use "Big Data" techniques when most users only have "big data". "big data" can often be handled efficiently by applying standard algorithms developed, tried and tested but coupled with succinct data structures to reduce the memory usage of such algorithms, thus allowing the "big data" to be processed in memory. I will introduce succinct data structures and some recent applications to "big data".

 Sayan Ranu [Biography]
Sayan Ranu is an Assistant Professor at IIT Madras since January, 2014. His research interests include spatiotemporal data analytics, graph indexing and mining, and bioinformatics. Prior to joining IIT Madras, he was a researcher at IBM Research. He obtained his PhD from University of California, Santa Barbara (UCSB) in March 2012. He was a recipient of the "Distinguished Graduate Research Fellowship" at UCSB. He obtained his Bachelor of Science from Iowa State University, where he received the “President’s top 2% of the class” award.
IIT Madras
Mining Communication Motifs from Dynamic Networks
A fundamental problem in behavioral analysis of human interactions
is to understand how communications unfold. In this talk,
we will analyze this problem by mining Communication motifs from dynamic
interaction networks. A communication motif is a recurring
subgraph that has a similar sequence of information flow. Mining
communication motifs requires us to explore the exponential
subgraph search space where existing techniques fail to scale. To
tackle this scalability bottleneck, we will discuss a technique called
COMMIT. COMMIT converts a dynamic graph into a database of
sequences. Through careful analysis in the sequence space, only a
small portion of the exponential search space is accessed to identify
regions embedding communication motifs. Extensive experiments
on three different social networks show COMMIT to be up to two
orders of magnitude faster than baseline techniques. Furthermore,
qualitative analysis demonstrate communication motifs to be effective
in characterizing the recurring patterns of interactions while
also revealing the role that the underlying social network plays in
shaping human behavior.

 Uday Reddy [Biography]
Uday Reddy is an Assistant Professor in the Department of Computer
Science and Automation at the Indian Institute of Science, Bangalore, India. His research interests are in the development of programming and compiler/runtime technologies for multicore architectures with an emphasis on high performance and automatic parallelization, the design of domainspecific compilers, and the polyhedral compiler framework. He recently received a Google Research Award (2015) for ongoing research and development on PolyMage. He has also received several other grants and awards for his research, including ones from Intel Labs, National Instruments R&D, AMD, and CDAC, an NVIDIA CUDA research center award, and an INRIA Associate Team award. Before joining IISc, he was with the Advanced Compiler Technologies group at the IBM T.J. Watson Research Center, Yorktown Heights, New York. He received his PhD in Computer Science and Engineering from the Ohio State University in 2008, and his BTech in Computer Science and Engineering from the Indian Institute of Technology, Madras in 2004.
IISc Bangalore, India
Programming and Compiler Technologies for Big Data: efficiently translating algorithms into highperformance code
This talk will present challenges involved in translating big data algorithms into highperformance code in a manner that is also productive for programmers. Big data has a strong connection with highperformance computing due to the need to exploit parallelism and locality when dealing with large amounts of data. We will first look at the relative strengths and weaknesses of various programming approaches: ultra highlevel languages, domainspecific languages and code generators, tuned librarybased, and completely manual.
An attractive solution that simultaneously provides high programmer productivity and high parallel performance is the design of new domainspecific languages (DSL) and their compilers. I will present our experience with the application domain of image processing pipelines as a motivating example, and emphasize the need for such solutions for emerging computation domains of interest to big data such as deep learning. A short video demo will also be presented.

 Anand Srivastav [Biography]
Anand Srivastav studied Mathematics and Physics at the University of
Muenster, Germany from 1978  1984. He completed the PhD in Mathematics
with a thesis in Functional Analysis at the University of Muenster in Spring 1988.
Thereafter, he moved joined the Research Institute of Discrete Mathematics, Uiversity of Bonn,
from 1988  1993. After academic stays as a visitig faculty at the University of
Minnesota, Yale University and New York University, he joined the Free University
of Berlin in 1994, and in 1995 the Humboldt University of Berlin. In Berlin he completed his
Habilitation in Computer Science with a thesis on
,, Derandomzied Algorithms in Combinatorial Optimziation´ in 1996. Since 1997 he
is professor and chair for Discrete Optimization at Kiel University.
From 2000  2005 he has been the speaker
of the DFG research training group 357 (,,Graduiertekolleg´) ,,Efficient Algorithms and
Multiscale Methods´'at Kiel University. Since 2007 he is PI in the DFG cluster of excellence
,,The Future Ocean´ and since 2010 he is speaker of the research platforms of the cluster.
In 2013 he held the guest professorship at the IndoMaxPlanck Center for Computer Science
at IIT Delhi.
His research interests
are combinatorial optimization, discrepancy theory, randomized and derandomized algorithms,
algorithm engineering and big data applications in marine science and life science, with
a personal emphasis on the IndoGerman cooperation in computer science and mathematics.
Kiel University, Germany
Algorithmic Foundation of Genome Assembly
We give an introduction to genome assembly, a fundamental task in
biology and medicine. Using sequencing machines, huge amounts of data (TB or PB)
regarding the genome of one or more particular life forms are
gathered. This data must be evaluated, with the goal of determining the
correct genomic sequences present in the species under consideration.
The first giant sucess has been the assembly of the human genome
by C. Venter, M.D. Adams, E. W. Meyers et. al, Science 2001.
This work needed almost 10 years and supercomputing facilities.
Today, there is a demand for very fast assembly algorithms, even
for the size of the human genome, but running on smaller platforms, even on PCs.
We show how probabilistic data structures help to filter out redundant
information. Then, in the main part of the presentation, we turn to the
longest path problem. This is a classical problem in combinatorial
optimization and a prototype for algorithmic tasks that arise in genome
assembly. We discuss known approaches and then turn to the Big Data
aspect. An new algorithm for the longest path problem in the graph streaming
model is presented. We prove a linear peredge processing time and show
experimental evidence that points towards a competitive solution quality
obtained within no more than 10 passes over the input, which is extremly small.
(joint work with Lasse Kliemann, Christian Schielke, and Axel Wedemeyer,
within the DFG SPP 1736 ,,Algorithms for Big Data´)

 Manik Varma [Biography]
Manik Varma is a researcher at Microsoft Research India and an adjunct professor of computer science at the Indian Institute of Technology (IIT) Delhi. His research interests lie in the areas of machine learning, computational advertising and computer vision. He has served as an area chair for machine learning and computer vision conferences such as ACCV, CVPR, ICCV, ICML, ICVGIP, IJCAI and NIPS. Classifiers that he has designed are running live on millions of devices around the world protecting them from viruses and malware. He has been awarded the Microsoft Gold Star award, won the PASCAL VOC Object Detection Challenge and stood first in chicken chess tournaments and Pepsi drinking competitions. Manik is also a failed physicist (BSc St. Stephen's College, David Raja Ram Prize), theoretician (BA Oxford, Rhodes Scholar), engineer (DPhil Oxford, University Scholar) and mathematician (MSRI Berkeley, Postdoctoral Fellow).
Microsoft Research, India
Extreme Classification: A New Paradigm for Ranking & Recommendation
The objective in extreme multilabel classification is to learn a classifier that can automatically tag a data point with the most relevant subset of labels from a large label set. Extreme multilabel classification is an important research problem since not only does it enable the tackling of applications with many labels but it also allows the reformulation of ranking and recommendation problems with certain advantages over existing formulations.
Our objective, in this talk, is to develop an extreme multilabel classifier that is faster to train and more accurate at prediction than the stateoftheart Multilabel Random Forest (MLRF) algorithm [Agrawal et al. WWW 13] and the Label Partitioning for Sublinear Ranking (LPSR) algorithm [Weston et al. ICML 13]. MLRF and LPSR learn a hierarchy to deal with the large number of labels but optimize task independent measures, such as the Gini index or clustering error, in order to learn the hierarchy. Our proposed FastXML algorithm achieves significantly higher accuracies by directly optimizing an nDCG based ranking loss function. We also develop an alternating minimization algorithm for efficiently optimizing the proposed formulation. Experiments reveal that FastXML can be trained on problems with more than a million labels on a standard desktop in eight hours using a single core and in an hour using multiple cores.

 Dorothea Wagner [Biography]
Dorothea Wagner heads the Institute of Theoretical Informatics at the Karlsruhe Institute of Technology. She earned her PhD 1986 from RWTH Aachen, and her habilitation 1992 from TU Berlin. Her research interests are in the field of graph algorithms and algorithm engineering with a focus on traffic optimization, social network analysis and network visualization. In 2012 she received the Google Focused Research Award for the project ""Next Generation Route Planner"". She is a member of several editoral boards and scientific advisory committees. From 2007 to 2014 she was vice president of the German Research Foundation (DFG). Since 2015 she is a member of the German Council of Science and Humanities.
Karlsruher Institut für Technologie, Germany
Route Planning for TimeDependent Transportation
Nowadays, route planning systems belong to the most frequently used
information systems. The algorithmic core problem of such systems,
is the classical shortest paths problem that can be solved by Dijkstra's
algorithm which, however, is too slow for practical scenarios.
Algorithms for route planning in transportation networks have recently undergone a rapid development, leading to methods that are up to several million times faster than Dijkstra’s algorithm.
However, dealing with timedependence is still a challenge.
This talk provides a condensed survey of recent advances in
algorithms for route planning in transportation networks. In
particular, we will discuss timedependent scenarios including the process of building a timedependent routing graph from raw road data like OpenStreetMap.

 David Woodruff [Biography]
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.
IBM Almaden Research Center, USA
Sketching as a Tool for Linear Algebra and Recent Developments
We give near optimal algorithms for regression, low rank approximation, and robust variants of these problems. Our results are based on the sketch and solve paradigm, which is a tool for quickly compressing a problem to a smaller version of itself, for which one can then run a slow algorithm on the smaller problem. These lead to the fastest known algorithms for fundamental machine learning and numerical linear algebra problems, which run in time proportional to the number of nonzero entries of the input. We first give algorithms for least squares regression, and robust variants such as l_p regression and MEstimator loss functions. Then we give algorithms for approximate singular value decomposition, and robust variants such as minimizing sum of distances to a subspace, rather than sum of squared distances. Timepermitting, we also discuss communicationefficient solutions to these problems in distributed environments.

