Publications
[Near-Optimal Relative Error Streaming Quantile Estimation via Elastic Compactors]
Elena Gribelyuk, Pachara Sawettamalya, Hongxun Wu, Huacheng Yu
In submission
Optimal quantile estimation: beyond the comparison model
Meghal Gupta, Mihir Singhal, Hongxun Wu
FOCS 2024
Sample-Based Matroid Prophet Inequalities
Hu Fu, Pinyan Lu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, Qianfan Zhang
EC 2024
A Faster Algorithm for Pigeonhole Equal Sums
Ce Jin, Hongxun Wu
ICALP 2024
Simple & Optimal Quantile Sketch: Combining Greenwald-Khanna with Khanna-Greenwald
Elena Gribelyuk, Pachara Sawettamalya, Hongxun Wu, Huacheng Yu
PODS 2024
The Cost of Parallelizing Boosting
Xin Lyu, Hongxun Wu, Junzhao Yang
SODA 2024
Breaking the Metric Voting Distortion Barrier
Moses Charikar, Prasanna Ramakrishnan, Kangning Wang, Hongxun Wu
SODA 2024
Tight Time-Space Lower Bounds for Constant-Pass Learning
Xin Lyu, Avishay Tal, Hongxun Wu, Junzhao Yang
FOCS 2023
Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting
Lijie Chen, William Hoza, Xin Lyu, Avishay Tal, Hongxun Wu
FOCS 2023
Faster Matrix Multiplication via Asymmetric Hashing
Ran Duan, Hongxun Wu, Renfei Zhou
FOCS 2023
New PRGs for Unbounded-width/Adaptive-order Read-once Branching Programs
Lijie Chen, Xin Lyu, Avishay Tal, Hongxun Wu
ICALP 2023
(Fractional) Online Stochastic Matching via Fine-Grained Offline Statistics
Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu
STOC 2022
Truly Low-Space Element Distinctness and Subset Sum via Pseudorandom Hash Functions
Lijie Chen, Ce Jin, R. Ryan Williams, Hongxun Wu
SODA 2022
Oblivious Online Contention Resolution Schemes
Hu Fu, Pinyan Lu, Zhihao Gavin Tang, Abner Turkieltaub, Hongxun Wu, Jinzhao Wu, Qianfan Zhang
SOSA 2022
Random Order Vertex Arrival Contention Resolution Schemes for Matching, with Applications
Hu Fu, Pinyan Lu, Zhihao Gavin Tang, Hongxun Wu, Jinzhao Wu, Qianfan Zhang
ICALP 2021
Fast and Simple Modular Subset Sum
Kyriakos Axiotis, Arturs Backurs, Karl Bringmann, Ce Jin, Vasileios Nakos, Christos Tzamos, Hongxun Wu
SOSA 2021
Near-Optimal Algorithm for Constructing Greedy Consensus Tree
Hongxun Wu
ICALP 2020
Faster Algorithms for All Pairs Non-Decreasing Paths Problem
Ran Duan, Ce Jin, Hongxun Wu
ICALP 2019
Fast Modular Subset Sum using Linear Sketching
Kyriakos Axiotis, Arturs Backurs, Ce Jin, Christos Tzamos, Hongxun Wu
SODA 2019
A Simple Near-Linear Pseudopolynomial Time Randomized Algorithm for Subset Sum
Ce Jin and Hongxun Wu
SOSA 2019
Single-Source Bottleneck Path Algorithm Faster than Sorting for Sparse Graphs
Ran Duan, Kaifeng Lyu, Hongxun Wu, Yuanhang Xie
Preprint