Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams

DOI10.1007/978-3-642-02927-1_43zbMath1248.68217OpenAlexW1878833411MaRDI QIDQ3638059

Sudipto Guha, Zhi-Yi Huang

Publication date: 14 July 2009

Published in: Automata, Languages and Programming (Search for Journal in Brave)

Full work available at URL: https://repository.upenn.edu/cgi/viewcontent.cgi?article=1426&context=cis_papers

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Related Items

Unnamed Item ⋮ Lower Bounds for Number-in-Hand Multiparty Communication Complexity, Made Easy ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Space-efficient estimation of statistics over sub-sampled streams