Tight cell probe bounds for succinct Boolean matrix-vector multiplication

DOI10.1145/3188745.3188830zbMath1427.68056arXiv1711.04467OpenAlexW2963650845MaRDI QIDQ5230382

Kasper Green Larsen, Lior Kamma, Diptarka Chakraborty

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://arxiv.org/abs/1711.04467

zbMATH Keywords

lower boundsuccinct data structurecell probe modelBoolean matrix-vector multiplication

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Data structures (68P05) Boolean and Hadamard matrices (15B34)

Related Items (2)

Pushing the online Boolean matrix-vector multiplication conjecture off-line and identifying its easy cases ⋮ A simple primal-dual approximation algorithm for 2-edge-connected spanning subgraphs

This page was built for publication: Tight cell probe bounds for succinct Boolean matrix-vector multiplication