Bio
Kiyoshi Asai graduated in Department of Applied Mathematics, University of Tokyo in 1983, and its master course in 1985. Then he began to apply HMMs to biological sequences and got Ph.D in 1995. Since then, he developed many algorithms and software tools based on stochastic models for sequence analyses and RNA secondary structure analyses.
He is a Professor of Department of Computational Biology, University of Tokyo since 2003. He founded Computational Biology Research Center of Japan in 2001 and was the director from 2007. He was one of the founding Board of Directors of ISCB, and was the president of Japanese Society for Bioinformatics from 2013 to 2015.

Title

Algorithms on Marginal Distributions of RNA Secondary Structures

Abstract 

The secondary (2D) structures of RNA are important to play their functions. We have developed several algorithms and tools for RNA analyses, including CentroidFold, one of the most accurate predictors of RNA 2D structures.

The probability of each specific 2D structure of an RNA is very small, but the marginal probabilities in its thermodynamic distribution are not necessarily too small. Some marginal probabilities, such as base-paring probabilities, are known to be efficiently computed by engineered dynamic programming (DP). Furthermore, the distributions of the certain type of scores on 2D structures can be efficiently computed by extending DPs.    

Bio
A.B. got a master of science degree in engineering physics at Lund University in 1998. He started pursuing a Ph.D. in algorithm theory at the same university but left academia in 2001 for a job at the local company Anoto. He completed his Ph.D. studies in 2007.

He has since continued working in industry at the companies C Technologies, Flatfrog laboratories, and ARM Ltd. where he is currently employed.

Title

Determinant Sums for Hamiltonicity

Abstract

The best worst case guarantee algorithm to see if a graph has a Hamiltonian cycle, a closed tour visiting every vertex exactly once, for a long time was based on dynamic programming over all the vertex subsets of the graph. In this talk we will show some algebraic techniques that can be used to see if a graph has a Hamiltonian cycle much faster. These techniques utilize sums over determinants of matrices.

In particular we will show how you can find out if an undirected graph has a Hamiltonian cycle much faster, but we will also talk about some partial results for the directed case and modular counting.

Bio
Marek Cygan has obtained his PhD degree in Computer Science at the Institute of Informatics, University of Warsaw, Poland in 2012. After being a researcher at the University of Maryland and a post-doc in IDSIA, Lugano, he returned to the University of Warsaw, where he currently is an assistant professor. Marek Cygan works in various branches of algorithmics, with main focus on parameterized complexity and approximation algorithms.

Title

Approximation algorithms for the k-Set Packing problem      

Abstract

In the k-Set Packing problem we are given a universe and a family of its subsets, where each of the subsets has size at most k. The goal is to select a maximum number of sets from the family which are pairwise disjoint. It is a well known NP-hard problem, that has been studied from the approximation perspective since the 80's. During the talk I will describe the history of progress on both the weighted and unweighted variants of the problem, with an exposition of methods used to obtain the best known approximation algorithms mostly involving local search based routines.

Bio
Giuseppe F. Italiano is Professor of Computer Science at the University of Rome "Tor Vergata". His research interests are in the design, analysis, implementation and experimental evaluation of algorithms and data structures. After receiving a PhD in Computer Science from Columbia University, he was Research Staff Member at the IBM T.J. Watson Research Center, and then full professor at University of Salerno, University of Venice "Ca' Foscari" and University of Rome "Tor Vergata". He is a Fellow of the EATCS. 

Title

2-Connectivity in Directed Graphs 2-Connectivity in Directed Graphs    

Abstract 

We survey some recent results on 2-edge and 2-vertex connectivity in directed graphs. Despite being complete analogs of the corresponding notions on undirected graphs, in digraphs 2-connectivity has a much richer and more complicated structure. For undirected graphs it has been known for over 40 years how to compute all bridges, articulation points, 2-edge- and 2-vertex-connected components in linear time, by simply using depth first search. In the case of digraphs, however, the very same problems have been  much more challenging and have been tackled only recently.

Bio

Volker Markl is a Full Professor and Chair of the Database Systems and Information Management Group at the Technische Universität Berlin (TUB) and an Adjunct Full Professor at the University of Toronto. He is Director of the Intelligent Analytics for Massive Data Research Group at DFKI and Director of the Berlin Big Data Center. In addition, he serves as the Secretary of the VLDB Endowment. His current research interests include new hardware architectures for information management, scalable processing and optimization of declarative data analysis programs, and scalable data science. To date, Volker has presented over 200 invited talks in numerous industrial settings, major conferences, and research institutions worldwide. Furthermore, he has authored and published over 100 research papers at world-class scientific venues. Between 2010-2016, he was Speaker and Principal Investigator of the Stratosphere Research Unit funded by the German Research Foundation (DFG), which resulted in numerous top-tier publications, as well as the Apache Flink big data analytics system. In 2014, he was named one of Germany's leading digital minds (Digitale Köpfe) by the German Informatics Society. Prior to joining TUB, he was a Research Staff Member and Project Leader at the IBM Almaden Research Center in San Jose, California. 

Title

Big Data Management and Scalable Data Science: Key Challenges and (Some) Solutions 

Abstract 

The shortage of qualified data scientists is effectively limiting Big Data from fully realizing its potential to deliver insight and provide value for scientists, business analysts, and society as a whole. Data science draws on a broad number of advanced concepts from the mathematical, statistical, and computer sciences in addition to requiring knowledge in an application domain. Solely teaching these diverse skills will not enable us to on a broad scale exploit the power of predictive and prescriptive models for huge, heterogeneous, and high-velocity data. Instead, we will have to simplify the tasks a data scientist needs to perform, bringing technology to the rescue: for example, by developing novel ways for the specification, automatic parallelization, optimization, and efficient execution of deep data analysis workflows. This will require us to integrate concepts from data management systems, scalable processing, and machine learning, in order to build widely usable and scalable data analysis systems. In this talk, I will present some of our research results towards this goal, including the Apache Flink open-source big data analytics system, concepts for the scalable processing of iterative data analysis programs, and ideas on enabling optimistic fault tolerance.

Bio
Thomas Schlechte was born in 1979 and got his doctoral degree in Natural Sciences at the TU Berlin in 2012. Since 2013, he is working for the ZIB-spinoff company LBW in the field of mathematical optimization and consulting for public and rail transport. He won the Dissertation Prize 2012 (awarded by the German Operations Research Society, GOR) and the Science Award 2012 (awarded by the Society of Merchants and Manufactures of Berlin, VBKI). Since 2014, he is head of the RailLab within the Research Campus MODAL and member of the Board of the International Association of Railway Operations Research. 

Title

Decide & Conquer - The Impact of Optimization on Today's Traffic Systems 

Abstract 

The design and operation of traffic systems typically require the solution of large scale combinatorial optimization problems. The resulting optimization models are often computationally challenging and increasingly so with the integration of more and more details. Extending classical algorithms and algorithm engineering, i.e, the design and the analysis of efficient algorithms, allows us to deal with complex challenges in real world traffic systems. This talk reviews recent progress in this area for various modes of transport, including a micro-macro approach to railway track allocation, a coarse-to-fine column generation approach to rolling stock rotation planning, and a two layer Dijkstra algorithm for the optimization of flight trajectories. The talk will conclude with a powerful heuristic approach for the rostering of toll inspectors on German highways. We present computational results as well as modeling and algorithmic techniques that were crucial to conquer areas for optimization.

Bio
Ola Svensson is a faculty at the School of Computer and Communication Sciences, EPFL.  He is interested in fundamental questions in combinatorial optimization related to the approximability of basic optimization problems, such as clustering, scheduling, and network design problems. His work on the traveling salesman problem received the best paper award at FOCS'11. 

Title

Algorithms with provable guarantees for clustering

Abstract 

In this talk, we give an overview of the current best approximation algorithms for fundamental clustering problems, such as k-center, k-median, k-means, and facility location.  We focus on recent progress and point out several important open problems. For the uncapacitated versions, a variety of algorithmic methodologies, such as LP-rounding and primal-dual method, have been applied to a standard linear programming relaxation. This has given a uniform way of addressing these problems resulting in small  constant approximation guarantees.  In spite of this impressive progress,  it remains a challenging open problem to give tight guarantees.  Moreover, this collection of powerful algorithmic techniques is not easily applicable to the capacitated setting. In fact, there is no simple strong convex relaxation known for the capacitated versions.  As a result, our understanding of these problems is significantly weaker and several fundamental questions remain open.

Bio
Ronald de Wolf is a senior researcher at CWI and full professor at the University of Amsterdam. He obtained his PhD in 2001, advised by Harry Buhrman and Paul Vitanyi, and subsequently spent a year at Berkeley. He works on quantum computing, focusing on algorithms, complexity theory, and the applications of quantum information to other areas. His main results include lower bounds on quantum algorithms, new separations between quantum and classical communication protocols, and lower bounds on linear programs for polytopes in combinatorial optimization. 

Title

On linear and semidefinite programs for polytopes in combinatorial optimization

Abstract 

Combinatorial problems like TSP optimize a linear function over some polytope P. If we can obtain P as a projection from a larger-dimensional polytope with a small number of facets, then we get a small linear program for the optimization problem; if we obtain P as a projection from a small spectrahedron, then we get a small semidefinite program. The area of extension complexity studies the minimum sizes of such LPs and SDPs. In the 1980s Yannakakis was the first to do this, proving exponential lower bounds on the size of symmetric LPs for the TSP and matching polytopes. In 2012, Fiorini et al. proved exponential lower bounds on the size of all (possibly non-symmetric) LPs for TSP. This was followed by many new results for LPs and SDPs, for exact optimization as well as for approximation. We will survey this recent line of work.

Bio
Fabian Kuhn received his M.Sc. and Ph.D. degrees in 2001 and 2005 from ETH Zurich in Switzerland. He spent time as a postdoctoral researcher at Microsoft Research Silicon Valley, at ETH Zurich, and at MIT. In the following, he was an assistant professor at the University of Lugano in Switzerland and in 2012, he joined the University of Freiburg in Germany as a full professor. His research interests include the distributed complexity of basic graph-theoretic problems, as well as the algorithmic foundation of dynamic and wireless networks.  

Title

Developing Robust Wireless Network Algorithms

Abstract 

The exact behavior of a wireless communication signal is influenced by many properties of the environment and wireless signals are therefore almost inherently unpredictable. As a result, wireless communication links are often unstable. In my talk, I will discuss recent attempts to develop more robust wireless network algorithms. I will argue that it makes sense to explicitly allow unreliable and possibly even dynamic behavior in the abstract communication models we use to develop distributed radio network algorithms.