Detailed Program
Program at a Glance   Biographies

Conference Room 1, Center of Academic Activities

Tuesday, June 16




Opening Remarks
Director Ming-Syan Chen of CITI, Academia Sinica, Taiwan
Director Pen-Chung Yew of IIS, Academia Sinica, Taiwan

Algorithms Session I
Session Chair: Dai-Wei Wang


Keynote Speech
“Evolving Computer Science”,
Franco Preparata (Brown University - USA)

A review of the historical evolution of computer science and, in particular, of algorithmics, is compelling motivation for a broadening of the curricular spectrum of our discipline.

10:40 – 11:00 Break

Session Chair: Ming-Tat Ko

“Some Algorithmic Aspects of Skeletal Structures”,
Franz Aurenhammer (University of Technology, Graz - Austria)

The medial axis is a skeletal structure that captures important topological and geometric information on a given shape in the plane. Most known algorithms compute the medial axis using Voronoi diagram algorithms. I will show that the other way round is possible, too, and discuss some advantages of this approach.
An alternative skeletal structure, which is solely composed of linear pieces, is the straight skeleton of a planar polygon.

However, and in contrast to the medial axis, no efficient practical algorithms are known for computing straight skeletons. I will briefly discuss that this is not true for the discrete version of the problem (pixel skeletons). Pixel algorithms based on the shrinking process for straight skeletons run faster than commonly used pixel medial axis algorithms based on the Euclidean distance transform.
“How Fast Can We Solve Problems Without Using Any Extra Array? Constant Working Space Algorithms for Geometric Problems”,
Tetsuo Asano (Japan Advanced Institute of Science and Technology)

Recent progress in computer systems has provided programmers with unlimited amount of working storage for their programs.Nowadays there are full of space-inefficient programs which use too much storage and become too slow if sufficiently large storage is not available.
Another requirement of limited working storage comes from applications to built-in or embedded software in highly functional hardware. Digital cameras and scanners are good examples. We measure the space efficiency of an algorithm by the number of working storage cells (or the amount of working space) used by the algorithm. Ultimate efficiency is achieved when only constant numbers of variables are used in addition to input array(s).
Another excellent example is sensor networks; with the drops of price of flash memory even a large number of cheap sensors can be equipped with huge-volume flash drive. While the data measured by the sensor must be stored onboard for processing, and need to be written, it is preferable to avoid writing to the flash drive, as this is a slow and expensive operation which reduces the flash drive's lifetime. Hence we would like to use only higher level memory (e.g.\ only CPU registers) that we write into, and perform only read operations on the flash drive. We call such an algorithm {\it a constant-working-space algorithm}.
The constant-working-space algorithms should not use any working space of size depending on input size and an array storing input data is given as read-only memory so that any value in the array cannot be changed.The same framework has been studied in the complexity theory.A typical problem is a so-called {\it ``st-connectivity''} problem: given an undirected graph $G$ of $n$ vertices in read-only memory and specified two arbitrary vertices $s$ and $t$ in $G$, determine whether they are connected or not using only constant number of variables of $O(\log n)$ bits. Reingold succeeded in proving that the problem can be solved in polynomial time. It is a great break-through in this direction.

In this talk I will present constant-working-space algorithms for geometric problems for drawing a Voronoi diagram, Delaunay triangulation, and minimum spanning tree for a given set of points in the plane, and also one for linear programming of two variables.
“Studying Geometric Graph Properties of Road Networks Through an Algorithmic Lens”,
Michael Goodrich (University of California, Irvine - USA)

We study real-world road networks from an algorithmic perspective, focusing on empirical studies that yield useful properties of road networks that can be exploited in the design of fast algorithms that deal with geographic data. Unlike previous approaches, our study is not based on the assumption that road networks are planar graphs.

Indeed, based on the a number of experiments we have performed on the road networks of the 50 United States and District of Columbia, we provide strong empirical evidence that road networks are quite non-planar. Our approach therefore instead is directed at finding algorithmically-motivated properties of road networks as non-planar geometric graphs, focusing on alternative properties of road networks that can still lead to efficient algorithms for such problems as shortest paths and Voronoi diagrams. In particular, we study road networks as multiscale-dispersed graphs, which is a concept we formalize in terms of disk neighborhood systems. This approach allows us to develop fast algorithms for road networks without making any additional assumptions about the distribution of edge weights. In fact, our algorithms can allow for non-metric weights.

12:30 – 14:00 Lunch Break

Algorithms Session II
Session Chair: Tsan-Sheng Hsu

Keynote Speech
“Some algorithms and data structures for IP-Lookup and conflict detection”,
Thomas Ottmann (Institute of Informatics - Germany)

When an internet router receives a packet it uses the destination address in the packet and a routing table in order to forward it to the next hop. This IP-lookup problem can be considered as the one-dimensional case of a more general packet classification problem where the router has to classify packets into different flows. We present new data structures for the representation of dynamic range router tables that employ most specific range matching. We introduce the min-augmented range trees and priority search pennants allowing updates and IP lookups. We also discuss how these structures can be used in order to detect and resolve conflicts in dynamic router tables.

15:00 – 15:30 Break
Session Chair: Jan-Ming Ho

“Randomized Motion Planning: From Intelligent CAD to Computer Animation to Protein Folding”,
Nancy Amato (Texas A&M University - USA)

Motion planning arises in many application domains such as computer animation (digital actors), mixed reality systems and intelligent CAD (virtual prototyping and training), and even computational biology and chemistry (protein folding and drug design).Surprisingly, a single class of planners, called probabilistic roadmap methods (PRMs), has proven effective on problems from all these domains. Strengths of PRMs, in addition to versatility, are simplicity and efficiency, even in high-dimensional configuration spaces.

In this talk, we describe the PRM framework and give an overview of several PRM variants developed in our group.We describe in more detail our work related to virtual prototyping, computer animation, and protein folding. For virtual prototyping, we show that in some cases a hybrid system incorporating both an automatic planner and haptic user input leads to superior results. For computation animation, we describe new PRM-based techniques for planning sophisticated group behaviors such as flocking and herding.Finally, we describe our application of PRMs to simulate molecular motions, such as protein and RNA folding. More information regarding our work, including movies, can be found at
“Open Rectangle-of-Influence Drawings of Inner Triangulated Plane Graphs”,
Takao Nishizeki (Tohoku University - Japan)
A straight-line drawing of a plane graph is called an open rectangle-of-influence drawing if there is no vertex in the proper inside of the axis-parallel rectangle defined by the two ends of every edge. In an inner triangulated plane graph, every inner face is a triangle although the outer face is not necessarily a triangle. In this talk, we first present a sufficient condition for an inner triangulated plane graph G to have an open rectangle-of-influence drawing; the condition is expressed in terms of a labeling of angles of a sub-graph of G. We then present an O(n^1.5/log n)-time algorithm to examine whether G satisfies the condition and, if so, construct an open rectangle-of-influence drawing of G on an (n-1) x(n-1) integer grid, where n is the number of vertices in G.
“Approximating Points by a Piecewise Linear Function”,
Danny Chen (University of Notre Dame - USA)

Approximating a set of points by a piecewise linear function is an extensively studied topic in computational geometry. In this talk, we present an array of new results in this topic in the $i$-D space ($i=2,3$), including points with weights, approximation with violations, using step functions or more generally piecewise linear functions, etc.

We consider both the min-\# version (i.e., given an error tolerance $\epsilon$, minimizing the size $k$ of the approximating function) and the min-$\epsilon$ version (i.e., given a size $k$ of the approximating function, minimizing the error tolerance $\epsilon$) of the problems.Our algorithms are based on several frameworks that utilize new algorithmic techniques and geometric data structures, which may be of independent interest and find other applications.Our algorithms either improve the previous best-known solutions or are the first known results for the target problems.


Wednesday, June 17



Digital Archives Session
Session Chair: Mark, Hong-Yuan Liao


Opening Remarks
Ming-Syan Chen (Academia Sinica - Taiwan)

“Implementation of User-Centric Identity using OpenID”,
Ching-Teng Hsiao (Academia Sinica - Taiwan)
A native web 2.0 platform to help distributing content of National Digital Archives Program (NDAP) has been raised in early 2007. This platform was expected to reduce the friction for accessing the archived content, enable users' redistribution of content, encourage user participation and prompt dialogues between creators and consumers. With this goal, we implemented a user-centric identity system that allows users to use one ID to login to a variety of services so to add web 2.0 community ingredients into NDAP. The service, started to serve on September 2008, and is the only OpenID provider in Taiwan.
“Multimedia Signal Processing and Its Applications to Taiwan e-Learning & Digital Archives Program”,
Mark, Hong-Yuan Liao (Academia Sinica - Taiwan)
The Taiwan e-Learning and Digital Archives Program (TELDAP) is sponsored by the National Science Council of Taiwan (the second 5-year term, from 2007-2011). As the principal investigator of the R&D division of TELDAP, my responsibility is to lead my colleagues to deal with a large amount of digitized aged pictures and aged films. Since the collected aged pictures/films were taken long time ago and the sensing devices used were analog by nature, the quality of these pictures/videos is very poor. We call the related techniques developed for improving the quality of the above mentioned digitized pictures or videos the pre-processing techniques. After pre-processing, the next step one needs to do is to develop useful tools to properly store, annotate, and retrieve the digitized multimedia.In this talk, I will talk about related multimedia signal processing techniques specifically developed for dealing with the multimedia data collected by the TELDAP.

12:00 – 13:30 Lunch Break

Information Security Session
Session Chair: Tzong-Chen Wu

Keynote Speech
“Quantum Computational Geometry and Quantum Cryptography”,
Hiroshi Imai (University of Tokyo - Japan)

Quantum information science is an emerging field of investigating the power of quantum computing and communication, and exploring a new paradigm of quantum cryptography.
In the first part of this talk, computational geometry is demonstrated to play an essential role in computing the capacity of a quantum channel. A quantum channel transfers classical information by sending and receiving quantum states through the channel, and its capacity is the maximum amount of transferable classical information through the channel. The capacity is characterized by the smallest ball enclosing the set of received quantum states in quantum information geometry space where the proximity is defined by the quantum divergence (or, quantum relative entropy). In this nonlinear space, still fundamental techniques for Voronoi diagrams and the smallest enclosing ball apply with some complications.

In the seconf part, realization of a generalized decoy Quantum Key Distribution (QKD) system is presented from theoretical and experimental viewpoints. Influence of an eavesdropper is modeled as a noise in a quantum channel. Using theoretical results related to the capacity of a quantum channel, the amount of information which the eavesdropper may obtain is theoretically analyzed to derive a specific computable estimate for it. This theory has been shown to work in a real quantum cryptographic system by experiments so that the security of a distributed key is guaranteed quantitatively.

Taiwan Information Security Industry
“Beyond Hardware and Software –“Operation Intelligence” for Security Monitoring”,
Simon Chang (Acer - Taiwan)

While most people have resorted to security defense hardware and software to build their information defense weaponry, experience has demonstrated that these means are less than sufficient to provide a comprehensive defense strategy.

Acer has engaged in “secured operation” service business since 2000 and has since developed considerable operation expertise to complement the hardware and software landscape for information security services.? Using a commercial Security Information and Event Management (SIEM) platform as its base, very fundamental network and system behavior were collected and analyzed in near-realtime to yield a library of attack and malware behavior models.? Correlation rules were then developed to detect these behaviors automatically or semi-automatically.? In the past 3 years, Acer uncovered more than 1000 new malware that were undetectable by commercial HW/SW from its customerbase.? This talk will highlight the philosophy and approach adopted to achieve the described results.? Other than practically applying these rules in daily monitoring operation service, this set of rich malware dataset was also feedback to the TWISC community for academic research.
“The Inspiration of Mass Web Attack and 911 : Next Generation of Penetration Testing and Software Security”,
Wayne Huang (Armorize - Taiwan)

15:00 – 15:30 Break
Session Chair: Michael Kao

International Collaboration
“Three years later: A review of successes and challenges in computer security”,
Doug Tygar (University of California, Berkeley - USA)
We look back on three years of collaboration as part of the iCAST program and mark successes and ongoing challenges.? We also discuss those features of computer security that seem to make it such a fascinating challenge.? Finally, we consider what progress we can hope for in the coming years.
“Building Secure Systems with Code Attestation”,
Adrian Perrig (Carnegie Mellon University - USA)

Attestation is a promising approach for building secure systems. The recent development of a Trusted Platform Module (TPM) by the Trusted Computing Group (TCG) that is starting to be deployed in common laptop and desktop platforms is fueling research in attestation mechanisms.
In this talk, I will present approaches on how to build secure systems with advanced TPM architectures. In particular, we have designed an approach for fine-grained attestation that enables the design of efficient secure distributed systems. We demonstrate this approach by designing a secure version of the BGP routing protocol.

We have also developed software-based attestation mechanisms for legacy systems without relying on trusted hardware. Our approach enables a verifier to obtain the property of untampered code execution on a legacy Pentium IV workstation.

18:30 – 21:00 Banquet (by invitation only)