We study the problem of proving lower bounds in the Priority CRCW PRAM for the query time of several fundamental and well-studied data structures, motivated by the observation that, for many basic data structure problems, no proven limits on parallelism exist. We use the cell-probe model, which has been studied extensively in the sequential setting and where for all the problems under consideration, Ω(log n/log log n) query time lowers bound exist. However, we report that in the parallel settings, some of these problems become "easy", i.e., admit solutions with constant query time in the Common CRCW PRAM using polylogarithmic number of processors, while others become "hard", via the following result. We prove query time lower bounds (in the Priority CRCW PRAM model) via a careful combination of some of the cell-probe lower bound techniques with ideas from the PRAM area. While the actual statement of the lower bounds are complicated, they all can be simplified to an Ω(log log n) query time lower bound under the most reasonable settings, and with polylogarithmic processors. The fact that all these problems admit an Ω(log n/log log n) query lower bound in the sequential settings implies that most of the cell-probe lower bound techniques cannot be generalized to the CRCW PRAM model of computation, meaning, the landscape of data structure lower bounds in the CRCW PRAM models of computation is more complicated.

We introduce the contiguous art gallery problem which is to guard the boundary of a simple polygon with a minimum number of guards such that each guard covers exactly one contiguous portion of the boundary. Art gallery problems are often NP-hard. In particular, it is NP-hard to minimize the number of guards to see the boundary of a simple polygon, without the contiguity constraint. This paper is a merge of three concurrent works [Ahmad Biniaz et al., 2024; Magnus Christian Ring Merrild et al., 2024; Eliot W. Robson et al., 2024] each showing that (surprisingly) the contiguous art gallery problem is solvable in polynomial time. The common idea of all three approaches is developing a greedy function that maps a point on the boundary to the furthest point on the boundary so that the contiguous interval along the boundary between them could be guarded by one guard. Repeatedly applying this function immediately leads to an OPT+1 approximation. By studying this greedy algorithm, we present three different approaches that achieve an optimal solution. The first and second approach apply this greedy algorithm from different points on the boundary that could be found in advance or on the fly while traversing along the boundary (respectively). The third approach represents this function as a piecewise linear rational function, which can be reduced to an abstract arc cover problem involving infinite families of arcs. We identify other problems that can be represented by similar functions, and solve them via the third approach. From the combinatorial point of view, we show that any n-vertex polygon can be guarded by at most ⌊(n-2)/2⌋ guards. This bound is tight because there are polygons that require this many guards.