All reports by Author Hongxun Wu:

__
TR24-065
| 6th April 2024
__

Meghal Gupta, Mihir Singhal, Hongxun Wu#### Optimal quantile estimation: beyond the comparison model

__
TR23-114
| 8th August 2023
__

Lijie Chen, William Hoza, Xin Lyu, Avishay Tal, Hongxun Wu#### Weighted Pseudorandom Generators via Inverse Analysis of Random Walks and Shortcutting

Meghal Gupta, Mihir Singhal, Hongxun Wu

Estimating quantiles is one of the foundational problems of data sketching. Given $n$ elements $x_1, x_2, \dots, x_n$ from some universe of size $U$ arriving in a data stream, a quantile sketch estimates the rank of any element with additive error at most $\varepsilon n$. A low-space algorithm solving this ... more >>>

Lijie Chen, William Hoza, Xin Lyu, Avishay Tal, Hongxun Wu

A weighted pseudorandom generator (WPRG) is a generalization of a pseudorandom generator (PRG) in which, roughly speaking, probabilities are replaced with weights that are permitted to be positive or negative. We present new explicit constructions of WPRGs that fool certain classes of standard-order read-once branching programs. In particular, our WPRGs ... more >>>