License: 
Creative Commons Attribution 3.0 Unported license (CC BY 3.0)
When quoting this document, please refer to the following
DOI: 10.4230/LIPIcs.ITCS.2020.35
URN: urn:nbn:de:0030-drops-117204
URL: http://dagstuhl.sunsite.rwth-aachen.de/volltexte/2020/11720/
Natarajan Ramamoorthy, Sivaramakrishnan ;
Rashtchian, Cyrus
Equivalence of Systematic Linear Data Structures and Matrix Rigidity
Abstract
Recently, Dvir, Golovnev, and Weinstein have shown that sufficiently strong lower bounds for linear data structures would imply new bounds for rigid matrices. However, their result utilizes an algorithm that requires an NP oracle, and hence, the rigid matrices are not explicit. In this work, we derive an equivalence between rigidity and the systematic linear model of data structures. For the n-dimensional inner product problem with m queries, we prove that lower bounds on the query time imply rigidity lower bounds for the query set itself. In particular, an explicit lower bound of ω(n/r log m) for r redundant storage bits would yield better rigidity parameters than the best bounds due to Alon, Panigrahy, and Yekhanin. We also prove a converse result, showing that rigid matrices directly correspond to hard query sets for the systematic linear model. As an application, we prove that the set of vectors obtained from rank one binary matrices is rigid with parameters matching the known results for explicit sets. This implies that the vector-matrix-vector problem requires query time Ω(n^(3/2)/r) for redundancy r ≥ √n in the systematic linear model, improving a result of Chakraborty, Kamma, and Larsen. Finally, we prove a cell probe lower bound for the vector-matrix-vector problem in the high error regime, improving a result of Chattopadhyay, Koucký, Loff, and Mukhopadhyay.
BibTeX - Entry
@InProceedings{natarajanramamoorthy_et_al:LIPIcs:2020:11720,
author = {Sivaramakrishnan Natarajan Ramamoorthy and Cyrus Rashtchian},
title = {{Equivalence of Systematic Linear Data Structures and Matrix Rigidity}},
booktitle = {11th Innovations in Theoretical Computer Science Conference (ITCS 2020)},
pages = {35:1--35:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {978-3-95977-134-4},
ISSN = {1868-8969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11720},
URN = {urn:nbn:de:0030-drops-117204},
doi = {10.4230/LIPIcs.ITCS.2020.35},
annote = {Keywords: matrix rigidity, systematic linear data structures, cell probe model, communication complexity}
}
|
Keywords: |
|
matrix rigidity, systematic linear data structures, cell probe model, communication complexity |
|
Collection: |
|
11th Innovations in Theoretical Computer Science Conference (ITCS 2020) |
|
Issue Date: |
|
2020 |
|
Date of publication: |
|
06.01.2020 |
