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

• October 3
  • David Avis(Kyoto University), All Meals for a Dollar and other Vertex Enumeration Problems

• October 10
  • Adam Jatowt(Kyoto University), Towards Effective Information Access Methods to Document Archives

• October 17
  • Ryo Yamada(Kyoto University), Mutations of Triangular Mesh for 3d Shape Analysis hosted by David Avis

• October 24
  • Kazuo Iwama(RIMS, Kyoto University), Narrowing Small Complexity Gaps hosted by David Avis

• October 31
  • Guillaume Malod(Université Paris Diderot), Can linear algebra solve difficult combinatorical counting problems? (An introduction to algebraic complexity theory.) Part 1

• November 7
  • Guillaume Malod(Université Paris Diderot), Can linear algebra solve difficult combinatorical counting problems? (An introduction to algebraic complexity theory.) Part 2

• November 14
  • Francois Le Gall(Nagoya University), Random Walks and Space Complexity

• November 28
  • Francois Le Gall(Nagoya University), Introduction to Distributed Computing

• December 5
  • No lecture on this day

• December 12
  • Adam Jatowt(Kyoto University), Estimating Document Comprehensibility and Comprehensibility-aware Search

• December 19
  • Hans Tiwary(Charles University),Extension complexity: How universal is the cut polytope hosted by David Avis

• December 26
  • Panote Siriaraya(Kyoto Institute of Technology), Game Technology for Supportive Healthcare hosted by Adam Jatowt

• January 23
  • Takeshi Tokuyama(Kwansei-Gakuin University), Does Alice confuse Geometric Complexity Theory?　Dodgson's Condensation Algorithm and Related Topics hosted by David Avis

• January 30
• Antoine Doucet(University of La Rochelle, France), Sequential pattern mining for information extraction hosted by Adam Jatowt

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 Communications and Computer Engineering 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.

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Adam Jatowt, Kyoto University
Title: Towards Effective Information Access Methods to Document Archives
Abstract: These days the amount of content stored in long-term document archives is rapidly increasing. This is due to widespread digitization and content curation initiatives aiming at preserving and disseminating our cultural heritage. Newspaper articles, books, or other document genres are becoming digitized and made open to the public. Nevertheless, effective methods for information access to document archives and methods aiming at making sense of the available data are still missing. In this talk, we will describe our latest research towards making document archives such as newspaper article archives more usable and useful to users, both to professionals and average users. We will start with presenting methods for finding similar entities and comparable entity sets from the past. Next, we will describe how the across-time similarity of entities can be explained. We will conclude with the description of research aiming to design methods for finding interesting and unusual content in document archives.

Bio: Adam Jatowt is Associate Professor at Social Informatics Department of Kyoto University. He has graduated from University of Tokyo in 2005 and worked at NICT as a postdoc. He then moved to Kyoto University from 2006 as an assistant professor. Adam's interest are in information retrieval, digital libraries and digital history.

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Ryo Yamada, Kyoto University
Title: Mutations of Triangular Mesh for 3d Shape Analysis

Abstract: Living cells have S2-isomorphic shapes and the shapes are constructed with micro-skeletal molecules spanned by lipid-bilayer membrane. To investigate cell morphology, they are discretized. Triangular mesh is the most popular discrete representation. Based on this biological research motivation, we have been studying the methods to characterize geometric features of triangular meshes or triangular planar graphs. In this talk we introduce an application of mutations of quiver to random changes of triangular meshes and representation of triangular meshes as permutations or combinations of cycles.

Bio: 1992-1999 : Rheumatologist, 2000-2004 : Researcher on disease-associated gene identification, RIKEN, Yokohama, 2005-2007 : Associate Professor, Human Disease Genomics, Medicine, Kyoto Univ., 2007-2008 : Associate Professor, Human Genome Center, IMS, Tokyo Univ., 2009- : Professor, Statistical Genetics, Medicine, Kyoto Univ.

Speciality: Genetic epidemiolgy, Statistical genetics, Quantitative biology

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Kazuo Iwama, RIMS, Kyoto University
Title: Narrowing Small Complexity Gaps
Abstract: Suppose that we have an algorithm which runs in time O(n). This algorithm is optimal in the usual sense and there is little room for further improvements. Nevertheless one may be interested in the constant factor that is hidden by the big-O notation, but that would cause nasty issues about machine models. On the other hand, there are several other complexity measures that are more accurate and cleaner than the number of computation steps. One of them is the number of comparisons for evaluating sorting algorithms. In many textbooks, it is just written that fast algorithms need O(nlogn) comparisons (log means the logarithm of base 2 here), which is optimal. It turns out, however, that its information theoretic lower bound is log(n!), which is approximately equal to nlogn - 1.4426n + O(logn). For instance, it is easy to prove that the simple binary insertion sort needs at most nlogn comparisons, but it is much harder to specifically bound the linear term or to bound its constant factor. The previous best upper bound for that constant factor is -1.32 due to Ford and Johnson that was published in 1959! Another example of such measure is the number of oracle calls for reconstruction of strings which is a model of sequence by hybridization. Again the previous upper bound is n + 2logn and it is a long-standing open question whether the logn term can be removed.

This talk is about our two recent results on improved upper bounds for those two complexity measures. Such a small improvement may be useless in practice, but it needs a lot of new algorithmic techniques that may be useful in other problems. Even more importantly, those are nice examples to demonstrate the power of randomization and/or the advantage of the average-case complexity over the worst-case complexity.

Bio: PhD from Kyoto University in 1980, Assistant and Associate Professor at Kyoto Sangyo University 1978-1990, Associate and Full Professor at Kyushu University 1990-1997, Full Professor at Kyoto University (School of Informatics) 1997-2016. Project Professor at Kyoto University (RIMS) from 2016.

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Guillaume Malod, Université Paris Diderot
Title: Can linear algebra solve difficult combinatorical counting problems? (An introduction to algebraic complexity theory.) Part 1
Abstract: We will give a short and intuitive introduction to algebraic complexity theory, the study of the number of arithmetic operations necessary to compute certain polynomials. Some need few operations, others are conjectured to need much more, and the resulting classes of polynomials, VP and VNP, are analogous to the famous P and NP classes for general computations. Whether VP is equal to VNP or not is also a major open question, which can be stated, without having to introduce computational models, as comparing the computational power of linear algebra and combinatorical counting.

Bio: Guillaume Malod is an Associate Professor at Paris Diderot University and JSPS Invitational Fellow for Research in Japan. He received his PhD in 2003 from Claude Bernard University in Lyon. His research is mainly focused on computational complexity.

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Guillaume Malod, Université Paris Diderot
Title: Can linear algebra solve difficult combinatorical counting problems? (An introduction to algebraic complexity theory.) Part 2
Abstract: We will give a short and intuitive introduction to algebraic complexity theory, the study of the number of arithmetic operations necessary to compute certain polynomials. Some need few operations, others are conjectured to need much more, and the resulting classes of polynomials, VP and VNP, are analogous to the famous P and NP classes for general computations. Whether VP is equal to VNP or not is also a major open question, which can be stated, without having to introduce computational models, as comparing the computational power of linear algebra and combinatorical counting.

Bio: Guillaume Malod is an Associate Professor at Paris Diderot University and JSPS Invitational Fellow for Research in Japan. He received his PhD in 2003 from Claude Bernard University in Lyon. His research is mainly focused on computational complexity.

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Francois Le Gall, Nagoya 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 well-known applications concerning the design of space-efficient 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 space-efficient algorithms for solving linear systems of equations based on random walks.

Bio: Francois Le Gall is an Associate Professor at the Graduate School of Mathematics, Nagoya University. He received his PhD in 2006 from the University of Tokyo. His research interests include algorithms, computational complexity and quantum computation.

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Francois Le Gall, Nagoya University
Title: Introduction to Distributed Computing
Abstract: I will give a short introduction to the field of distributed algorithms. I will explain describe the concept of distributed computing and describe some fundamental distributed algorithms. I will then explain how simple techniques from complexity theory (e.g., communication complexity) can be used to show lower bounds on the running time of distributed algorithms.

Bio: Francois Le Gall is an Associate Professor at the Graduate School of Mathematics, Nagoya University. He received his PhD in 2006 from the University of Tokyo. His research interests include algorithms, computational complexity and quantum computation.

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Adam Jatowt, Kyoto University
Title: Estimating Document Comprehensibility and Comprehensibility-aware Search

Abstract: 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 on 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.

Bio: Adam Jatowt is Associate Professor at Social Informatics Department of Kyoto University. He has graduated from University of Tokyo in 2005 and worked at NICT as a postdoc. He then moved to Kyoto University from 2006 as an assistant professor. Adam's interest are in information retrieval, digital libraries and digital history.

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Hans Tiwary, Charles University
Title: Extension complexity: How universal is the cut polytope

Abstract: It is known that the cut polytope of the complete graph cannot be written as the projection of any polytope with a polynomial number of facets. This hardly seems surprising since optimizing a linear function over this polytope is the NP-hard MAXCUT problem. However, this is not at all the intuition behind the proof of the complexity of cut polytope.

In this talk I will present a universality property of the cut polytope that for pretty much any polytope P that can be reasonably described, one can construct a polytope Q such that P is a linear projection of Q and the number of inequalities needed to describe Q is bounded by the aforementioned complexity of cut polytope (plus a reasonable additive factor).

Bio: Hans Tiwary is an associate professor (Docent) in the Department of Applied Mathematics of the Faculty of Mathematics and Physics at the Charles University in Prague. His research interests include Optimization, Algorithms, Complexity and Physics.

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Panote Siriaraya, Kyoto Institute of Technology
Title: Game Technology for Supportive Healthcare

Abstract: In this seminar, we would explore the use of game technology in supportive healthcare. A range of multidisciplinary research projects will be discussed, such as projects involving the use of gamification to enhance mental healthcare therapies, supporting healthy ageing through online 3D virtual environments and using gesture based interaction and tangible interfaces to augment virtual world interaction and engage people with Dementia. The central theme of these projects lie in the theoretical and practical demonstration of how game technology and game thinking could be applied to solve real world problems, often by blending the physical and virtual worlds. We would introduce various UX techniques which we have developed and employed to create these systems, providing an overview of how user experience research is carried out when designing innovative solutions for the healthcare context.

Bio: Panote Siriaraya is currently an Assistant Professor at the Kyoto Institute of Technology. Previously, he served as a post-doc researcher at Kyoto Sangyo University in Japan and the Delft University of Technology in the Netherlands. He received his PhD in Electronic Engineering from the School of Engineering and Digital Arts, University of Kent in the UK.

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Takeshi Tokuyama, Kwansei Gakuen University
Title: Does Alice confuse Geometric Complexity Theory?　Dodgson's Condensation Algorithm and Related Topics

Abstract: The determinant of a matrix is a central function in computer science. Indeed, Valiant showed that any polynomial time computable polynomial function can be interpreted as a determinant (of a matrix of polynomial size), and proposed VP vs VNP problem, which can be regarded as an algebraic variant of the P vs NP (or P vs #P ) problem. This motivated the Geometric Complexity Theory (GCT), which tackles VP vs VNP problem via algebraic group theory.

There are several algorithms for computing the determinant. Among them, Dodgson (Lewis Carrol)'s agorithm is a simple and efficient dynamic programming algorithm. Unfortunately, the algorithm has a defect of possibility to fail. However, the algorithm motivated the discovery of the generalized determinant defined by Robbins and Rumsey in 1986. And amazing thing is that the generalized determinant can be computed in polynomial time despite of the fact that it loses the group action. This looks controversial to the GCT program.

We also discuss how to make the Dodgson's algorithm perfect through the generalized determinant. Moreover, we give a generalized determinantal formula, which is specialized to the Weyl character formula of type A, and considered as its natural q-analogue. It is considered to be a novel interpretation of a formula (called Tokuyama's formula in the literature) given in 1988, which was originally stated in the language of Gelfand-Zetlin patterns. Tokuyama's formula has been interpreted in several ways in the last decade, and applied to the study of Kashiwara crystal, L-functions of group representations, and six-vertex model of statistical mechanics. However, its interpretation as a natural determinantal identity was not known before.

Bio: Takeshi Tokuyama received a Ph. D in mathematics (algebraic group theory) in 1985 from U. Tokyo, and worked for IBM Tokyo Research Laboratory from 1986 to 1999. From 1999 to 2018, he was a professor in Tohoku University, and from 2019, he is a professor at Kwansei Gakuen University. His research interest is theoretical computer science, including computational geometry, algorithms, optimization, and data mining.

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Antoine Doucet, University of La Rochelle
Title: Sequential pattern mining for information extraction
Abstract: With ever increasing amounts of data, the task of automatically analysing numerous media in various format and multiple languages is getting all the more critical. The ability to quickly and efficiently analyse massive amounts of documents, both digitised and digitally-born, is crucial. With a history dating a few centuries and a current rate of about hundreds of thousands of articles published every day, newspapers represent a heterogeneous resource of great importance. This talk will present an approach that is able to detect events from news using very limited external resources, notably not requiring any form of linguistic analysis. By relying on the journalistic genre rather than on linguistic analysis, it is both able to process text written in any language, and in a fashion that is robust to noise (eg, stemming from imperfect OCR). Applied for instance to epidemic event detection, it is able to find what epidemic diseases are active where, in any language and in real time. Evaluated over 40 languages, the DaNIEL system is on average able to find epidemic events faster than human experts. In this presentation, we will further explain how this work is being expanded to further domains and particularly to historical documents, and how similar ideas are applied to other important NLP problems such as named entity recognition and linking.

Bio: Antoine Doucet is a tenured Full Professor in computer science at the L3i laboratory of the University of La Rochelle since 2014. Director of the ICT department in the University of Science and Technology of Hanoi, he leads in La Rochelle the research group in document analysis, digital contents and images (about 40 people). He is the coordinator of the H2020 project NewsEye, running until 2021 and focusing on augmenting access to historical newspapers, across domains and languages. He further leads the effort on semantic enrichment for low-resourced languages in the context of the H2020 project Embeddia. His main research interests lie in the fields of information retrieval, natural language processing and (text) data mining. The central focus of his work is on the development of methods that scale to very large document collections and that do not require prior knowledge of the data, hence that are robust to noise (e.g, stemming from OCR) and language-independent. Antoine Doucet holds a PhD in computer science from the University in Helsinki (Finland) since 2005, and a French research supervision habilitation (HDR) since 2012.