Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming
From MaRDI portal
Publication:5428851
DOI10.1007/978-3-540-73420-8_61zbMath1171.68839OpenAlexW1533319289MaRDI QIDQ5428851
Publication date: 28 November 2007
Published in: Automata, Languages and Programming (Search for Journal in Brave)
Full work available at URL: https://repository.upenn.edu/cgi/viewcontent.cgi?article=1390&context=cis_papers
Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) General topics in the theory of algorithms (68W01)
Related Items (4)
Sleeping on the job: energy-efficient and robust broadcast for radio networks ⋮ Optimal collapsing protocol for multiparty pointer jumping ⋮ Interior-Point-Based Online Stochastic Bin Packing ⋮ Best-order streaming model
This page was built for publication: Lower Bounds for Quantile Estimation in Random-Order and Multi-pass Streaming