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.

We provide a compact data structure for representing polyominoes that supports neighborhood and visibility queries. Neighborhood queries concern reporting adjacent cells to a given cell, and visibility queries determine whether a straight line can be drawn within the polyomino that connects two specified cells. For an arbitrary small ϵ > 0, our data structure can encode a polyomino with n cells in (3 + ϵ)n + o(n) bits while supporting all queries in constant time. The space complexity can be improved to 3n + o(n), while supporting neighborhood queries in $\mathcal{O}(1)$ and visibility queries in $\mathcal{O}(t(n))$ for any arbitrary t(n) ∈ ω(1). Previous attempts at enumerating polyominoes have indicated that at least 2.00091n−o(n) bits are required to differentiate between distinct polyominoes, which shows our data structure is compact.In addition, we introduce a succinct data structure tailored for bar graphs, a specific subclass of polyominoes resembling histograms. We show that a bar graph comprising n cells can be encoded using n + o(n) bits, enabling constant-time query processing. Meanwhile, n − 1 bits are necessary to represent any bar graph, proving our data structure is succinct.