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

 Chingman 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

 HwannTzong 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

 November Festival , No seminar

 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

 ChienChung 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 BasseNormandie), 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
Chingman 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 repackaging of existing Internetrelated 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 InfrastructureasaService (IaaS), PlatformasaService (PaaS),
SoftwareasaService (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
HwannTzong 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 supervoxels in videos to solve this task. The algorithm computes i) the intravideo relative motion derived from dense optical ﬂow and ii) the intervideo cofeatures based on Gaussian mixture models. The experimental results show that, by integrating the intravideo and intervideo 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 smallestperimeter region containing a translate of every rotated copy of G.
(Joint work with HeeKap 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 socalled Steiner network problem that generalizes the classical Steiner tree (1connected) 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 NPhard. 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 2connected 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 6approximation augmentation on the 2connected Steiner network to achieve connectivity 3 by constructing a minimumcost inarborescence 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 turntaking
games of perfect information, such as TicTacToe, 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 SpragueGrundy 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
ChienChung 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
nonnegligible, 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 postcollusion equilibrium is
guaranteed to have less social cost than the precollusion
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 superlinearly. 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 nonsparse type regularizations, e.g. elasticnet and Lpnorm, 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 BasseNormandie
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 stateoftheart methodologies and access their limitations. To solve some existing problems, I will present a languageindependent 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.