Equivalence of Systematic Linear Data Structures and Matrix Rigidity 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 omegaleft(fracnrlog mright) 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 Omega(n32r) for redundancy r geq sqrtn 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, Kouckxc3xbd, Loff, and Mukhopadhyay.

Optimal Deterministic Shallow Cuttings for 3d Dominance Ranges Shallow cuttings are one of the most fundamental tools in range searching as many problems in the field admit efficient static data structures due to their application. We present the first efficient deterministic algorithms that, given n threedimensional points, construct optimalsize (single and multiple) shallow cuttings for orthogonal dominance ranges. Specifically, we show how to construct a single shallow cutting in                                                                           Oleft( nlog nright)                                                                          :138,290,worstcase time, using                                                                           Oleft( nright)                                                                          space. We also show that the same complexity suffices to construct simultaneously a logarithmic number of shallow cuttings on the input pointset. Our algorithms are optimal in the comparison and algebraiccomparison models, and constitute an important step forwards as the first improvement over previous deterministic polynomialtime guarantees by Matousek (Comput Geom 2(3):169xe2x80x93186, 1992) and Agarwal et al. (SIAM J Comput 29(3):912xe2x80x93953, 2000) matching the complexity of the optimal deteministic algorithm for the more general 3d halfspace ranges by Chan and Tsakalidis (Discrete Comput Geom 56(4):866xe2x80x93881, 2016). Our methods yield :138,290,worstcase efficient preprocessing algorithms for a series of important orthogonal range searching problems in the pointer machine and the wordRAM models, where such shallow cuttings are utilized to support queries efficiently.