Theory Day in Taiwan (2017C)

Date: Saturday, 2 December, 2017
Location: Auditorium 106, New Building, Institute of Information Science, Academia Sinica, Taipei



Past Theory Days in Taiwan: 2016A@Taipei, 2016B@HsinChu, 2017A@Taipei, 2017B@HsinChu

The Theory Day in Taiwan is an experimental one-day event that aims to stimulate interaction and discussion for TCS researchers in Taiwan and nearby countries. We plan to host 3-4 hour-long talks in general TCS area with long breaks for interaction. The meeting is free and open to everyone; in particular, students are encouraged to attend. We also create mailing lists for disseminating theory-related events in Taiwan. Please subscribe NOW for more information about Theory Day and Theory Event in Taiwan!

Speakers: Danny Chen (Notre Dame), Hsien-Chih Chang (UIUC), Yi-Jun Chang (U Michigan), and Meng-Tsung Tsai (NCTU)

Subscribe to the Mailing List !

Subscribe


We create two mailing lists:
Theory Event Announcement for announcement of theory events.
Theory Talk Announcement for announcement of talks in TCS.

Theory Day Information

Date: Saturday, 2 December, 2017
Location:Auditorium 106, New Building, Institute of Information Science, Academia Sinica

Schedule

Speaker: Danny Chen, Hsien-Chih Chang, Yi-Jun Chang, and Meng-Tsung Tsai


9.30 - 10.30
 
Talk 1: Danny Chen, Geometric Algorithms for Biomedical Problems
10.30 - 11.00
 
 Break and Discussion
11.00 - 12.00
 
 Talk 2: Hsien-Chih Chang, Discrete and Computational Topology: Untangling Planar Curves (and Beyond)
12.00 - 2.00
 
Lunch
2.00 - 3.00
 
 Talk 3: Yi-Jun Chang , Complexity of Local Distributed Graph Problems
3.00 - 3.30
 
 Break and Discussion
3.30 - 4.30
 
 Talk 4: Meng-Tsung Tsai , Streaming Algorithms for Convex Hull
4.30 - 5.00
 
 Break and Discussion

Talk Abstracts.

Danny Chen

Title: Geometric Algorithms for Biomedical Problems


Abstract: Computer technology plays a crucial role in modern medicine, health care, and life sciences, especially in medical imaging, human genome study, clinical diagnosis and prognosis, treatment planning and optimization, treatment response evaluation and monitoring, and medical data management and analysis. As computer technology rapidly evolves, computer science solutions will inevitably become an integral part of modern medicine and health care. Computational research and applications on modeling, formulating, solving, and analyzing core problems in medicine and health care are not only critical, but are actually indispensable!

Recently emerging deep learning (DL) techniques have achieved remarkably high quality results for many computer vision tasks, such as image classification, object detection, and semantic segmentation, largely outperforming traditional image processing methods. In this talk, we present new approaches based on DL techniques for solving a set of medical imaging problems, such as segmentation and analysis of glial cells, analysis of the relations between glial cells and brain tumors, segmentation of neuron cells, and new training strategies for deep learning using sparse medical image data. We develop new deep learning models, based on fully convolutional networks (FCN), recurrent neural networks (RNN), and active learning, to effectively tackle the target medical imaging problems. For example, we combine FCN and RNN for 3D biomedical image segmentation; we propose a new complete bipartite network model for neuron cell segmentation. Further, we show that simply applying DL techniques alone is often insufficient to solve medical imaging problems. Hence, we construct new methods to complement and work with DL techniques. For example, we devise a new cell cutting method based on k-terminal cut in geometric graphs, which complements the voxel-level segmentation of FCN to produce object-level segmentation of 3D glial cells. We show how to combine a set of FCNs with an approximation algorithm for the maximum k-set cover problem to form a new training strategy that takes significantly less annotation data. A key point we make is that DL is often used as one main step in our approaches, which is complemented by other main steps. We also show experimental data and results to illustrate the practical applications of our new DL approaches.


Hsien-Chih Chang

Title: Discrete and Computational Topology: Untangling Planar Curves (and Beyond)


Abstract: Planar curves are one of the most fundamental objects one can think of in both mathematics and computer science. Apart from their obvious usage in computational geometry and topology, interesting applications have been found in optimizations, knot theory, and more.

In this talk we will take a road trip together through a small part of the landscape. We will start with various way of representing the planar curve and its deformations, together with its appearance and many uses in various disciplines of math and cs. Then we focus on a particular set of operations called homotopy moves --- a discrete version of deformations one can perform on curves. We will sketch the ideas behind a few recent results on untangling planar curves using homotopy moves, its generalization on surfaces, and the implications on solving planar graph optimization problems using electrical transformations.

There is no assumptions on background knowledge in topology, and open questions (not restricted to planar curves) will be mentioned throughout the talk.


Yi-Jun Chang

Title: Complexity of Local Distributed Graph Problems


Abstract: Locality is a central concept in distributed computing. Roughly speaking, a local algorithm is a distributed algorithm on a network where the output of each device v only depends on its local neighbors (i.e., within a small radius of v). In this talk. I will present my works (arXiv:1704.06297 and arXiv:1602.08166) regarding the following fundamental questions about the nature of the distributed LOCAL model: (i) How to classify the distributed problems according to their complexities? (ii) How much does randomness help? (iii) Can we solve more problems given more time? (iv) Are there any natural “complete problems” in some complexity class? (v) Is there a “time hierarchy theorem” in the LOCAL model?




Meng-Tsung Tsai

Title: Streaming Algorithms for Convex Hull


Abstract: Given a set P of n points in R2, the convex hull of P can be computed efficiently using O(n) space by many classic algorithms. For large point set whose size exceeds the size s of working space, these algorithms cannot be directly used. The current best streaming algorithm for computing the convex hull is complicated because it needs to solve a set of linear programs.

In this talk, we will present simpler and faster streaming algorithms for computing the convex hull. Our algorithms are simpler in the sense that the used techniques are elementary. We also prove the near-optimality of our algorithms by lower-bounding the communication complexity for this problem.


About

The Theory Day in Taiwan is an experimental one-day event that aims to stimulate interaction and discussion for TCS researchers in Taiwan and nearby countries. We plan to host 3-4 hour-long talks in general TCS area with long breaks for interaction. The meeting is free and open to everyone; in particular, students are encouraged to attend.
Please contact theoryday.tw@gmail.com if you have any question.

Organizers
Ho-Lin Chen (NTU), Yu-Chi Chen (Academia Sinica),
Kai-Min Chung (Academia Sinica), and Chung-Shou Liao (NTHU)