Prof. Chung-Shou Liao

National Tsing Hua University

From online algorithms to learning-augmented online algorithms

In the past three decades, online algorithms have gained a considerable amount of research interest. The concept of online algorithms has been actually applied to a variety of practical computational models with uncertainty such as online learning and incremental learning, while the only theoretical measure to evaluate the performance of an online algorithm is “competitive ratio”; that is, comparing an online algorithm to an offline optimal adversary. The fundamental question in the field of online algorithms is that: Can we evaluate the quality of an online algorithm in a better way? A new concept, called learning-augmented algorithms, or algorithms with prediction, was proposed to answer the question in 2018. Precisely, the notion exploits the prediction power of popular machine learning models to obtain the robustness guarantees of competitive analysis for online algorithms. In this talk, we first introduce several classical problems as well as their online algorithms. Next, we discuss not only how to devise online algorithms with learning prediction in order to obtain a better theoretical guarantee, but also how to provide a way to look into different performance evaluation beyond the most common worst-case

Prof. Meng-Tsung Tsai

Academia Sinica

Finding Sparse Supereulerian Certificates via Sampling with Applications to Dynamic Graph Streams

Restricted input access is required for efficient computations on large graphs. Under the restriction, the standard algorithms for many graph computation problems do not have an efficient implementation and thus need an alternative. In this talk, we will use finding a sparse spanning Eulerian subgraph for dynamic graphs as an example to introduce some essentials of the algorithm design and lower bound techniques for dynamic streams. This example demonstrates a significant separation between the Hamiltonian and supereulerian tests on their space complexities in dynamic streams. In contrast, no comparable separation on their time complexities is known.

Prof. 張瑞雄


Cloud Computing: The next Frontier


2006年,亞馬遜公司推出了他們的雲端計算平台Amazon Web Services(AWS),為企業和個人提供了基於互聯網的計算和儲存服務。隨後,微軟也推出了自己的雲端計算平台Azure,並在2008年開始提供服務。Google也推出了Google Cloud平台,使得這些平台成為現今最大的雲端計算供應商。