Theory Day in Taiwan (2024)

Shih-Han Hung (EE, NTU)

Title: Certified Randomness from Quantum Supremacy

---

Abstract:

After three decades of research in quantum computing theory and experiments, the world has seen the emergence of noisy quantum devices capable of solving special sampling problems using 50-60 qubits or approximately 100 photons in a way that is believed to achieve quantum computational supremacy, i.e., the quantum devices outperform any existing classical computer for these tasks. Despite these achievements, whether they lead to practical applications have remained unclear. In this talk, I will discuss the latest developments in quantum supremacy proposals and applications from them. Then I will focus on our recent work on certified randomness from random circuit sampling, where we show that, whenever the outputs of these experiments pass the now-standard Linear Cross-Entropy Benchmark (LXEB), under plausible hardness assumptions they necessarily contain min-entropy proportional to the number of qubits. This novel application challenges us to further explore the limitations of quantum devices, and repurposes the supremacy experiment for practical uses. This talk is based on joint work with Scott Aaronson.

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

---

Abstract:

A cactus representation of an undirected graph G, introduced by Dinitz et al. in 1976, is an edge sparsifier H of size O(n) where any global mincut on H corresponds to a global mincut on G and vice versa. Cactus representations are essential objects for connectivity augmentation problems and for maintaining minimum cuts subject to edge insertions. This type of cactus representation has been generalized to Steiner cactus. For a specified set of terminals T, a Steiner cactus for T captures all possible ways of partitioning T with the minimum possible cut value. This can be further generalized to hypercactus for hypergraphs.

In a long line of work on fast constructions of cactus and its generalizations, a near-linear time construction of cactus was shown by Karger and Panigrahi in 2009. Unfortunately, their technique based on tree packing inherently does not generalize. In this talk, I will introduce our work on constructing a Steiner cactus by reducing the problem to a polylogarithmic number of maximum flow instances. With the state-of-the-art maxflow algorithms, we are able to achieve an almost-linear time algorithm for constructing Steiner cactus (and hypercactus), improving upon previous quadratic-ish algorithms, which require Ω(n) maxflows by Chekuri and Xu in 2017, and Ω(|T|) maxflows by Dinitz and Vainshtein in 1994.

This is joint work with Zhongtian He and Thatchaphol Saranurak.

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.