Simulation beats richness: new data-structure lower bounds

DOI10.1145/3188745.3188874MaRDI QIDQ5230358zbMATH OpenOpenAlexFDO

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

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

communication complexitydata structureslifting theoremrichness methodsimulation theoremvector-matrix-vector product

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 1263186
• A comparison of two lower-bound methods for communication complexity
• On data structures and asymmetric communication complexity
• The pattern matrix method
• scientific article; zbMATH DE number 1769898

Cited in

(5)

• On data structures and asymmetric communication complexity
• scientific article; zbMATH DE number 3974286 (Why is no real title available?)
• 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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5230358)