Theory of Computing Systems

Abstract The Suffix Array is a classic text index enabling on-line pattern matching queries via simple binary search. The main drawback of the Suffix Array is that it takes linear space in the text’s length, even when the text itself is extremely compressible. Several works in the literature showed that the Suffix Array can be compressed, but they all rely on complex succinct data structures which in practice tend to exhibit poor cache locality and thus significantly slow down queries. In this paper, we propose a new simple and very efficient solution to this problem by presenting the Suffixient Array : a tiny subset of the Suffix Array sufficient to locate on-line one pattern occurrence (in general, all its Maximal Exact Matches) via binary search, provided that random access to the text is available. We prove that: (i) the Suffixient Array length $$\varvec{\chi }$$ χ is a strong repetitiveness measure, (ii) unlike most existing repetition-aware indexes such as the $$\varvec{r}$$ r -index, our new index is efficient in the I/O model, and (iii) Suffixient Arrays can be computed in linear time and compressed working space. We show experimentally that, when using well-established compressed random access data structures on repetitive collections, the Suffixient Array $$\varvec{\textrm{sA}}$$ sA is simultaneously (i) faster and orders of magnitude smaller than the Suffix Array and (ii) smaller and one to two orders of magnitude faster than the $$\varvec{r}$$ r -index. With an average pattern matching query time as low as 3.5 ns per character, our new index gets very close to the ultimate lower bound: the RAM throughput of our workstation (1.18 ns per character).

Abstract With the developments in machine learning, there has been a surge in interest and results focused on algorithms utilizing predictions, not least in online algorithms where most new results incorporate the prediction aspect for concrete online problems. While the structural computational hardness of problems with regards to time and space is quite well developed, not much is known about online problems where time and space resources are typically not in focus. Some information-theoretical insights were gained when researchers considered online algorithms with oracle advice, but predictions of uncertain quality is a very different matter. We initiate the development of a complexity theory for online problems with predictions, considering minimization problems and one prediction bit per request. Based on the most generic hard online problem type, string guessing, we define a family of hierarchies of complexity classes (indexed by pairs of error measures) and develop notions of reductions, class membership, hardness, and completeness. Our framework contains all the tools one expects to find when working with complexity, and we illustrate our tools by analyzing problems with different characteristics. In addition, we show that known lower bounds for paging with discard predictions apply directly to all hard problems for each class in the hierarchy based on the canonical pair of error measures. This paging problem is not complete for these classes. Our work also implies corresponding complexity classes for classic online problems without predictions, with the corresponding complete problems.

Abstract Electoral control types are ways of trying to change the outcome of elections by altering aspects of their composition and structure [6]. We say two compatible (i.e., having the same input types) control types that are about the same election system $$\mathcal {E}$$ E form a collapsing pair if for every possible input (which typically consists of a candidate set, a vote set, a focus candidate, and sometimes other parameters related to the nature of the attempted alteration), either both or neither of the attempted attacks can be successfully carried out (see the Preliminaries for a more formal definition) [31]. For each of the seven general (i.e., holding for all election systems) electoral control type collapsing pairs found by Hemaspaandra, Hemaspaandra, and Menton [31] and for each of the additional electoral control type collapsing pairs of Carleton et al. [10] for veto and approval (and many other election systems in light of that paper’s Theorems 3.6 and 3.9), both members of the collapsing pair have the same complexity since as sets they are the same set. However, having the same complexity (as sets) is not enough to guarantee that as search problems they have the same complexity. In this paper, we explore the relationships between the search versions of collapsing pairs. For each of the collapsing pairs of Hemaspaandra, Hemaspaandra, and Menton [31] and Carleton et al. [10], we prove that the pair’s members’ search-version complexities are polynomially related (given access, for cases when the winner problem itself is not in polynomial time, to an oracle for the winner problem). Beyond that, we give efficient reductions that from a solution to one compute a solution to the other. For the concrete systems plurality, veto, and approval, we completely determine which of their (due to our results) polynomially-related collapsing search-problem pairs are polynomial-time computable and which are NP-hard.

Abstract We investigate properties of the bijective Burrows-Wheeler transform (BBWT). We show that for any string w , a bidirectional macro scheme of size $$ O ( r_B{} )$$ O ( r B ) can be induced from the BBWT of w , where $$ r_B{} $$ r B is the number of maximal same-symbol runs in the BBWT. We also show that $$ r_B{} = O ( z \, \log ^{ 2 }\, n ) $$ r B = O ( z log 2 n ) , where n is the length of w and z is the number of Lempel-Ziv 77 factors of w . Then, we show a separation between BBWT and BWT by a family of strings with $$ r_B{} = \Omega ( \log \, n ) $$ r B = Ω ( log n ) but having only $$ r= 2 $$ r = 2 , where $${r}$$ r is the maximal same-symbol runs in the standard Burrows–Wheeler transform (BWT). However, we observe that the smallest $$ r_B{} $$ r B among all cyclic rotations of w is always at most $$ r{} $$ r . While computing an optimal rotation yielding the smallest $$ r_B$$ r B in $$ o ( n ^ {2} ) $$ o ( n 2 ) time remains an open problem, we show how to compute the Lyndon factorizations – a component for computing BBWT – of all cyclic rotations in O ( n ) time using right and left Lyndon trees. We also show that the optimal rotations can be computed in $$ \tilde{O} (nh) $$ O ~ ( n h ) time, where