Simulation beats richness: new data-structure lower bounds

DOI10.1145/3188745.3188874zbMath1427.68057OpenAlexW2809332496MaRDI QIDQ5230358

Sagnik Mukhopadhyay, Arkadev Chattopadhyay, Michal Koucký, Bruno Loff

Publication date: 22 August 2019

Published in: Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1145/3188745.3188874

zbMATH Keywords

lifting theoremdata structurescommunication complexitysimulation theoremrichness methodvector-matrix-vector product

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Communication complexity, information complexity (68Q11)

Related Items (3)

Lifting Theorems for Equality ⋮ Query-To-Communication Lifting for BPP Using Inner Product ⋮ Query-to-Communication Lifting Using Low-Discrepancy Gadgets

This page was built for publication: Simulation beats richness: new data-structure lower bounds