Schedule for Fall 2019 - Kyoto University Informatics Seminar

avis

Schedule for Fall 2019

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 (総合7), Main Campus

    • David Avis(Kyoto University), All Meals for a Dollar and other Vertex Enumeration Problems
    • Adam Jatowt(Kyoto University), Towards Effective Information Access Methods to Document Archives
    • Ryo Yamada(Kyoto University), Mutations of Triangular Mesh for 3d Shape Analysis hosted by David Avis
    • Kazuo Iwama(RIMS, Kyoto University), Narrowing Small Complexity Gaps hosted by David Avis
    • Guillaume Malod(Université Paris Diderot), Can linear algebra solve difficult combinatorical counting problems? (An introduction to algebraic complexity theory.) Part 1
    • Guillaume Malod(Université Paris Diderot), Can linear algebra solve difficult combinatorical counting problems? (An introduction to algebraic complexity theory.) Part 2
    • Francois Le Gall(Nagoya University), Random Walks and Space Complexity
    • Francois Le Gall(Nagoya University), Introduction to Distributed Computing
    • Adam Jatowt(Kyoto University),Estimating Document Comprehensibility and Comprehensibility-aware Search
    • Hans Tiwary(Charles University),Extension complexity: How universal is the cut polytope hosted by David Avis
    • Panote Siriaraya(Kyoto Institute of Technology), Game Technology for Supportive Healthcare hosted by Adam Jatowt
    • Takeshi Tokuyama(Kwansei-Gakuin University), Does Alice confuse Geometric Complexity Theory? Dodgson's Condensation Algorithm and Related Topics hosted by David Avis
  • Antoine Doucet(University of La Rochelle, France), Title hosted by Adam Jatowt

Detailed Information and Abstracts

October 3

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合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.

October 10

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合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.

October 17

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合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

October 24

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合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.

October 31

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合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.

November 7

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合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.

November 14

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合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.

November 21

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合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.

December 12

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合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.

December 19

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合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.

December 26

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合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 could 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.

January 30

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Antoine Doucet, University of La Rochelle
Title: tbd
Abstract: tbd

Bio: ??