Schedule for Fall 2013 - Kyoto University Informatics Seminar

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 (総合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
    • 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 Two-machine Flow Shop Scheduling with One Transporter, hosted by K. Iwama
    • Gael Dias (Normandie University), Temporal Web Information Retrieval: Text and Image, hosted by A. Jatowt
  • November 28 Irregular Schedule: following the first talk, 16:30-18:00 in the same room
    • Robert Kowalski (Imperial College London), English, Logic, and the Language of Thought, hosted by A. Yamamoto
    • Ming-Yang Kao (Northwestern University), Combinatorial Algorithms and Computational Complexity for DNA Self-Assembly, hosted by K. Iwama
  • December 19 Lecture is moved to January, because of the speaker's schedule change.
    • 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 black-box: faster optimization methods for non-smooth and big-data problems, hosted by M. Cuturi

Abstracts and Detailed Information

October 3

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合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 BR-matching is a non-crossing geometric perfect matching where each segment has one endpoint in B and one in R. Such a matching always exists. Two BR-matchings are compatible if their union is also non-crossing. We prove that, for any two distinct BR-matchings M and M', there exists a sequence of BR-matchings M = M_1, …, M_k = M' such that M_{i-1} 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 (総合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 expander-like graphs called amplifiers, and a healthy dose of gadgeteering.

October 17

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合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 so-called 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 almost-monochromatic triangles in an undirected, edge-colored 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 (総合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 system-on-chips (SoCs), especially under the increasing impact of process variations and device aging. Furthermore, the situation is exacerbated by real-time 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 cross-layer reliability solutions, from device-level modeling of leading reliability mechanisms, to circuit-level 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 neural-inspired design with emerging memory devices, helping illustrate their potential in reliable computation.

November 7

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合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 real-world 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 ground-truth 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 (総合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 (総合7), Main Campus
Xin HAN, Dalian University of Technology
Title: Complexity of Two-machine 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 NP-hard in the strong sense by 4-Partition problem.

November 28

14:45 -16:15, Joho 2, Research Bldg. No.7 (総合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 implicitly-dated 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 (総合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 (総合7), Main Campus
Ming-Yang Kao, Northwestern University
Title: Combinatorial Algorithms and Computational Complexity for DNA Self-Assembly
Abstract: Self-assembly 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. Self-assembly is ubiquitous, and there are many kinds of self-assembly. This talk will focus on algorithmic DNA self-assembly. 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 self-assembly, discuss basic models for algorithmic DNA self-assembly, 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 (総合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 non-negative 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 non-negative 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 (総合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 (総合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 (総合7), Main Campus
Mark Schmidt, Simon Fraser University
Title: Opening up the black-box: faster optimization methods for non-smooth and big-data problems.

The way we solve continuous optimization problems is changing. The ever-growing size of data sets, along with the increasingly-important use of non-smooth 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 L1-regularization. I will discuss methods for optimizing a general smooth loss with L1-regularization, and how methods are increasingly using the idea of two-metric minimum-norm sub-gradient projection. 2. Group Sparsity: How the problem of learning the graph structure in conditional random fields motivates the use of group L1-regularization. This has applications ranging from computer vision to analyzing mutual funds to non-Pearlian causality. I will discuss the class of inexact proximal quasi-Newton 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 higher-order interactions motivates the use of structured sparsity, which allows sparsity patterns such as hierarchical constraints. I will discuss inexact proximal-gradient methods for solving this class of problems. 4. Big-N Problems: In many data-fitting problems we need to optimize the sum of a large number of functions. First-order deterministic-gradient methods achieve a linear convergence rate for this problem but need to evaluate every function on every iteration. Stochastic-gradient 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 stochastic-gradient methods, but for certain problems it provably outperforms all possible first-order deterministic-gradient methods in terms of passes through the data.

Slides