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