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.

I am an Associate Professor and the Head of Computer Science Division at School of Computing and Data Science, the University of Hong Kong. Before joining HKU, I was a postdoc at Stanford University from 2013 to 2014, working with Tim Roughgarden. I received my 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.

 

I work broadly on algorithms, focusing on the role of information—and its flip-side, uncertainty—in computation. I am 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). My research was recognized by several Best Paper Awards from ESA 2024 (Track S), FOCS 2020, and SPAA 2015. I also received an RGC Research Fellow Scheme and an Early Career Award by RGC Hong Kong, an Excellent Young Scientists Fund (HK & Macau) by NSFC, a Morris and Dorothy Rubinoff Dissertation Award, and a Simons Graduate Fellowship in Theoretical Computer Science.