Fall 2012 - Abstracts and Detailed Information - Kyoto University Informatics Seminar

Fall 2012 - Abstracts and Detailed Information

Unless noted otherwise, all talks 2:45 - 4:15, Room 213, Faculty of Engineering Integrated Research Bldg, Main Campus

    • Kazuo Iwama, Adam Jatowt, David Avis (Kyoto University), G30 Project Research Overview
    • Hans Raj Tiwary (Universite libre de Bruxelles), Equivalence between communication protocols and extended formulations for integer programs, hosted by David Avis
    • Marco Cuturi, Xuefeng Liang, Stanko Trifkovic (Kyoto University), G30 Project Research Overview
    • Ching-man Au Yeung (Hong Kong Applied Science and Technology Research Institute (ASTRI)), Looking through the Cloud - Cloud Computing and Its Core Technologies, hosted by Adam Jatowt
    • Hwann-Tzong Chen (National Tsing Hua University), Video Object Cosegmentation, hosted by Xuefeng Liang
    • Alan Johnston (UCL), Dynamic Face Perception, hosted by Xuefeng Liang
    • Takeshi Tokuyama (Tohoku University), Area minimization of convex hull of movable objects: Algorithmic convex Kakeya problem, hosted by David Avis
    • No seminar - Reports for Nov 8 may be put in the dropbox, Research Building No. 8, 1F before 5pm on Wednesday Nov 21
    • Jon Noel (McGill University), A Proof of Ohba's List Colouring Conjecture, hosted by David Avis
    • No seminar - Reports for Nov 29 may be put in the dropbox, Research Building No. 8, 1F before 5pm on Wednesday December 12, or handed in on December 13 at the seminar
    • Hong Shen (University of Adelaide), Effective Methods for Survivable Network Design, hosted by Kazuo Iwama
    • David Kinny (Kyoto University), Why losing can be harder than winning
    • Chien-Chung Huang (MPI Saarbruecken), Uniqueness and Social Cost of Equilibria in Atomic Splittable Routing Games, hosted by Kazuo Iwama
    • Alvaro Cassinelli (University of Tokyo), Performing Time, Space and Light, hosted by Marco Cuturi
    • Taiji Suzuki (University of Tokyo), Fast Algorithm and Statistical Theory of Multiple Kernel Learning, hosted by Marco Cuturi
  • January 30th 4:30 - 6:00
    • Gael Dias (University of Caen Basse-Normandie), First order association measures for Multiword Unit Extraction, hosted by Adam Jatowt
    • Lorenzo Rosasco (Massachusetts Institute of Technology, Italian Institute of Technology), Towards a statistical theory of learning data representation, hosted by Marco Cuturi

Fall 2012 - Abstracts and Detailed Information

October 4th

2:45 - 4:15, Room 213, Faculty of Engineering Integrated Research Bldg, Main Campus
Kazuo Iwama, Adam Jatowt, David Avis, Kyoto University
Title: G30 Project Research Overview
Abstract: This first colloquium of the semester aims at giving an overview of the research being done by professors in the G30 project of the Graduate School of Informatics. Several professors are going to present short talks about their current research interests and projects.

October 11th

2:45 - 4:15, Room 213, Faculty of Engineering Integrated Research Bldg, Main Campus
Hans Raj Tiwary, Universite Libre de Bruxelles
Title: Equivalence between communication protocols and extended formulations for integer programs
Abstract: Extended formulations are a powerful tool in combinatorial optimization, and have witnessed a growing interest in the research community in recent years. In this talk I will introduce Extended Formulations and discuss relations with the area of communication complexity. I will present some equivalence relations between the two concepts and briefly overview some recent advances in the area.

A basic understanding of polytope theory and communication complexity would be beneficial but not required as I will discuss the fundamental concepts necessary for understanding the talk.

October 25th

2:45 - 4:15, Room 213, Faculty of Engineering Integrated Research Bldg, Main Campus
Ching-man Au Yeung, Hong Kong Applied Science and Technology Research Institute (ASTRI)
Title: Looking through the Cloud - Cloud Computing and Its Core Technologies
Abstract: Cloud computing has attracted a lot of attention in recent years. Some argue that cloud computing is going to change (or is already changing) the world, while some argue that it is nothing new but a re-packaging of existing Internet-related technologies. However, there is no doubt that cloud computing is playing an increasingly important role in different areas of the IT industry. To understand whether cloud computing is going to be as significant as many people have claimed, it is important to understand what exactly does cloud computing refer to. In this talk, I will give an introduction of cloud computing and its core technologies, and discuss the different dimensions of cloud computing and cloud applications. I will also talk about the concepts of Infrastructure-as-a-Service (IaaS), Platform-as-a-Service (PaaS), Software-as-a-Service (SaaS), the technology of virtualization that has enabled these services, as well as technologies for managing a cloud infrastructure. Since cloud computing covers a broad range of technologies, this talk will mainly focus on a few important concepts, but will also mention other relevant issues and provide pointers to references for those who would like to learn more about cloud computing.

November 1st

2:45 - 4:15, Room 213, Faculty of Engineering Integrated Research Bldg, Main Campus
Hwann-Tzong Chen, National Tsing Hua University
Title: Video Object Cosegmentation
Abstract: The problem of video object cosegmentation concerns the task of segmenting the common object in a pair of video sequences. We present a new algorithm that works on super-voxels in videos to solve this task. The algorithm computes i) the intra-video relative motion derived from dense optical flow and ii) the inter-video co-features based on Gaussian mixture models. The experimental results show that, by integrating the intra-video and inter-video information, our algorithm is able to obtain better results of segmenting video objects.

November 8th

2:45 - 5:00, Room 213, Faculty of Engineering Integrated Research Bldg, Main Campus (two lectures)
Alan Johnston, UCL
Title: Dynamic Face Perception
Abstract: It is now common to think of faces as represented in a multidimensional face space in the brain. The space is centred on the mean face and facial identity is represented as a direction in the space. This idea is examined in more detail. In particular, the issue of what would be the mean face, what are the axes of the space, how we encode family resemblance and how we encode dynamic facial expression will be considered.

Takeshi Tokuyama, Tohoku University
Title: Area minimization of convex hull of movable objects: Algorithmic convex Kakeya problem
Abstract: Given a set of line segments in the plane, not necessarily finite, what is a convex region of smallest area that contains a translate of each input segment? This question can be seen as a generalization of Kakeya's problem of finding a convex region of smallest area such that a needle can be rotated through 360 degrees within this region. We show that there is always an optimal region that is a triangle, and we give an optimal Theta(nlog n)-time algorithm to compute such a triangle for a given set of n segments. We also show that, if the goal is to minimize the perimeter of the region instead of its area, then placing the segments with their midpoint at the origin and taking their convex hull results in an optimal solution. Finally, we show that for any compact convex figure G, the smallest enclosing disk of G is a smallest-perimeter region containing a translate of every rotated copy of G. (Joint work with Hee-Kap Ahn, Sang Won Bae, Otfried Cheong,Joachim Gudmundsson, and Antoine Vigneron)

November 29th

2:45 - 4:15, Room 213, Faculty of Engineering Integrated Research Bldg, Main Campus
Jon Noel, McGill University
Title: A Proof of Ohba's List Colouring Conjecture
Abstract: A classical problem in graph colouring asks the following question: Is it possible to colour the vertices of a graph from a fixed set of available colours such that every pair of vertices which are joined by an edge are assigned to different colours? Such a colouring is called a proper colouring of the graph. The minimum number of colours required to obtain a proper colouring is called the chromatic number of the graph. In list colouring, we would like to find a proper colouring when each vertex has its own list of available colours; two vertices may have different lists. The minimum number of colours required at each vertex to guarantee that a colouring of this type exists is called the list chromatic number. Surprisingly, the list chromatic number can be much larger than the chromatic number. In this talk, we prove a conjecture, made by Kyoji Ohba in 2002, which says that if the number of vertices in a graph is at most two times the chromatic number plus one, then the list chromatic number equals the chromatic number. That is, for graphs of this type, list colouring and classical colouring require the same number of available colours at each vertex.

December 13th

2:45 - 4:15, Room 213, Faculty of Engineering Integrated Research Bldg, Main Campus
Hong Shen, University of Adelaide
Title: Effective Methods for Survivable Network Design
Abstract: For various types of contemporary networks resulted by information communication technology advancement, with their rapidly increasing size, topological complexity and application variety, network survivability is attracting more and more attention nowadays. How to minimize resource (bandwidth) usage while ensuring a guaranteed network survivability is an interesting problem of both theoretical significance and application value, which is called the survivable network design problem in the general setting. It is especially important for the emerging cloud computing, datacenter networks and the next generation Internet that have a high degree of interconnection complexity and fault dynamicity. A practical appearance of this problem that arises in a wide range of applications is the so-called Steiner network problem that generalizes the classical Steiner tree (1-connected) problem and assumes a uniform connectivity (survivability) across the subset of nodes (terminals) concerned. When this subset spans to the whole network, the Steiner network problem reduces to the connected spanning subgraph problem which was shown NP-hard. Numerous efforts have been made in searching for effective methods to obtain approximation solutions for these problems in the past decades. In this talk, I will first provide an overview on the existing solutions to the above three problems. I will then introduce our recent work on constructing a 2-connected Steiner network that has an approximation ratio of 2 to the optimal (minimum cost) solution through progressive improvement on a set of disjoint shortest path pairs incident with each terminal. Next I will show how to compute a 6-approximation augmentation on the 2-connected Steiner network to achieve connectivity 3 by constructing a minimum-cost in-arborescence in the directed complete graph with vertices being all terminals and each edge weight the shortest path distance between the end vertices. Finally I will conclude the talk by presenting some open problems for future research.

December 20th

2:45 - 4:15, Room 213, Faculty of Engineering Integrated Research Bldg, Main Campus
David Kinny, Kyoto University
Title: Why losing can be harder than winning
Abstract: Combinatorial Game Theory (CGT) deals with finite turn-taking games of perfect information, such as Tic-Tac-Toe, Nim, Chess and Go. Impartial games are those, such as Nim, where the legal moves do not depend on whose turn it is to move. Those impartial games where the last player to move wins are easily solved by the Sprague-Grundy Theorem, discovered more than 75 years ago. Misere games, where by contrast the last player to move loses, can be very much harder to analyse, and some apparently simple ones still remain unsolved. In effect, the winner of a misere game is the the player with a guaranteed losing strategy for the normal game. In this talk I will review some basic elements of CGT, illustrating them with interesting old and new variants of the game of Nim, and present some recent significant progress in analyzing and solving misere impartial games.

January 10th

2:45 - 4:15, Room 213, Faculty of Engineering Integrated Research Bldg, Main Campus
Chien-Chung Huang , MPI Saarbruecken
Title: Uniqueness and Social Cost of Equilibria in Atomic Splittable Routing Games
Abstract: In an atomic splittable routing game, each player controls a non-negligible, splittable flow in a network. Each edge has a delay that is a function of the total flow on the edge. Each player seeks a routing strategy to minimize the total delay of his flow, measured as the sum over edges of his flow on the edge times that edge's delay. In this setting, a flow is at a Nash equilibrium if no player can unilaterally alter his individual flow and reduce his total cost.

In this talk, I will discuss two topics about equilibria in atomic splittable routing games. The first is the uniqueness of Nash equilibria. I will give a complete characterization on the multiplicity of equilibria based on graph topology. The second topic is the social cost of equilibria when players form coalitions. In particular, I will talk about the conditions under which the post-collusion equilibrium is guaranteed to have less social cost than the pre-collusion equilibrium.

January 17th

2:45 - 4:15, Room 213, Faculty of Engineering Integrated Research Bldg, Main Campus
Alvaro Cassinelli, University of Tokyo
Title: Performing Time, Space and Light
Abstract: In this talk I will present some of my works as a media artist and researcher and show how, depending on the academic/social context, these can flip as a Necker cube between the realms of Media Art and HCI research. I will talk in particular of some attempts at embodying elusive realities such as Time, Space and Light, so they can they can be actors and perform with humans in public spaces. This include for example deformable walls that remember the past, robots made of light, video “plumbing” that transverse continents, laser auras that extend emotions (capriciously), the use of the body as an interface as well as a surface for projection, the introduction of minimalistic, iconic displays as an alternative to the pixilated screen, as well as several experiments on mediating the Self with technology (including devices to help people with disabilities), and new paradigms for a sustainable ubiquitous computing world - among other miscellaneous but related topics.

January 24th

2:45 - 4:15, Room 213, Faculty of Engineering Integrated Research Bldg, Main Campus
Taiji Suzuki, University of Tokyo
Title: Fast Algorithm and Statistical Theory of Multiple Kernel Learning
Abstract: In this talk, we present two topics of our recent works on Multiple Kernel Learning (MKL): Fast optimization algorithm for general convex loss functions and statistical convergence analysis for various types of regularization functions. (Optimization algorithm): The proposed optimization algorithm of MKL is a proximal minimization method that utilizes the ``smoothed'' dual objective function and converges super-linearly. The sparsity of the intermediate solution plays a crucial role for the efficiency of the proposed algorithm. Consequently our algorithm scales well with increasing number of kernels. Experimental results show that our algorithm is favorable against existing methods especially when the number of kernels is large (> 1000). (Statistical convergence analysis): According to the numerical experiments, the sparse L1 regularization is sometimes outperformed by dense type regularizations. Motivated by this fact, we derive new fast learning rates for various types of regularizations including non-sparse type regularizations, e.g. elasticnet and Lp-norm, and compare those rates with that of the L1 regularization. Then we discuss which regularization is preferred depending on conditions of the true function. This work is a collaboration with Ryota Tomioka and Masashi Sugiyama.

January 30th

4:30 - 6:00, Room 213, Faculty of Engineering Integrated Research Bldg, Main Campus
Gael Dias, University of Caen Basse-Normandie
Title: First order association measures for Multiword Unit Extraction
Abstract: In this talk, I will present different research on collocation extraction. First, I will present the motivations of the identification of multiword units for natural language processing. Then, I will present state-of-the-art methodologies and access their limitations. To solve some existing problems, I will present a language-independent solution called SENTA. Finally, due to its limitations, the hybrid solution called HELAS will be presented.

January 31st

2:45 - 4:15, Room 213, Faculty of Engineering Integrated Research Bldg, Main Campus
Lorenzo Rosasco, Massachusetts Institute of Technology, Italian Institute of Technology
Title: Towards a statistical theory of learning data representation
Abstract: Data representation is known to be the critical step in most supervised learning tasks. Yet, the question of finding good representations has often relied on domain expertise to engineer ad hoc features. In recent years, a variety of unsupervised feature learning algorithms have been proposed to learn representations from data. The general intuition is that an unsupervised feature learning step can adaptively reduce the dimensionality of the data, eventually leading to improved performances. Indeed this intuition is often confirmed by promising empirical results. In this talk we will discuss an approach that provides a solid theoretical foundation to some of these intuitions and empirical observations. We show that a large class of algorithms for learning data representation can be cast in a common framework and shown to define regularized estimators of the data generating distribution. Interestingly, our work establishes a novel connections between concepts in Optimal Transport, Optimal Quantization, and Learning Theory.