Schedule for Fall 2018
Official course name: Perspectives in Informatics 5, Graduate School of Informatics
Unless noted otherwise, all talks Thursday 14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus

 Francois Le Gall(Kyoto University), Random Walks and Space Complexity

 Francois Le Gall(Kyoto University), Quantum Algorithms for Algebraic and GraphTheoretic Problems

 David Avis(Kyoto University and McGill University), All Meals for a Dollar and Other Vertex Enumeration Problems

 Oliver Friedmann(Ziggeo), Scaling Realworld Highperformance Applications hosted by David Avis

 Yihong Zhang(Kyoto University), Statistical Machine Learning and Its Application on Social Media hosted by Adam Jatowt

 Kokichi Sugihara(Meiji University), Mathematics of Impossible Objects hosted by David Avis

 Raj Dabre(NICT), Generative Adversarial Network (tentative) hosted by Fabien Cromieres

 Fabien Cromieres(Kyoto University), Neural Machine Translation

 Fabien Cromieres(Kyoto University), Word Embeddings

 Fabien Cromieres(Kyoto University), Automatic Image Captioning

 Francois Le Gall(Kyoto University), Introduction to Distributed Computing

 Adam Jatowt(Kyoto University), Acrosstime Term Similarity Computation and Explanation

 Adam Jatowt(Kyoto University), Estimating Document Comprehensibility

 David Avis(Kyoto University and McGill University), mts: A Framework for Parallel Tree Search

 Adnan Sljoka(Kwansei Gakuin University), Rigidity Theory and its Applications to Protein Function Analysis hosted by David Avis
Detailed Information and Abstracts
October 4
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Francois Le Gall, Kyoto University
Title: Random Walks and Space Complexity
Abstract: The concept of random walk is an extremely versatile and powerful paradigm in the field of randomized algorithms. In the first part of this talk I will review the concept of random walks and describe several wellknown applications concerning the design of spaceefficient algorithms (e.g., how to test if an undirected graph is connected in logarithmic space). In the second part of this talk I will present new results about spaceefficient algorithms for solving linear systems of equations based on random walks.
Bio: Francois Le Gall is an Associate Professor in the Department of Communications and Computer Engineering, Graduate School of Informatics, Kyoto University. He received his PhD in 2006 from the University of Tokyo. His research interests include algorithms, computational complexity and quantum computation.
October 11
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Francois Le Gall, Kyoto University
Title: Quantum Algorithms for Algebraic and GraphTheoretic Problems
Abstract: In this talk I will present recent developments on quantum algorithms for problems from linear algebra and graphtheoretic problems. I will first introduce the concept of quantum algorithms, and in particular the powerful technique known as “quantum search”, and describe several fundamental applications. Most examples will deal with problems from linear algebra (computing the product of two matrices, inverting a matrix,…), and their natural applications to graphtheoretic problems.
October 18
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
David Avis, Kyoto University and McGill University
Title: All Meals for a Dollar and Other Vertex Enumeration Problems
Abstract: Linear programming is a powerful modelling tool that has wide application and is very efficient in practice. However it provides only the optimum solution to a linear program. How can one obtain a set of near optimum solutions, say those within 1% of the optimum? This is an example of a vertex enumeration problem. I will introduce this problem, give some examples such as computing all meals for a dollar, and discuss its solution using the reverse search technique discovered by the speaker and Komei Fukuda.
Bio: David Avis is Professor Emeritus in the School of Computer Science at McGill University and a researcher in the Department of Intelligence Science and Technology at Kyoto University. He received his PhD in 1977 from Stanford University in Operations Research. His research interests include discrete optimization, polyhedral computation and parallel computation.
October 25
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Oliver Friedmann, Ziggeo
Title: Scaling Realworld Highperformance Applications
Abstract: Scaling realworld highperformance applications poses great difficulties on the technical infrastructure as well as on the architecture of distributed applications. We discuss how to architect and structure a highperformance web video application by distributing the computational requirements across looselycoupled microservices and by reducing bottlenecks through the use of independent edge computational resources and sharding NoSQL database systems.
Bio: Oliver Friedmann is a German computer scientist and mathematician known for his work on parity games and the simplex algorithm. He is CTO and cofounder of Ziggeo, a cloudbased video technology company. Friedmann earned his doctorate's degree from the Ludwig Maximilian University of Munich in 2011 under the supervision of Martin Hofmann and Martin Lange. He won the Kleene award for showing that stateoftheart policy iteration algorithms for parity games require exponential time in the worst case. His seminal body of work on lower bounds in convex optimization, leading to a subexponential lower bound for Zadeh's Rule, was awarded with the Tucker Prize.
November 1
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Yihong Zhang, Kyoto University
Title: Statistical Machine Learning and Its Application on Social Media
Abstract: Recent years have seen rapid growth in largescale social data. A social media platform such as Twitter generates hundreds of millions of short messages every day, which contain important information about various social phenomenon. Due to its large volume, it is almost impossible for human operators to manually digest this data. Statistical machine learning consists techniques that aim to extract important information from large volumes of data. In this lecture, I will show how statistical machine learning can be applied for mining social media data. I will talk about supervised learning, unsupervised learning, and optimization algorithms. Particularly, I will introduce techniques such as Naive Bayes Classifier, Neural Network, Kmeans clustering, and Particle Swarm Optimization. I will show how these techniques can be used in a particular application, namely, event extraction from social media.
November 8
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Kokichi Sugihara, Meiji University
Title: Mathematics of Impossible Objects
Abstract: “Impossible objects” originally meant objects that cannot exist as real physical objects; they could only exist in our mind when we saw special pictures. However, they are not necessarily impossible; there are some tricks by which we can construct objects whose appearances match the pictures of impossible objects. Starting with this fact, we can extend the concept of impossible objects so that various behaviors of the objects appear impossible. We show them together with the underlying mathematics.
Bio: Kokichi Sugihara received Bachelor of Engineering, Master of Engineering, and Dr. of Engineering from the University of Tokyo in 1971, 1973 and 1980, respectively. He worked at Electrotechnical Laboratory in the Ministry of International Trade and Industry of Japan, Nagoya University and the University of Tokyo before moving to the current position at Meiji University in 2009. His research area is mathematical engineering. He won the first prize twice (2010 and 2013) and the second prize twice (2015 and 2016) in the Best Illusion of the Year Contest. He is the author of “Machine Interpretation of Line Drawing” (MIT Press) and a coauthor of “Spatial Tessellations: Concepts and Applications of Voronoi Diagrams” (Wiley and Sons).
November 15
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Raj Dabre, NICT
Title: Generative Adversarial Network
Abstract:
Deep neural networks (DNN) are well known for their ability to excel at text or image classification aka discriminative tasks. Although, DNNs are also good at generative tasks (sequence or image), it is very difficult to say whether the generated content is similar to what humans would produce. Enter Generative Adversarial Networks (GANs)! GANs extend a classic generative DNN to include an additional component known as the discriminator which learns to distinguish between generated (fake) and natural (real) data. This enables the generator to learn to generate content that is nearly indistinguishable from real life content. In this talk we will start out with a primer of DNN and its classic applications and then dive into GANs. We will cover an indepth working of GANs and its variations and then explore several exciting applications of adversarial approaches. We will also focus on how GANs are good at leveraging unlabelled data to boost the quality of generative models.
November 29
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Fabien Cromieres, Kyoto University
Title: Neural Machine Translation
Abstract:
Neural Machine Translation uses Neural Networks to translate automatically texts in different languages. This is a recent approach to Machine translation which started in 2014 but quickly became the stateoftheart technique for the field, leading to large improvements in translation quality. Moreover, the neural networks used in MT can actually learn to convert any sequence of symbol into another sequence of symbol, which make them useful in many areas outside of Machine Translation (eg. automatic summarization). We will give an overview of the main Neural Network Architectures used in Machine Translation: RNN with attention mechanism, Convolutional Networks, Transformer Network.
December 6
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Fabien Cromieres, Kyoto University
Title: Word Embedding
Abstract:
Word embedding is an ubiquitous technique in modern Natural Language Processing. As the name implies, it consists in embedding a vocabulary into a vector space, that is, assigning a vector of real numbers to each words in the vocabulary. However, to be useful, such an embedding has to carry the lexical and semantic properties of the words in the vector space. Words that are close in meaning should have embeddings that are close in the vector space. And if two pair of words have the same semantic relation (eg. manwoman and kingqueen), their vector difference should be similar. We look at the most efficient algorithms to produce automatically such embeddings: skipgram, Glove, FastText, etc.
December 13
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Fabien Cromieres, Kyoto University
Title: Automatic Image Captioning
Abstract:
Automatic Image Captioning is a relatively new field of research combining NLP (Natural Language Processing) and Computer Vision aspects. It consists in automatically creating natural language sentences describing a given input image. It has a wide range of application, from Information Retrieval to improving web accessibility for blind persons. The typical approach is to use a convolutional network for encoding the input image followed by a decoder similar to the ones used in Machine Translation to generate the output. We will describe this approach and the typical result obtained
December 27
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Adam Jatowt, Kyoto University
Title: Acrosstime Term Similarity Computation and Explanation
Abstract: Recently, large amounts of historical texts have been digitized and made accessible to the public. However, accessing them is difficult due to the terminology gap problem resulting from semantic evolution of terms. Current users of longterm archives may then not know the correct terms for formulating their queries. In this talk, I will first describe the framework for estimating and explaining the acrosstime similarity of terms. For example, given an input term (e.g., iPod) and the target time (e.g. 1980s), the task is, first, to find its counterpart that existed in the target time (e.g., Walkman) and, then, to output evidences of their similarity (e.g., portable music devices, mp3/tape). Next, I will show the demo system that can generate candidate words for an input query term and an aspect term. Finally, I will introduce approach for explaining term similarity over time.
January 10
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Adam Jatowt, Kyoto University
Title: Estimating Document Comprehensibility
Document comprehensibility is one of key factors determining document quality and, in result, reader’s satisfaction. Relevant documents are of little utility for users searching and browsing the Web, if they are incomprehensible or impose too much cognitive burden on readers. In this talk we survey our research on estimating comprehensibility of web pages and on ranking search results based on their understandability levels.
January 17
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
David Avis, Kyoto University and McGill University
Title: mts: A Framework for Parallel Tree Search
Abstract: I will describe mts, a generic framework for parallelizing certain types of tree search programs using a single common wrapper. The first part of the talk is a tutorial on how to parallelize enumeration codes based on reverse search using a very simple mts interface. mts also supports sharing information between processes which is important for applications such as satisfiability testing and branchandbound. No parallelization is implemented in the legacy single processor code minimizing the changes needed and simplifying debugging. mts is written in C, uses MPI for parallelization and can be used on a network of computers. I will give computational results for the parallelization of two simple existing reverse search codes, generating topological sorts and generating spanning trees of a graph, and two codes for satisfiability testing. (Joint work with Skip Jordan)
January 24
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Adnan Sljoka, Kwansei Gakuin University
Title: Rigidity Theory and its Applications to Protein Function Analysis
Abstract: Rigidity theory has a rich mathematical foundation in geometry and graph theory and it investigates the rigidity and flexibility of structures which are defined by geometric constraints on a set of rigid objects. Rigidity theory has many practical applications in engineering, material science and biochemistry. Since the time of Laman’s theorem (1970), which gives a rigorous combinatorial (counting) characterization for (generic) rigidity of 2dimensional bar and joint frameworks, there have been a number of important advancements in this rich and fascinating subject. In this talk we will introduce some basic concepts and algorithms in rigidity theory and its applications to predicting flexibility and dynamics of protein structures to better understand their function. We will discuss our experimentally validated methods on probing the mechanism of elusive allosteric regulation (i.e. second secret of life) of protein function (Science, 2017, Nature Communication, 2018) and other proteins as a powerful computational algorithms and methods for probing the difficult allosteric control of protein function. We will also highlight our recent results on uses of rigidity theory algorithms in analysis of antibodies [Frontiers in Immunology, 2018] which provides novel insights into how immune system proteins recognize antigens. We will also discuss decomposition of special minimally rigid graphs and their applications in robotics.
Bio: Adnan Sljoka is a Canadian, Applied Mathematician and Computational Biologist. His research is highly interdisciplinary. He is working on rigidity theory and algorithm design for analysis of protein function, drug discovery and robotics. He completed his PhD at York University in Toronto, Canada in 2012 in Applied Mathematics. Currently he is a Visiting Professor in University of Toronto in Biochemistry and Assistant Professor in Kwansei Gakuin, Informatics. For more info see http://adnansljoka.ca/