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 ndimensional 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 vectormatrixvector 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 vectormatrixvector 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:135:20},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959771344},
ISSN = {18688969},
year = {2020},
volume = {151},
editor = {Thomas Vidick},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2020/11720},
URN = {urn:nbn:de:0030drops117204},
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 