Theory Day in Taiwan (2024)

Shih-Han Hung (EE, NTU)

Title: Certified Randomness from Quantum Supremacy

---

Biography:

Shih-Han Hung is an Assistant Professor in the Department of Electrical Engineering at National Taiwan University. Previously, he held short-term postdoc positions at Academia Sinica and National Taiwan University. Before that, he was a postdoc at the University of Texas at Austin, where he was hosted by Scott Aaronson. He earned his Ph.D. degree in Computer Science at the University of Maryland, where he was advised by Andrew Childs. He received a bachelor’s degree in Electrical Engineering and a master’s degree in Physics at National Taiwan University, where he was advised by Shih-I Chu. Shih-Han is broadly interested in quantum information science, with recent focus on demonstrating quantum advantage, verification of quantum devices, and their applications. He has been working on various problems in quantum query complexity, computational complexity theory, (post-)quantum cryptography, and quantum programming languages.

Ya-Chun Liang (CSIE, NCKU)

Title: Scheduling with Obligatory Tests

---

Abstract:

Motivated by settings such as medical treatments or aircraft maintenance, we consider a scheduling problem with jobs that consist of two operations: a test and a processing part. The time required to execute the test is known in advance, while the time required for the processing part becomes known only upon completion of the test. We use competitive analysis to study algorithms for minimizing the sum of completion times for $n$ given jobs on a single machine. As our main result, we prove, using a novel analysis technique, that the natural $1$-SORT algorithm has a competitive ratio of at most 1.861. For the special case of uniform test times, we show that a simple threshold-based algorithm has a competitive ratio of at most 1.585. We also prove a lower bound, showing that no deterministic algorithm can be better than $\sqrt{2}$-competitive, even in the case of uniform test times.

Joint work with Konstantinos Dogeas and Thomas Erlebach.

Biography:

Ya-Chun Liang is currently an Assistant Professor in the Department of Computer Science and Information Engineering at National Cheng Kung University. She earned her M.S. degree in Industrial Engineering and Engineering Management from National Tsing Hua University, Hsinchu, Taiwan. She then completed a dual Ph.D. in Electrical Engineering and Electronics at the University of Liverpool, U.K., and in Industrial Engineering and Engineering Management at National Tsing Hua University. After earning her Ph.D., she conducted postdoctoral research at the Data Science Institute, Columbia University. Her research interests include various interdisciplinary optimization problems, with a particular focus on developing online and dynamic algorithms for scheduling problems with real-world applications.

Shang-En Huang (CSIE, NTU)

Title: Fast Algorithms for Cactus Representations

---

Biography:

Shang-En Huang is currently an assistant professor in the Department of Computer Science and Information Engineering (CSIE), National Taiwan University. Previously, he had the honor of being advised by Seth Pettie and obtained his Ph.D. degree from University of Michigan. He then became a postdoc at Boston College advised by Hsin-Hao Su. Shang-En's research interests include dynamic graph data structures and algorithms and distributed graph algorithms.