Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

All reports by Author Hongxun Wu:

TR24-065 | 6th April 2024
Meghal Gupta, Mihir Singhal, Hongxun Wu

Optimal quantile estimation: beyond the comparison model

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 >>>

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

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 >>>

ISSN 1433-8092 | Imprint