Schedule for Fall 2016 - Kyoto University Informatics Seminar

Schedule for Fall 2016

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

  • October 6 (2 talks) 1st talk: 14:45-16:15, 2nd talk: 16:30-18:00
    • 14:45-16:15: Stephan Langerman(Université Libre de Bruxelles), Tilings and unfoldings, hosted by D. Avis and A. Yamamoto
    • 16:30-18:00: Greg Dudek(McGill University), Robotic System Design for Automated Marine Data Collection , hosted by D. Avis and A. Yamamoto
    • Adam Jatowt(Kyoto University), Estimating Document Comprehensibility and Comprehensibility-enhanced Search
    • Xuefeng Liang(Kyoto University), Visual Attention Inspired Distant View and Close-Up View Classification
    • Takashi Horiyama(Saitama University), On the Enumeration of Unfoldings of Polyhedra, hosted by D. Avis and A. Yamamoto
    • Michael Houle(NII), An Extreme-Value-Theoretic Foundation for Similarity Applications, hosted by D. Avis and A. Yamamoto
    • Francois Le Gall(Kyoto University), Random Walks and Space Complexity
    • Abuzer Yakaryilmaz(University of Latvia), The Power of a Single Qubit, hosted by F. Le Gall
    • Cathal Gurrin(DCU, Ireland), The Information Retrieval Challenge of Personal Lifelogs, hosted by Adam Jatowt
    • Bakhadyr Khoussainov(University of Auckland), Parity Games are Fixed Parameter Tractable, hosted by Adam Jatowt
  • December 15, irregular time slot: 16:30-18:00
    • Jun Tani(KAIST, Korea), How can we Develop 'Deep Minds' of Robots?, hosted by Xuefeng Liang
    • David Bremner(University of New Brunswick), Small Linear Programs for Decision Problems, hosted by D. Avis and A. Yamamoto
    • Zhenglu Yang(Nankai University), Exploration on Searching Similar Short Texts, hosted by Adam Jatowt
    • Bingkai Lin(National Institute of Informatics), Gap Amplification Using Bipartite Random Graphs, hosted by F. Le Gall
    • Skip Jordan(Hokkaido University), mts: A Framework for Parallel Tree Search, hosted by D. Avis and A. Yamamoto

Detailed Information and Abstracts

October 6

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Stefan Langerman, Université Libre de Bruxelles
Title: Tilings and unfoldings
Abstract: A tiling is a covering of the plane with copies of a geometric shape (tiles) without gaps or overlaps. An unfolding is obtained by cutting along the surface of a polyhedron through all its vertices, and opening all the dihedral angles between adjacent faces to obtain a single flat nonoverlapping geometric shape. In this hands-on talk, I will explore connections between these two fascinating concepts, in an attempt to shed some light on the following still unsolved algorithmic problem: How easy (or hard) is it to determine if a given geometric shape can tile the plane? and the following more artistic and no less fundamental problem: How to create beautiful (or even ugly) tilings?

Bio: Stefan Langerman is a Directeur de recherches at the F.R.S.-FNRS Algorithms Research Group, Département d'Informatique, Université Libre de Bruxelles. He received his PhD degree from Rutgers University in May 2001. His research interests are in Algorithms, Data Structures, and Computational and Combinatorial Geometry.

Greg Dudek, McGill University
Title: Robotic System Design for Automated Marine Data Collection
Abstract: This talk will address the deployment of robotic systems for data collection with particular emphasis on the marine (shallow water) environment. This includes task specification, gait learning and data analysis. As a concrete example I will discuss the automated analysis of video data, and specifically video data collected underwater with an amphibious vehicle (the Aqua2 hexapod robot). Automated systems can collect data at prodigious rates and the timely analysis of this data is a growing challenge, especially when there are bandwidth constraints between the data source and the people who must examine the data. We are specifically interested in the real-time summarization and detection of the most interesting events in a video sequence, for use by humans who will analyze the data either in real time, or offline. To do this, we are developing methods that adapt to video data streams in real time to collect salient events and using them in the context of a group of vehicles that fly, swim and float.

Bio: Gregory Dudek is a Professor with the School of Computer Science and a member of the McGill Research Centre for Intelligent Machines (CIM) and an Associate member of the Dept. of Electrical Engineering at McGill University. In 9/2008 he became the Director of the McGill School of Computer Science. Since 2012 he has been the Scientific Director of the NSERC Canadian Field Robotics Network (NCFRN): http://ncfrn.mcgill.ca He is the former Director of McGill's Research Center for Intelligent Machines, a 25 year old inter-faculty research facility. In 2002 he was named a William Dawson Scholar. In 2008 he was made James McGill Chair. In 2010 he was awarded the Fessenden Professorship in Science Innovation. In 2010 he was also awarded the Canadian Image Processing and Pattern Recognition Award for Research Excellence and also for Service to the Research Community. He directs the McGill Mobile Robotics Laboratory.

October 13

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Adam Jatowt, Kyoto University
Title: Estimating Document Comprehensibility and Comprehensibility-enhanced Search
Abstract: Document comprehensibility is one of key factors determining document quality and, in result, user’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 degrees.

Bio: Adam Jatowt received his Ph.D. in Information Science and Technology from University of Tokyo, Japan in 2005. He is currently Associate Professor at Social Informatics Department, Kyoto University. His research interests include information retrieval and knowledge extraction from document archives and information comprehensibility. Adam has served or serves as a PC co-chair of IPRES2011, SocInfo2013, ICADL2014, JCDL2017 conferences, tutorial co-chair of SIGIR2017 and editorial board member of Information Processing and Management Journal.

October 20

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Xuefeng Liang, Kyoto University
Title: Visual Attention Inspired Distant View and Close-Up View Classification
Abstract: The images of distant view and close-up view indicate a photographers' attention which can be further utilized for user behavior analysis and scene evaluation. As images may compose arbitrary contexts, distant view and close-up view classification becomes non-trivial. In this work, we found two cues can represent human visual attention, i.e. focus cue and scale cue. We model the focus cue in frequency domain using the Discrete Wavelet Transform, and employ signal distribution as the focus feature. For the scale cue, we model it by defining a spatial size and a conceptual size in the image using the Edge Box and Convolution Neural Network. By integrating these two models, a robust scheme is proposed for this non-trivial task. Experiments on a newly retrieved dataset, which has 2137 natural images, show the classification accuracy achieves up to 97.3%.

Bio: Xuefeng liang has research interests on visual perception, computer vision, algorithms and bio-metrics. He once worked in both University College of London and Queen Mary University of London from 2008 to 2010. Currently, he is an associate professor in Kyoto University. He is on the editorial board of two international journals, and has served as TAP and TCP members for several international conferences.

October 27

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Takashi Horiyama, Saitama University
Title: On the Enumeration of Unfoldings of Polyhedra

Abstract: We will discuss enumeration algorithms of unfoldings of polyhedra. An unfolding of a polyhedron is a simple polygon obtained by cutting along edges of the polyhedron and unfolding it into a plane. A zero-suppressed binary decision diagram (ZDD) is a directed acyclic graph that represents a family of sets. By sharing isomorphic subgraphs, many practical families of sets can be compactly represented by ZDDs. Recenlty, a novel technique is proposed for constructing ZDDs representing the solutions of constraint satisfying problems. We learn basics and techniques of ZDDs.

Bio: Takashi Horiyama is an Associate Professor at Graduate School of Science and Engineering, Saitama University. He received Ph.D. in informatics from Kyoto University in 2004. His research interests include algorithms, data structures, and computational geometry.

November 10

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Michael Houle, National Institute of Informatics
Title: An Extreme-Value-Theoretic Foundation for Similarity Applications
Abstract: For many large-scale applications in data mining, machine learning, and multimedia, fundamental operations such as similarity search, retrieval, classification, clustering, and anomaly detection generally suffer from an effect known as the `curse of dimensionality'. As the dimensionality of the data increases, distance values tend to become less discriminative due to their increasing relative concentration about the mean of their distribution. For this reason, researchers have considered the analysis of similarity applications in terms of measures of the intrinsic dimensionality (ID) of the data sets. This presentation is concerned with a generalization of a discrete measure of ID, the expansion dimension, to the case of continuous distance distributions. This notion of the ID of a distance distribution is shown to precisely coincide with a natural notion of the indiscriminability of distances, thereby establishing a theoretically-founded relationship among probability density, the cumulative density (cumulative probability divided by distance), intrinsic dimensionality, and discriminability. The proposed indiscriminability function is shown to completely determine an extreme-value-theoretic representation of the distance distribution. From this representation, a characterization in terms of continuous ID is derived for the notions of outlierness and inlierness of data.

Bio: Michael Houle is a Visiting Professor at the National Institute of Informatics, Collaborative Research Unit and the Graduate University of Advanced Studies (Sokendai), Department of Informatics. He received his PhD from McGill University in 1989. His research interests are in databases (similarity search), data mining (clustering, classification), design and analysis of algorithms, visualization, combinatorial geometry.

November 17

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

November 24

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Abuzer Yakaryilmaz, University of Latvia
Title: The Power of a Single Qubit
Abstract: In this talk, we consider a finite automata having only a single qubit and present some interesting results based on it in unbounded-error, bounded-error, and nondeterministic settings. Moreover, we consider its verification power and give an easy example protocol. Depending on remaining time, we also mention about a new quantum-like non-linear classical automata called affine automata with some basic results. At the beginning of the talk, we quickly review classical automata.

Bio: Abuzer Yakaryilmaz is a theoretical computer scientist working on computational complexity for quantum automata models. He got his PhD in 2011 in Istanbul, Turkey. Then, he was a postdoc researcher in Andris Ambainis' group in Latvia for three years. After this, he received a research grant and he worked in LNCC, Brazil for 2 years. Currently he is a visiting researcher in Latvia.

December 1

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Cathal Gurrin, Dublin City University
Title: The Information Retrieval Challenge of Personal Lifelogs

Abstract: Personal Lifelogs are media rich archives of personal data from many heterogeneous sources. Recent advances in information technology have brought us to a point where it is now inexpensive and therefore feasible to capture rich personal lifelogs for all individuals. However, unlike many other Information Retrieval challenges, there are no standard retrieval approaches and few commonly used interaction methodologies for lifelogging. In this talk, I will explore the information retrieval challenge of lifelogging. This requires the exploration of the different types of lifelog data available now and in the coming years. Following that, the challenge of indexing and retrieval will be discussed before examining the different types of interface methodologies employed by the first generation of lifelog prototypes. Finally, we will explore the various efforts underway to drive the community forward by practitioners through real-world applications and by researchers through benchmarking exercises, such a NTCIR13-Lifelog or ImageCLEF-Lifelog.

Bio: Cathal Gurrin is a senior lecturer at the School of Computing, at Dublin City University, Ireland and he is a Principal investigator at the Insight Centre for Data Analytics. His research interests are personal analytics and lifelogging. Lifelogging integrates personal sensing, computer science, cognitive science and data-driven healthcare analytics to realize the next-generation of digital records for the individual. He is especially interested in how wearable sensors can be used to infer knowledge about the real-world activities of the individual and how lifelogs can be used to enhance the life experience of the individual. He regularly speaks at Quantified Self events and his research been featured internationally on Discovery Channel, BBC, NHK, as well as in the Economist magazine, New York Times, among many others.. He has been the General Chair of ECIR 2011, MMM 2014 and MB2016, will be the General co-chair of MMM2017. He was also the PC co-chair of ECIR 2010 and Sensecam 2013 as well as being the posters and demos co-chair of ACM SIGIR 2013.

December 8

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Bakhadyr Khoussainov, University of Auckland
Title: Parity Games are Fixed Parameter Tractable

Abstract: Parity games is a class of perfect information two player games that are of great interest due to connections to μ-calculus, various logics, tree automata, verification and model checking problems. Given a parity game (with n nodes and m colours), the problem consists of finding the winner of the game. Emerson, Jutla and Sistla showed that the problem is in NP ∩co -NP. Jurdzinski improved this bound to UP ∩ co -UP. It is an old standing open problem if the winners in parity games can be found in polynomial time. We prove that the parity games problem can be solved in quasi-polynomial time. As a corollary, we prove that the problem is fixed parameter tractable with respect to the parameter m. These significantly improve all the known bounds. Although the original problem is still open, our result gives a glimpse of hope towards a positive solution of the problem. Also, see https://en.wikipedia.org/wiki/Parity_game​ The work is joint with C. Calude, Sanjay Jain, L. Wei, and F. Stephan.

== December 15 == irregular time slot
16:30 - 18:00, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Jun Tani, Korea Advanced Institute of Science and Technology
Title: How can we Develop 'Deep Minds' of Robots?
Abstract: My research motivation has been to investigate how cognitive agents can acquire structural representation via iterative interaction with the world, exercising agency and learning from resultant perceptual experience. Over the past 20 years, my group has tackled on this problem by investigating the idea of predictive coding applied to development of cognitive constructs of robots. Under the principle of predictive coding, dense interaction take place between the top-down intention proactively acting on the outer world and the resultant bottom-up perceptual reality accompanied with the prediction error. Our finding has been that compositionality or systematicity enabling some conceptualization can emerge via such iterative interaction when constraints such as multiple spatio-temporal scale property applied to the neural network modeling and the way of tutoring the robots applied to the behavioral interaction level act on the development of the whole system in terms of 'downward causation'. The talk will highlight our recent results on interactive and integrative learning among multimodality of perceptual channels including pixel level dynamic vision, proprioception and linguistic inputs using a humanoid robot platform. Finally, I will point to one aim of future research, how the deep mind of a robot may arise through long-term educational tutoring program.

Reference: J. Tani: “Exploring Robotic Minds: Actions, Symbols, and Consciousness as Self-Organizing Dynamic Phenomena.”, New York: Oxford University Press, 2016

Bio: Jun Tani received a doctor of engineering degree in electrical engineering from Sophia University in Tokyo in 1995. He worked for Sony Corp. and later for Sony Computer Science Lab as a researcher from 1990 to 2001. Then, he worked at Riken Brain Science Institute from 2001 to 2012 where he has been a PI of Lab. for Behavior and Dynamic Cognition. He had been also appointed as a Visiting Associate Professor, Graduate School of Arts and Sciences, University of Tokyo from 1997 to 2002. He became a full professor of Electrical Engineering in KAIST in Korea in 2012 where he started Cognitive Neuro-Robotics Lab. His research interests include neurorobotics, deep learning, complex systems, brain science, developmental psychology, and philosophy of mind.

December 22

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
David Bremner, University of New Brunswick
Title: Small Linear Programs for Decision Problems
Abstract: In the classical “Edmonds” model of solving combinatorial optimization problems with linear programs, one optimizes over the convex hull P of the zero-one vectors representing feasible instances. An “extended formulation” is then some polytope Q that lets one optimize any objective over P by optimizing over Q. This is an extremely natural model for an optimizer, but it provides much more power than is needed to solve decision problems. This leads to the surprising situation where certain problems in P have no polynomial sized extended formulations.

In this talk I will discuss so called “weak extended formulations” where one considers the convex hull of all instances, with an extra coordinate for “YES/NO”. In this setting it suffices to optimize a very limited (and structured) set of objectives, one per YES instance. It turns out that previous constructions can be used to show that any problem in P/Poly (i.e. that has a polynomial sized circuit family) has a weak extended formulation. This in turn leads to some interesting connections with the theory of non-negative factorization of matrices.

Bio: David Bremner holds three degrees in Computer Science, a B.Sc. Hons. from the University of Calgary (1990), an M.Sc. from Simon Fraser University (1993) and a Ph.D. from McGill University (1997). David spent two years as an NSERC postdoctoral fellow in the Department of Mathematics at the University of Washington from 1997 to 1999. Since 2000 David has been a faculty member at the University of New Brunswick, and is currently a Professor of Computer Science with a Cross Appointment to the Department of Mathematics and Statistics. Recently, David has made extended research visits to the Technical University of Berlin (as an Alexander von Humboldt Fellow), the University of Rostok, and Kyoto University.

January 12

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Zhenglu Yang, Nankai University
Title: Exploration on Searching Similar Short Texts
Abstract: Searching similar short texts is an important problem because it is the basis of many applications, such as query recommendation, data clean, duplicate page detection, question answer, and so forth. In this talk, I will introduce several efficient strategies for searching top-k similar short texts (i.e., words and sentences), taking into account both the string similarities (e.g., edit distance) and the semantic similarities (e.g., PMI). Effective indices are presented to facilitate the reduction of searching space. In addition to the efficiency issue, I will introduce our recent work on measuring similarities between sentences for a specific application, i.e., question answer, where deep learning techniques are utilized to improve the effectiveness.

Bio: Zhenglu Yang received the Bachelor degree from Tsinghua University, China and the PhD degree from the University of Tokyo, Japan. From 2008 to 2014, he worked as a faculty (first assistant professor and then associate professor) in the Institute of Industrial Science, the University of Tokyo. He is now a professor in the College of Computer and Control Engineering, Nankai University, China. His research interests include data mining, artificial intelligence, and natural language processing.

January 19

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
Bingkai Lin, National Institute of Informatics
Title: Gap Amplification Using Bipartite Random Graphs
Abstract: Gap amplification transformation plays an important role in proving hardness of approximation results. In this talk, I will present a new method to construct gap amplification reduction for parameterized optimization problems. First, I will review the threshold phenomena of random graphs G(n,p) containing a bipartite complete subgraph . Then I will show its application on ruling out super-polynomial time algorithms for approximating Maximum k-Subset Intersection and Minimum Set Cover to some ratios.

Bio: Bingkai Lin is a Postdoctoral Researcher at National Institute of Informatics. He received his PhD in 2016 from the University of Tokyo. His research interests include parameterized complexity and algorithm, hardness of approximation.

January 26

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合7), Main Campus
https://www-alg.ist.hokudai.ac.jp/~skip/, Hokkaido University
Title: mts: a Framework for Parallel Tree Search
Abstract: I will describe mts, which is a generic MPI framework for parallelizing certain types of tree search programs, that (a) provides a single common wrapper containing all of the parallelization, and (b) minimizes the changes needed to the existing single processor legacy code. The mts code was derived from ideas used to develop mplrs, a parallelization of the reverse search vertex enumeration code lrs. The tree search properties required for the use of mts are satisfied by any reverse search algorithm as well as other tree search methods such as backtracking, branch and bound, and satisfiability testing. As examples we parallelized two simple existing reverse search codes, generating topological sorts and generating spanning trees of a graph, and two codes for satisfiability testing. I will give some experimental results comparing the parallel codes with state of the art sequential codes for the same problems. (Joint work with David Avis)

Bio: Skip Jordan is an assistant professor in the Laboratory for Algorithmics, Graduate School of Information Science and Technology, Hokkaido University and a member of the ELC project. Previously, he was a postdoc in the JST ERATO Minato Discrete Structure Manipulation Project. He is interested in logic in computer science, especially applications related to descriptive complexity. He is also interested in parallel solvers for SAT and QBF, complexity theory, and related topics.