Schedule for Fall 2013
Informatics Seminar, Perspectives in Informatics 5
Unless noted otherwise, all talks 14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus

 Stefan Langerman (ULB), Bichromatic compatible matchings, hosted by D. Avis

 Michael Lampis (Kyoto University), Baby steps towards TSP inapproximability, hosted by K. Iwama

 Jesper Jansson (Kyoto University), Counting Triangles to Compute the Rooted Triplet Distance between Galled Trees, hosted by K. Iwama

 Yu Cao (Arizona State University), Designing Smarter SoCs for Reliability, hosted by K. Iwama
 October 31 Cancelled

 Kyoung Mu Lee (Seoul National University), Visual Tracking by Uncertainty Analysis, hosted by X. Liang
 November 11 Irregular Schedule: Monday
 Philip Knight (University of Strathclyde), The How and Why of Balancing, hosted by M. Cuturi

 Xin HAN (Dalian University of Technology), Complexity of Twomachine Flow Shop Scheduling with One Transporter, hosted by K. Iwama
 November 21 Autumn Festival

 Gael Dias (Normandie University), Temporal Web Information Retrieval: Text and Image, hosted by A. Jatowt
 November 28 Irregular Schedule: following the first talk, 16:3018:00 in the same room
 Robert Kowalski (Imperial College London), English, Logic, and the Language of Thought, hosted by A. Yamamoto
 December 5 Cancelled

 MingYang Kao (Northwestern University), Combinatorial Algorithms and Computational Complexity for DNA SelfAssembly, hosted by K. Iwama
 December 19 Lecture is moved to January, because of the speaker's schedule change.
 December 26 Cancelled
 January 9 Cancelled

 Md. Saidur Rahman (Bangladesh University of Engineering and Technology), Pairwise Compatibility Graphs, hosted by K. Iwama

 Skip Jordan (Hokkaido University), Experimental Descriptive Complexity, hosted by D. Avis

 Hans Tiwary (Charles University), Extended formulations: recent results and outlook, hosted by D. Avis

 Mark Schmidt (Simon Fraser University), Opening up the blackbox: faster optimization methods for nonsmooth and bigdata problems, hosted by M. Cuturi
Abstracts and Detailed Information
October 3
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Stefan Langerman, ULB
Title: Bichromatic compatible matchings
Abstract: For a set R of n red points and a set B of $n$ blue points, a
BRmatching is a noncrossing geometric perfect matching where each
segment has one endpoint in B and one in R. Such a matching always
exists. Two BRmatchings are compatible if their union is also
noncrossing. We prove that, for any two distinct BRmatchings M
and M', there exists a sequence of BRmatchings M = M_1, …, M_k
= M' such that M_{i1} is compatible with M_i.
Joint work with Greg Aloupis, Luis Barba, and Diane L. Souvaine
October 10
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Michael Lampis, Kyoto University
Title: Baby steps towards TSP inapproximability
Abstract: Although the Traveling Salesman Problem is one of the most intensely studied problems in combinatorics, the best currently known hardness of approximation bounds are a long way off the guarantee provided by the best approximation algorithms. In this talk we will discuss two recent hardness proofs which slightly improve the inapproximability bounds for both TSP and ATSP, after more than a decade. Though the gap between upper and lower bounds remains huge, our approach will emphasize simplicity and modularity, leaving some reasonable hope that further improvements are still possible. The main ingredients used will be Constraint Satisfaction Problems where each variable appears a bounded number of times, some special classes of expanderlike graphs called amplifiers, and a healthy dose of gadgeteering.
October 17
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Jesper Jansson, Kyoto University
Title: Counting Triangles to Compute the Rooted Triplet Distance between Galled Trees
Abstract: We consider a generalization of the rooted triplet distance between
two phylogenetic trees to two phylogenetic networks.
A naive algorithm can compute this distance in O(n^3) time, where n is
the number of leaf labels in the input networks.
We show that if each of the given phylogenetic networks is a socalled
galled tree
then the rooted triplet distance can be computed in
o(n^{2.687}) time.
Our bound is obtained by reducing the problem to that of counting
monochromatic and almostmonochromatic triangles in an undirected,
edgecolored graph.
To count different types of colored triangles in a graph efficiently, we
extend an existing technique based on matrix multiplication and obtain
some new algorithmic results that may be of independent interest.
[Joint work with Andrzej Lingas.]
October 24
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Yu Cao, Arizona State University
Title: Designing Smarter SoCs for Reliability
Abstract: Circuit and system reliability has emerged as one of the top design concerns of future complex systemonchips (SoCs), especially under the increasing impact of process variations and device aging. Furthermore, the situation is exacerbated by realtime uncertainties, such as workload and environmental conditions, which dynamically influence the degradation rate. Traditional approach has been focused on either process improvement or simple design guard banding, which is too conservative and insufficient to cope with these threats. To build reliable systems from unreliable devices, it is essential to develop an integrated reliability analysis and management framework that understands reliability physics, identifies failure signatures, detects the fault during run time, and adapts the design for resilience.
This talk will first present a suite of crosslayer reliability solutions, from devicelevel modeling of leading reliability mechanisms, to circuitlevel failure prediction and diagnosis, and to adaptive design techniques that sense and mitigate the degradation. As validated by silicon data, the combination of these solutions provides the vital basis to deliver robust yet efficient systems. Beyond the silicon roadmap, this talk will further outreach to neuralinspired design with emerging memory devices, helping illustrate their potential in reliable computation.
November 7
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Kyoung Mu Lee, Seoul National University
Title: Visual Tracking by Uncertainty Analysis
Abstract: Visual object tracking is one of the important problems in computer Vision. To robustly track a target in a realworld scenario, most conventional tracking methods formulate the tracking problem by the Bayesian approach, where the goal is to find the best state that maximizes the posterior under the assumption that the distribution models are perfectly known. However, usually this assumption is not valid in practice and the resulting MAP state does not always correspond to the groundtruth state of a target. In this talk, we consider the modeling uncertainty problem in probabilistic visual tracking and propose two novel approaches to solve it, namely Bayesian Model Averaging (BMA) and Interval Analysis (IA). The philosophy of these two approaches is to best utilize the information of multiple candidates of posteriors. Experimental results demonstrate the superiority of the proposed approaches over existing methods.
November 11
Irregular Schedule: Monday
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Philip Knight, University of Strathclyde
Title: The How and Why of Balancing
Abstract: We consider the problem of taking a matrix A and finding diagonal matrices D and E such that the rows and columns of B = DAE satisfy some specific constraints. Examples of constraints are that
 the row and column sums of B should all equal one;
 the norms of the rows and columns of B should all be equal;
 the row and column sums of B should take values specified by vectors p and q.
Simple iterative algorithms for solving these problems have been known for nearly a century. We provide a simple framework for describing these algorithms that allow us to develop robust convergence results and describe a straightforward approach to accelerate the rate of convergence.
We describe some of the diverse applications of balancing with examples from preconditioning, clustering, network analysis and psephology.
This is joint work with Kerem Akartunali (Strathclyde), Daniel Ruiz (ENSEEIHT, Toulouse) and Bora Ucar (ENS, Lyon).
November 14
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Xin HAN, Dalian University of Technology
Title: Complexity of Twomachine Flow Shop Scheduling with One Transporter
Abstract: In this paper, we study a flow shop scheduling problem, in which there are a set of n jobs and two machines, A and B. Each job has to be processed on machine A first, then transported by a vehicle to machine B, finally processed on machine B.
The interstage transporter can carry at most two jobs between the machines at a time. When the transport carry items from machine A to machine B, it will take time T; when it is back from machine B to machine A, it will take zero time. And there is an unlimited buffer on each machine to store jobs that will be processed. The complexity of the problem is open in Journal of Scheduling 2001. We prove the problem is NPhard in the strong sense by 4Partition problem.
November 28
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Gael Dias, Normandie University
Title: Temporal Web Information Retrieval: Text and Image
Abstract: In recent years, the temporal dimension has taken a real importance in multimedia information retrieval. In this presentation, we will present different important research trends and we will detail the specific problem of (1) disambiguating implicitlydated queries and and consequent applications; and (2) time tagging images based on text and image features.
November 28
16:30 18:00, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Robert Kowalski, Imperial College London
Title: English, Logic, and the Language of Thought
Abstract: The purpose of a natural language, such as Japanese or English, is to help a writer (or speaker) communicate thoughts to a reader (or listener). The reader’s task is to try to understand those thoughts, and the writer’s task is to make the reader’s task as easy as possible. Many books about English writing style give excellent advice about how to write more effectively, but with little, if any, justification. In this talk, I will present a theory that aims to justify that advice. The theory is based on the hypothesis that readers understand a written text by translating it into a mental representation, which has a simple logical form. By expressing the text in a style that is closer to its logical form, writers can make the text easier to understand.
Note: A special workshop following this lecture is held on 29 Nov. More information is here.
December 12
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
MingYang Kao, Northwestern University
Title: Combinatorial Algorithms and Computational Complexity for DNA SelfAssembly
Abstract: Selfassembly is a phenomenon in which something complex (such as structures, patterns, and behaviors) emerges through local interactions of simple components with limited or no global control. Selfassembly is ubiquitous, and there are many kinds of selfassembly. This talk will focus on algorithmic DNA selfassembly. With this technology, one can encode computer programs into DNAs and execute the programs to guide DNAs to bind into desired nanostructures. For this reason, this emerging field lies in the intersection of nanotechnology and theoretical computer science (i.e., combinatorial algorithms and computational complexity) among other disciplines. In this talk, we will briefly look at examples of selfassembly, discuss basic models for algorithmic DNA selfassembly, survey some recent algorithmic and complexity results, and pose open problems for further research.
Slides
January 16
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Md. Saidur Rahman, Bangladesh University of Engineering and Technology
Title: Pairwise Compatibility Graphs
Abstract: Let T be an edge weighted tree, let d_T(u, v) be the sum of the weights of the edges on the path from u to v in T, and let d_min and d_max be two nonnegative real numbers such that d_min ≤ d_max.
Then a pairwise compatibility graph of T for d_min and d_max is a graph G = (V,E), where each vertex u' in V corresponds to a leaf u of T and there is an
edge (u', v') in E if and only if d_min ≤ d_T(u, v) ≤ d_max.
A graph G is called a pairwise compatibility graph (PCG) if there exists an edge weighted tree T and two nonnegative real numbers d_min and d_max such that G is a pairwise compatibility graph of T for d_min and d_max.
In 2003, Kerney et al. introduced the concept of PCG and showed how to use them
to model evolutionary relationship among a set of organisms.
They conjectured that every graph is a PCG.
In 2010, we have proved that there exists a graph of 15 vertices that is not
a PCG.
On the other hand, recently Calamoneri, Frascaria and Sinaimeri proved that every graph with at most seven vertices is a PCG.
In this talk I show a graph of eight vertices that is not a PCG.
Moreover, I show that several classes of graphs such as trees, cycles, cactus graphs, block graphs, ladder graphs are pairwise compatibility graphs.
I also discuss the hardness of PCG recognition problem.
The talk is based on my joint works with M. N. Yanhaona, M. S. Bayzid, K. S. M. T. Hossain, S. A. Salma, S. Durocher and D. Mondal.
January 23
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Skip Jordan, Hokkaido University
Title: Experimental Descriptive Complexity
Abstract: In many situations, we hope to find a program or function that satisfies
certain properties. For example, in program synthesis we desire a
program that is correct and preferably fast and in complexity theory, we
often look for reductions between computational problems.
Descriptive complexity theory is a logical approach to complexity theory
that represents programs and functions as formulas in various logics,
where expressive power corresponds to computational resources. In this
presentation, we give an overview of recent experimental work in
descriptive complexity. Experimental descriptive complexity uses
computers to try to understand issues in complexity theory and uses
techniques from descriptive complexity in other fields. We give an
introduction to basic notions from descriptive complexity and describe
several of these applications.
January 30
14:45 16:15, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Hans Tiwary, Charles University
Title: Extended formulations: recent results and outlook
Abstract: A polytope Q is called an extended formulation of a polytope P if
P is a projection of Q. Recently various remarkable results have
been proved about the complexity of extended formulations. In this
talk we survey some of these results and discuss the outlook for
future work, specially in the context of complexity theoretic problems
like P=?NP.
February 14
13:30 15:00, Joho 2, Research Bldg. No.7 (総合７), Main Campus
Mark Schmidt, Simon Fraser University
Title: Opening up the blackbox: faster optimization methods for nonsmooth and bigdata problems.
The way we solve continuous optimization problems is changing. The evergrowing size of data sets, along with the increasinglyimportant use of nonsmooth objective functions, has forced various scientific and engineering communities to consider 'opening up the black box' and developing custom solvers for their problems. In this talk I will overview my recent work along these lines, highlighting the various applications that motivated the work. The talk will accessible to a general computer science audience and discuss four topics: 1. Sparsity: How a medical imaging application led me to be interested in feature selection, regularization, and their combination through L1regularization. I will discuss methods for optimizing a general smooth loss with L1regularization, and how methods are increasingly using the idea of twometric minimumnorm subgradient projection. 2. Group Sparsity: How the problem of learning the graph structure in conditional random fields motivates the use of group L1regularization. This has applications ranging from computer vision to analyzing mutual funds to nonPearlian causality. I will discuss the class of inexact proximal quasiNewton methods, which are especially suited to optimization problems where we have an expensive objective function but a simple regularizer or simple constraints. 3. Structured Sparsity: How the problem of structure learning with higherorder interactions motivates the use of structured sparsity, which allows sparsity patterns such as hierarchical constraints. I will discuss inexact proximalgradient methods for solving this class of problems. 4. BigN Problems: In many datafitting problems we need to optimize the sum of a large number of functions. Firstorder deterministicgradient methods achieve a linear convergence rate for this problem but need to evaluate every function on every iteration. Stochasticgradient methods only need to evaluate one function, but have a sublinear convergence rate. I will present the stochastic average gradient (SAG) algorithm, which achieves the best of both worlds. SAG not only provably outperforms all possible standard stochasticgradient methods, but for certain problems it provably outperforms all possible firstorder deterministicgradient methods in terms of passes through the data.