Speaker:

Zhiyi Huang (University of Hong Kong)

Time:

• 09:30-10:30 Beijing Time
• June 13, 2025 (Friday)

Venue:

518, Research Building 4

Abstract:

The Correlated Pandora’s Problem posed by Chawla et al. (2020) generalizes the classical Pandora’s Problem by allowing the numbers inside the Pandora’s boxes to be correlated. It also generalizes the Min Sum Set Cover problem, and is related to the Uniform Decision Tree problem. This paper gives an optimal 4-approximation for the Correlated Pandora’s Problem, matching the lower bound of 4 from Min Sum Set Cover.

Speaker Bio:

Zhiyi Huang is an Associate Professor of Computer Science at the University of Hong Kong. Before joining HKU, he was a postdoc at Stanford University from 2013 to 2014, working with Tim Roughgarden. He earned his Ph.D. from the University of Pennsylvania under the supervision of Sampath Kannan and Aaron Roth in 2013, and a bachelor’s degree in 2008 from the first “Yao Class” founded by Andrew Chi-Chih Yao at Tsinghua University.

Zhiyi works broadly on algorithms, focusing on the role of information—and its flip-side, uncertainty—in computation. He is interested in algorithms for sequential decision-making under uncertainty (online algorithms), learning based on different forms of information (learning theory), incentivizing self-interested agents to share private information (mechanism design), and disclosing one kind of information while keeping the other confidential (differential privacy).

Zhiyi’s research was recognized by several Best Paper Awards, including those from ESA 2024 (Track S), FOCS 2020, and SPAA 2015. He was also the recipient of an Excellent Young Scientists Fund (HK & Macau) by NSFC, an Early Career Award by RGC Hong Kong, a Morris and Dorothy Rubinoff Dissertation Award, and a Simons Graduate Fellowship in Theoretical Computer Science.