Hongxun Wu

Hongxun Wu

Auto-generated profile, based on publicly available information

Hongxun Wu

UC Berkeley, Berkeley, USA

Research Focus & Metrics

Academic Career Length

3Years (2024-Present)

(Calculated once Scilit publication data is synced: current year − year of first publication + 1)

Representative Publications

View All Publications
8 November 2024 in Journal of the ACM
Verified
Journal Article
Open access
MCMoses Charikar
Moses Charikar
PRPrasanna Ramakrishnan
Prasanna Ramakrishnan
KWKangning Wang
Kangning Wang
HWHongxun Wu
Hongxun Wu
We consider the following well-studied problem of metric distortion in social choice. Suppose that we have an election with n voters and m candidates located in a shared metric space. We would like to design a voting rule that chooses a candidate whose average distance to the voters is small. However, instead of having direct access to the distances in the metric space, the voting rule obtains, from each voter, a ranked list of the candidates in order of distance. Can we design a rule that, regardless of the election instance and underlying metric space, chooses a candidate whose cost differs from the true optimum by only a small factor (known as the distortion )? A long line of work culminated in finding optimal deterministic voting rules with metric distortion 3. However, for randomized voting rules, there is still a significant gap in our understanding: even though the best lower bound is substantially lower at 2.112, the best upper bound is still 3, which is attained even by simple rules such as Random Dictatorship. Finding a randomized rule that guarantees distortion 3 - ɛ for some constant ɛ has been a major challenge in computational social choice, as prevalent approaches to designing voting rules are known to be insufficient. In particular, such a voting rule must use information beyond aggregate comparisons between pairs of candidates, and cannot only assign positive probability to candidates that are voters’ top choices. In this work, we give a rule that guarantees distortion less than 2.753. To do so, we study a handful of voting rules that are new to the problem. One is Maximal Lotteries , a rule based on the Nash equilibrium of a natural zero-sum game that dates back to the 1960s. The others are novel rules that can be thought of as hybrids of Random Dictatorship and the Copeland rule. None of these rules can beat distortion 3 alone; however, a careful randomization between Maximal Lotteries and any of the novel rules can.

10 May 2024 in Proceedings of the ACM on Management of Data
Verified
Journal Article
Open access
EGElena Gribelyuk
Elena Gribelyuk
PSPachara Sawettamalya
Pachara Sawettamalya
HWHongxun Wu
Hongxun Wu
HYHuacheng Yu
Huacheng Yu
Estimating the ε-approximate quantiles or ranks of a stream is a fundamental task in data monitoring. Given a stream x_1,..., x_n from a universe \mathcalU with total order, an additive-error quantile sketch \mathcalM allows us to approximate the rank of any query y\in \mathcalU up to additive ε n error. In 2001, Greenwald and Khanna gave a deterministic algorithm (GK sketch) that solves the ε-approximate quantiles estimation problem using O(ε^-1 łog(ε n)) space \citegreenwald2001space ; recently, this algorithm was shown to be optimal by Cormode and Vesleý in 2020 \citecormode2020tight. However, due to the intricacy of the GK sketch and its analysis, over-simplified versions of the algorithm are implemented in practical applications, often without any known theoretical guarantees. In fact, it has remained an open question whether the GK sketch can be simplified while maintaining the optimal space bound. In this paper, we resolve this open question by giving a simplified deterministic algorithm that stores at most (2 + o(1))ε^-1 łog (ε n) elements and solves the additive-error quantile estimation problem; as a side benefit, our algorithm achieves a smaller constant factor than the \frac11 2 ε^-1 łog(ε n) space bound in the original GK sketch~\citegreenwald2001space. Our algorithm features an easier analysis and still achieves the same optimal asymptotic space complexity as the original GK sketch. Lastly, our simplification enables an efficient data structure implementation, with a worst-case runtime of O(łog(1/ε) + łog łog (ε n)) per-element for the ordinary ε-approximate quantile estimation problem. Also, for the related "weighted'' quantile estimation problem, we give efficient data structures for our simplified algorithm which guarantee a worst-case per-element runtime of O(łog(1/ε) + łog łog (ε W_n/w_\textrmmin )), achieving an improvement over the previous upper bound of \citeassadi2023generalizing.

8 July 2024
Verified
Conference Paper
Open access
HFHu Fu
Hu Fu
PLPinyan Lu
Pinyan Lu
ZTZhihao Gavin Tang
Zhihao Gavin Tang
HWHongxun Wu
Hongxun Wu
JWJinzhao Wu
Jinzhao Wu
QZQianfan Zhang
Qianfan Zhang
The classical prophet inequalities problem introduced by Krengel and Sucheston [1977, 1978] assumed complete knowledge of distributions. However, such an assumption may be unrealistic both in practice and for some applications. We study matroid prophet inequalities when distributions are unknown and accessible only through samples. While single-sample prophet inequalities for special matroids are known, no constant-factor competitive algorithm with even a sublinear number of samples was known for general matroids. Adding more to the stake, the single-sample version of the question for general matroids has close (two-way) connections with the long-standing matroid secretary conjecture. In this work, we give a (1/4 - ε)-competitive matroid prophet inequality with only Oε (poly log n) samples. Our algorithm consists of two parts: (i) a novel quantile-based reduction from matroid prophet inequalities to online contention resolution schemes (OCRSs) with Oε(log n) samples, and (ii) a (1/4 - ε)-selectable matroid OCRS with Oε (poly log n) samples which carefully addresses an adaptivity challenge. A full version of this paper can be found at https://arxiv.org/abs/2406.12799.