setall [datatype=literal] [datatype=name] [field=journal] [datatype=bibtex]
[overwrite, foreach=setall] [fieldsource=$MAPLOOP$, match=01310300,
replace=00EC] [fieldsource=$MAPLOOP$, match=01310301, replace=00ED]
[fieldsource=$MAPLOOP$, match=01310302, replace=00EE] [fieldsource=$MAPLOOP$,
match=01310308, replace=00EF]

# Cell-Probe Lower Bound for Accessible Interval Graphs

Sankardeep Chakraborty
University of Tokyo, Japan<EMAIL_ADDRESS>Christian Engels
National Institute of Informatics, Japan<EMAIL_ADDRESS>This work was
supported by JSPS KAKENHI Grant Number JP18H05291. Seungbum Jo
Chungnam National University, South Korea<EMAIL_ADDRESS>Mingmou Liu
University of Copenhagen, Denmark<EMAIL_ADDRESS>Mingmou is a part of Basic
Algorithms Research Copenhagen (BARC), supported by the VILLUM Foundation
grant 16582. Part of this work was done when the author was a research fellow
at the Nanyang Technological University, supported by the Singapore Ministry
of Education (AcRF) Tier 1 grant RG75/21.

###### Abstract

We spot a hole in the area of succinct data structures for graph classes from
a universe of size at most $n^{n}$. Very often, the input graph is labeled by
the user in an arbitrary and easy-to-use way, and the data structure for the
graph relabels the input graph in some way. For any access, the user needs to
store these labels or compute the new labels in an online manner. This might
require more bits than the information-theoretic minimum of the original graph
class, hence, defeating the purpose of succinctness. Given this, the data
structure designer must allow the user to access the data structure with the
original labels, i.e., relabeling is not allowed. We call such a graph data
structure “accessible”. In this paper, we study the complexity of such
accessible data structures for interval graphs, a graph class with
information-theoretic minimum less than $n\log_{2}n$ bits. More specifically,
our contributions are threefold:

  * •

We formalize the concept of “accessibility” (which was implicitly assumed in
all previous succinct graph data structures), and propose a new presentation,
called “universal interval representation”, for interval graphs.

  * •

Any data structure for interval graphs in universal interval representation,
which supports both adjacency and degree query simultaneously with time cost
$t_{1}$ and $t_{2}$ respectively, must consume at least $\log_{2}(n!)+n/(\log
n)^{O(t_{1}+t_{2})}$ bits of space. This is also the first lower bound for
graph classes with information-theoretic minimum less than $n\log_{2}n$ bits.

  * •

Finally, we provide two efficient succinct data structures for interval graphs
in universal interval representation that support adjacency query and degree
query individually in constant time and space costs
$\log_{2}(n!)+\tilde{O}(\sqrt{n})$ bits and $\log_{2}(n!)+\tilde{O}(n^{2/3})$
bits respectively.

Therefore, two upper bounds together with the lower bound show that the two
elementary queries for interval graphs are incompatible with each other in the
context of succinct data structure. To the best of our knowledge, this is the
first proof of such incompatibility phenomenon.

##  1 Introduction

In the field of compressed data structures design, given a combinatorial
structure $T$ as input, e.g., a graph, a poset, a permutation, etc., a storage
scheme is called optimal if it takes an information-theoretic minimum of
$\log(|T|)$ bits (throughout this paper, $\log$ denotes the logarithm to the
base $2$) to encode any arbitrary member $x\in T$. In general, it is not
difficult to encode any $x\in T$ optimally, but, it is extremely difficult to
navigate and query on $x$ efficiently in this compressed form. The whole point
of compressed data structures is to represent combinatorial objects with as
few as possible bits, not just for the sole purpose of compressing them, but
also to query them efficiently without decompressing. To this end, it is
customary to allow some extra space (called “redundancy” in compressed data
structure parlance) so that queries can be executed on the code word of $x$
efficiently. This gives rise to the notion of succinct data structures.
Formally, a data structure is called succinct if the total space used is
$\log(|T|)+o(\log(|T|))$ bits. Since Jacobson [Jac89] initiated the
investigation of succinct data structures for various classes of graphs 35
years ago, extensive research in this domain has led to such data structures
(refer to [Nav16] for a thorough introduction) for various combinatorial
objects like trees [NS14], arbitrary graphs [FM13], planar maps [ADS08],
finite automaton [Cha+23], functions [MR04], permutations [Mun+12], posets
[MN16], bounded treewidth graphs [FK14], texts [GNP20], sequences [NN14],
etc., among many others and by now this is a mature field of study. Typically,
the ideal query time would be constant (or polylogarithmic in the input size)
for such data structures, thus, these data structures truly offer the best of
both worlds (time- and space-wise) solution for modern storage issues.

We observe that underlying all compressed data structures, there exists a
fundamentally subtle (yet implicit in previous works) assumption which we call
the notion of “accessibility”. It can be defined from the end user’s point of
view in the following sense. Suppose that the user has an unlabeled graph $G$
as input, so huge that the user first wants to construct an encoding $E$ of
$G$ using little space, and then, the user wants to execute queries
efficiently on $E$ to retrieve useful information about $G$. Note that, to
query $G$, the user has to assign some labels to either the vertices or the
edges of $G$ in an arbitrary and easy-to-use way, and the user always wants to
query on the graph with the labels chosen by herself. From now on, we assume
that only vertices are being labeled/relabeled, not the edges, but in general,
one can relabel either or both. The user then hands over $G$ to the data
structure designer, who can either adopt the user’s labeling or relabel the
vertices for any arbitrary reasons. When the designer returns the final data
structure to the user, two scenarios emerge. If the designer used the same
labeling as the user, no additional “vertex mapping translation” data
structure is required, resulting in an “accessible” data structure from the
user’s perspective. However, if the labeling differs, the designer must
provide either a vertex mapping translation data structure to the user so that
the user can correctly identify any vertex in $G$ and can access/query the
data structure meaningfully, or an algorithm for the user to compute the
labeling by herself in an online manner. Note that both the translation data
structure and the algorithm could be considered as a built-in component of our
data structure for graphs. Failure to address these cases leads to an
“inaccessible” data structure for $G$ from the user’s perspective.

To illustrate, take as input a labeled tree. The designer may relabel the tree
so that the relabeled tree becomes some unique representative labeled tree in
its automorphism group. This move is very tempting, as it reduces the minimum
bits to encode the tree from $(n-2)\log n$ to $\approx 1.58n$ [FS09, Eq.(58),
p. 481]. However, it makes the data structure inaccessible since it forces the
user to spend lots of computational resources (e.g., additional space as an
extra translation data structure, or lots of time on accessing the original
tree to find the correct way to access the data structure) on computing the
automorphism before accessing the data structure as it is relabeled. Thus,
from a data structure designer’s perspective, it is certainly not desirable to
construct a data structure that is correct, and efficient yet inaccessible
(thus, somewhat useless) to the end user. In light of the above discussion,
let us now formally define the notion of accessible data structures.

> A data structure is said to be “accessible” to a user if the data structure
> designer uses the labeling chosen by the user for the input. Otherwise, the
> data structure is inaccessible.

Note that the above definition naturally carries over to the previously
defined succinct data structures, hence, resulting in accessible succinct data
structures. While the notion of accessibility is generally a recommended
design practice, it is worth asking: Is it always strictly required? It turns
out that at least in some scenarios, we can relax this notion to some extent.
The cost of transforming an “inaccessible” structure into an “accessible” one,
by including a vertex mapping translation data structure, is at most $O(n\log
n)$ bits (assuming the input is a graph $G$ with $n$ nodes). This cost is
negligible for combinatorial structures with an information-theoretic lower
bound of $\omega(n\log n)$ bits. In such cases, the designer can easily
relabel and provide the permutation to the user at minimal extra cost.
Examples include chordal and split graphs [MW18], posets [MN16], strongly
chordal and chordal bipartite graphs [Spi95].

The notion of accessibility also demonstrates a simple yet absolutely critical
fact that the benchmark of a succinct data structure for one graph class is
not unique as the user may label the graphs in any possible way and the labels
should be considered as a part of the input. More concretely, in the tree
example, the information-theoretic minimum of the input varies from $\approx
1.58n$ bits to $(n-2)\log n$ bits, depending on how the user labels the tree.
Thus, through the lens of “accessibility”, all the space efficiency of
previous data structures should be re-examined.

Concretely, for interval graphs, [Aca+21] (we will provide the formal
definition and other required properties of interval graphs shortly) processes
the input to $n$ intervals in the range of $[1,2n]$ such that there is exactly
one endpoint that lands in each position $i\in[1,2n]$. The space cost of their
data structure is $n\log n+2n$ bits, and the authors show that the
information-theoretic minimum of an unlabeled interval graph is at least
$n\log n-2n\log\log n$. Hence, the authors claim a redundancy of $O(n\log\log
n)$ bits. However, suppose the user labels the graph in the same way as the
authors, then its information-theoretic minimum is
$\log\left(\prod_{i=1}^{n}(2i-1)\right)\approx n\log n-0.44n$. Thus, its
redundancy is in fact $\approx 2.44n$ bits. In conclusion, we want to
emphasize that sticking to the notion of “accessibility” is a good data
structure design principle almost always, and it is the responsibility of the
data structure designer to design different data structures adapting to the
labeling chosen by the user. Furthermore, as can be expected, all the existing
previous succinct data structures are accessible in some sense, although this
fact is always implicit in the literature.

It is through this lens that we study the class of interval graphs in this
paper. In particular, in this work, we study the complexity of compressed data
structures for interval graphs. Roughly speaking, a simple undirected graph
$G$ is called an interval graph if its vertices can be assigned to intervals
on the real line, so that two vertices are adjacent in $G$ if and only if
their assigned intervals intersect. Interval graphs are of immensely
importance in multiple fields. [Haj57], and then [Ben59] independently defined
these graphs, and since then, interval graphs have been studied extensively
for their structural properties (for example, interval graphs are chordal
graphs and perfect graphs) and algorithmic applications. Interval graphs have
appeared in a variety of applications, for example, operations research and
scheduling theory [Bar+01], bioinformatics [Zha+94], temporal reasoning
[GS93], VLSI design [Spi03], and many more. We refer the reader to [Gol04,
Gol85] for a thorough introduction to interval graphs and their myriad of
applications. Being such a fundamentally important and practically motivated
graph class, in this work, we ask: Can we design an efficient data structure
for interval graphs that respects the labeling chosen by the user? What would
be the optimal time/space trade-off for such an interval graph data structure?

###  1.1 Our Set-up

In order to state our main results, let us first set the stage by formally
defining and discussing some fundamental concepts and properties that will be
used throughout this paper. For any two integers $n$ and $m$, we use $[n]$ to
denote $\\{1,\dots,n\\}$, and use $[m,n]$ to denote $\\{m,\dots,n\\}$ where
$m\leq n$. When we consider data structures for graphs, we are concerned with
mainly supporting the adjacency query and degree query. Given a graph
$G=(V,E)$, and for any two vertices $u,v\in V$,
$\operatorname{\mathsf{adj}}(u,v)$ query returns true if $u$ and $v$ share an
edge in $G$, and $\operatorname{\mathsf{deg}}(v)$ query for a vertex $v$
returns the number of neighbors of $v$ in $G$. A graph $G=(V,E)$ is defined as
an _interval graph_ if and only if  (i) for each $v\in V$, there exists a
corresponding interval $I_{v}$ on the real line, and  (ii) for any two
vertices $u,v\in V$, $u$ and $v$ are adjacent if and only if $I_{u}\cap
I_{v}\neq\emptyset$. We call a set of intervals $\\{I_{v}\mid v\in G\\}$ an
_interval representation_ of $G$.  Note that, a single interval graph can have
multiple interval representations. For instance, the complete graph on three
vertices, $K_{3}$, can be represented as $\\{[1,2],[2,3],[1,3]\\}$ and
$\\{[1,1],[1,1],[1,1]\\}$. To uniquely define and access the vertices of $G$
from its interval representation, we introduce the notion of a _universal
interval representation_ as follows.

######  Definition 1.

An interval representation $I$ of an interval graph $G$ with $n$ vertices is a
_universal interval representation_ if every $i\in[n]$ is a leftmost endpoint
of exactly one interval.

Now, from the user’s point of view, using the universal interval
representation, each vertex can, very naturally, be denoted as the leftmost
endpoint of its corresponding interval. This simply implies that vertex $i$
corresponds to the interval $I_{i}=[i,e_{i}]$. This shows that the universal
interval representation has the potential to be considered as a viable
solution for interval graph representation from the accessibility standpoint
if the user agrees to the same methodology for referring to the vertices of
the input interval graph. But, does every interval graph have a universal
representation? Fortunately, we answer this question affirmatively by giving a
constructive proof (the details can be found in the proof of the Proposition
5). Hence, we conclude that the universal interval representation is a good
proxy for studying the complexity of interval graphs, and as a consequence,
throughout this paper, we crucially adopt the convention that our input
interval graphs are always represented by adhering to this protocol.

Since each interval $i$ can have $n-i+1$ different right endpoints, i.e.,
$[i,i],\dots,[i,n]$, there exists up to $n!$ distinct universal interval
representations, which intuitively implies that the information-theoretic
minimum of the universal interval representation is $\log(n!)$ bits.
Furthermore, any interval $I_{i}$ can be decoded using
$\operatorname{\mathsf{adj}}{}$ queries only by finding
$\min_{j>i,\operatorname{\mathsf{adj}}(i,j)=\text{false}}j$. Also, $I_{i}$ can
be decoded using $\operatorname{\mathsf{deg}}{}$ queries only, by decoding
from the leftmost interval (the detailed procedure is described in Section 5).
Therefore, any data structure which supports $\operatorname{\mathsf{adj}}{}$
or $\operatorname{\mathsf{deg}}{}$ queries on interval graphs in universal
interval representation should consume at least $\log(n!)$ ($\approx n\log
n-1.44n$) bits of space. As alluded to earlier, the state-of-the-art
information-theoretic lower bound to encode any interval graph $G$ on $n$
nodes is given by $n\log n-2n\log\log n-O(n)$ bits [Aca+21].111Recently [BJ22]
claim an improved (tight) bound of $\approx n\log n-2.478n+\Theta(\log n)$
bits. As our lower bound does not deviate too much from the information-
theoretic minimum to encode unlabeled interval graphs, we believe that the
notion of universal interval representation is a very natural choice while
studying the complexity of interval graph data structure. We also observe that
comparing with the above implementation of [Aca+21], our universal interval
representation offers two salient benefits,  (i) the implementation becomes
more space-efficient, i.e., the benchmark (the information-theoretic minimum
of the input) becomes $\log(n!)\approx n\log n-1.44n$ instead of $\approx
n\log n-0.44n$ bits, saving $n$ bits of space implicitly, and  (ii) as we will
see in Section 4 and Section 5, it would be easier to analyze the distribution
of interval graphs in universal interval representation for providing lower
and upper bounds, since the left endpoints are always fixed, whereas in
[Aca+21], left endpoints could be arbitrary distinct points from $[2n-1]$.

In conclusion, we believe that the assumption of the universal interval
representation is very natural, practical, and advantageous when applied to
interval graphs, and for this reason, it is also our method of choice in this
work. Now we are ready to state the main results of our paper.

###  1.2 Our Contribution

Since Jacobson’s pioneering work [Jac89] on succinct data structures for
trees, extensive research has led to substantial progress in achieving such
data structures for various other graph classes. In the regime of succinct
space, the time cost of data structures very often is remarkably higher than
in the regime of linear space, however showing such a separation remains a
challenge since [Jac89]. Note that tight lower bounds have been shown only for
a handful of problems such as RANK [PV10], range minimum query [Liu21, LY20],
permutations [Gol09], systematic data structure for boolean matrix-vector
multiplication [CKL18] and sampler [BL13] in the succinct regime. Our research
adds to this growing body of work by providing novel time/space trade-off
lower bounds for succinct data structures designed for interval graphs. More
specifically, we start by showing the following impossibility result, which,
informally speaking, states that any data structure for interval graphs that
assumes that the input interval graph is represented using a universal
interval representation must have a high lower bound if the data structure
aims to support both $\operatorname{\mathsf{adj}}$ and
$\operatorname{\mathsf{deg}}$ query together.

######  Theorem 2.

Any data structure taking $\log(n!)+r$ bits for representing an input interval
graph with $n$ vertices that answers $\operatorname{\mathsf{adj}}$ in $t_{1}$
time, and $\operatorname{\mathsf{deg}}$ in $t_{2}$ satisfies

$r\geq\frac{n}{(\log n)^{O(t_{1}+t_{2})}}$

in the cell-probe model with $w=\Theta(\log n)$ bits word size when the input
interval graph is provided using a universal interval representation.

Surprisingly, there exists a dichotomy between these two queries which we
summarize in the following two theorems. Here we assume the usual model of
computation, i.e., a $\Theta(\log n)$-bit word RAM model while designing the
following succinct data structures.

######  Theorem 3.

There exists a data structure that supports $\operatorname{\mathsf{adj}}$
queries in $O(1)$ time using $\log(n!)+O(\sqrt{n}\log n)$ bits for $n$-vertex
interval graphs represented in universal interval representation.

######  Theorem 4.

There exists a data structure that supports $\operatorname{\mathsf{deg}}$
queries in $O(1)$ time using $\log(n!)+O({n}^{2/3}\log n)$ bits for $n$-vertex
interval graphs represented in universal interval representation.

Notice that for constant time $\operatorname{\mathsf{adj}}$ and
$\operatorname{\mathsf{deg}}$ queries together, our lower bound from Theorem 2
results in $\log(n!)+O(n/\polylog(n))$ bit, thus, from the perspective of
succinct data structure complexity, we capture an interesting phenomenon of
incompatibility between two different queries on the same database: There are
efficient data structures for the two queries individually, but any data
structure which supports two queries simultaneously has a high lower bound. To
the best of our knowledge, this is the first proof of such a phenomenon.
Previously, [Gol09] proved lower bounds for three different problems with
multiple queries. It turns out that two of the problems (text searching &
retrieving, rank/select query on matrix) can be reduced from the rank/select
problem on a boolean string, which has high lower bounds with individual query
by [PV10]. On the other hand, there is no known efficient succinct data
structure (e.g., constant time and $n^{0.9}$ bits of redundancy) for the third
problem (permutation) with an individual query, to our knowledge.

###  1.3 Previous techniques

The state-of-the-art lower bound techniques in cell-probe model are derived
from [Mil+98]. In this seminal work, Miltersen et al. propose two important
techniques, _richness_ and _round elimination_.

The richness technique is refined and improved later on by [PT09, PTW10]. The
technique appears in context of proving lower bound for static data structure
[Sie89, PTW10, Lar12, GL16, Yin16], dynamic data structure [Lar12a, CGL15,
LWY20], streaming [LNN15], and succinct data structure [GM07, BL13, CKL18].
The richness technique is similar to the rectangle refutation technique in the
literature on communication complexity. The richness technique is all about
showing that  (i) a too-good-to-be-true data structure implies the existence
of a large monochromatic (or “almost monochromatic” for randomized data
structures) combinatorial rectangle in the answer table of the data structure
problem;  (ii) large (“almost”) monochromatic rectangles do not exist in the
answer table.  Specifically, we find a large set $Q$ of queries and a large
set $B$ of databases by observing a too-good-to-be-true data structure, and
proving that  (i) for any $q\in Q,b\in B$, the answer to $q$ on $b$ is the
same (or “almost the same” for randomized data structure);  (ii) by extremal
combinatorics, in the answer table of the data structure problem, there do not
exist such $Q$ and $B$.  It is known that the technique works well in proving
lower bound for problems which satisfy that the answers to a few fixed queries
reveal much information about the database.

The round elimination technique is also used in, and refined to adapt to,
various scenarios accordingly, including static data structure with polynomial
space [SV08, CR10, LPY18], static data structure with near-linear space [PT06,
PT07], and succinct data structure [PV10, LY20, Liu21]. The technique works in
the following manner:  (i) suppose there is a data structure with time cost
$t$, then we can modify the data structure to obtain a new data structure that
has a time cost of $t-1$ but consumes more space, and/or works only for a
smaller database;  (ii) we recursively apply this modification and at the end
of the recursion, there is a data structure that solves a non-trivial problem
but does not access any memory cell, so we obtain a contradiction.  In this
work, we adapt the ideas from [PV10, LY20] to prove the lower bound.

[Gol09] develops an independent technique to prove lower bounds for a special
class of problems that support a pair of opposite queries which can “verify”
each other, for example, $\pi(i)=j$ and $\pi^{-1}(j)=i$ assuming the database
is a permutation $\pi$. The central observation is the following. Assume the
time cost is low, then there is a cell $d$ such that the number of opposite
query pairs which access $d$ simultaneously is only $\beta\ll w/\log w$ where
the word size is $w$ bits. Thus, we can compress the data structure by
removing $d$ in the following way:  (i) write down the address of $d$ to
identify $d$;  (ii) enumerate and execute queries to identify the $\beta$
opposite query pairs which access $d$ simultaneously;  (iii) write down the
bijection between the queries with $\beta\log\beta$ bits.  Indeed, for a pair
of opposite queries $\pi(i)=j$ and $\pi^{-1}(j)=i$, if only $\pi(i)$ accesses
$d$, then $\pi^{-1}(j)=i$ can be answered without knowing $d$.

[RR18] propose a different technique to prove lower bound for dynamic non-
adaptive succinct data structures with the sunflower lemma. They proved lower
bounds for a couple of elementary data structure problems, including returning
the median (or the minimum) of a set of numbers, and predecessor search. Their
technique essentially leverages the _non-adaptivity_ of the _dynamic_ data
structures. Non-adaptivity means that the set of cells which are accessed by
the query/update algorithm is independent of the database. Therefore, the
technique is not applicable in our case, as we study _fully-adaptive_ _static_
data structures.

Very recently, [Li+23] proved a tight lower bound for dynamic succinct
dictionaries. They extend a classical idea in proving lower bound for the
dynamic data structures, and develop an ad-hoc analysis for dynamic dictionary
problem. Their technique intrinsically utilizes the update operations of
_dynamic_ data structure, and hence does not apply to our case of _static_
data structure.

##  2 Technical Overview

Our lower bound results presented in Section 4 are established in the _cell-
probe_ model [Yao81]. In the cell-probe model, we have given two algorithms,
$C,Q$ which can have unlimited computational power. $C$ takes a certain
structure, such as a graph, and produces a table of $s$ words with each word
having $w$ bits (the word size). Given any query, we access the table using
the query algorithm $Q$. We are allowed to adaptively access at most $t$ cells
of the table. Meaning, given a query, $Q$ decides the first cell to probe.
Then $Q$ decides using the cell’s content the next cell to probe and so on. At
the end, it accessed $t$ cells and outputs the answer to the query according
to the contents of the $t$ cells. We call the tuple of parameters $(s,w,t)$
the _cell-probe complexity_ of the algorithm. This is the only complexity
metric we will use for our lower bounds. Additionally, we augment the model as
in [PV10] with $P$ extra bits which $Q$ is allowed to access for free. The
bits are called _published bits_. Informally, one may consider the published
bits as the cache of the CPU, so it is (almost) free to access.

###  2.1 The Issue of Applying Pǎtraşcu and Viola’s Technique

We adopt the basic framework from [PV10]. As we discussed previously, the
framework is called round elimination. Without loss of generality, suppose the
information-theoretic lower bound of the database is $n$ bits, the word size
is $w$ bits, and we have a data structure that takes $n+r$ bits of space and
solves any query in $t$ time. Besides the memory, [PV10] further assumes that
there are some _published bits_ , which the query algorithm can access _for
free_. Given a succinct data structure using $n+r$ bits of space and $t$ time,
one may construct a data structure that consumes $n$ bits of space, $r$ bits
of published bits and solves any query in $t$ time. The round elimination in
[PV10] then works in the following manner:  (i) Given a data structure using
$p$ bits of published bits and $t$ time, we can find a set $\mathcal{P}$ of
memory cells such that a fraction of queries, e.g., a constant fraction,
access at least one cell in $\mathcal{P}$.  (ii) Then we copy the contents
together with the addresses of the cells in $\mathcal{P}$ to the published
bits, and modify the original query algorithm so that whenever the original
query algorithm wants to access a cell in $\mathcal{P}$, the query algorithm
can save the memory access with the information we copied to the published
bits.  (iii) Thus, we obtain a data structure which uses $p+|\mathcal{P}|(\log
n+w)$ published bits and answers an average query with $t-\Omega(1)$ times of
memory access.  (iv) We recursively apply this modification and at the end, we
obtain a data structure which does not access memory at all but can solve any
query. Then the final data structure must use at least $n$ published bits.  In
[PV10], $|\mathcal{P}|$ is always in $\Theta(p\log n)$. Hence, at the end of
the recursion, the authors have $r(w+\log n)^{O(t)}$ published bits, and they
can prove $r=n/(\log n)^{O(t)}$ by assuming $w=O(\log n)$.

The issue of applying the original technique in [PV10] to our problem happens
in the very first step. Intuitively, [PV10] can find such $\mathcal{P}$
because the answers to the queries are correlated and the database is encoded
succinctly. Hence, many queries must access the same cells to retrieve the
same information. For the interval graph, the answers to adjacency queries are
almost independent of each other222 One may think that we are dealing with an
array $A$ of integers from $[n]\times[n-1]\dots[2]\times[1]$ which is the
length of eac interval. To answer $\operatorname{\mathsf{adj}}(i,j)$ with
$j\geq i$, we simply retrieve $A_{i}$ and check if $A_{i}\geq j-i+1$. So the
answers to queries are basically independent of each other. In fact, if one
would like to solve adjacency query only, in the cell-probe model we can have
a data structure using $\log(n!)+1$ bits of space and constant time by
generalizing the technique in [DPT10]. See formal proof in Appendix A. . A
similar thing holds for the degrees of the vertices.

##### Observations:

  1. (1)

Answers to adjacency queries can verify the length of each interval.

  2. (2)

For each interval with left endpoint $i$, if one can know
$\operatorname{\mathsf{deg}}(i)$ together with the right endpoint of the
interval (denoted by $e_{i}$), one can know the number of right endpoints
which land before position $i$ (denoted by $R(i)$) as
$e_{i}=\operatorname{\mathsf{deg}}(i)+R(i)$.

  3. (3)

[PV10] proves a lower bound for the RANK problem where the database is a
Boolean string $\\{0,1\\}^{n}$ and the answer to query $i$ is the number of
ones before position $i$.

Hence, our problem is somehow similar to the one in [PV10]. To leverage this
observation, we will exploit that “answers to adjacency queries can verify the
length of each interval”. At first glance, this might be a problem as querying
$\operatorname{\mathsf{adj}}(i,j)$ for $j\geq i$ only returns one bit to tell
us if the length of interval $i$ is at least $j-i$. There is no fixed query to
reveal the length. Therefore, we focus on a tuple of _hard_ queries
$\operatorname{\mathsf{deg}}(i)$, $\operatorname{\mathsf{adj}}(i,e_{i})$, and
$\operatorname{\mathsf{adj}}(i,e_{i}+1)$. Notice that $e_{i}$ is hidden from
us and is a random variable which depends on the database. The situation
reminds us of [LY20] which fixes a similar issue about proving lower bound for
some hard queries which depend on the database.

###  2.2 Towards applying [LY20]’s technique

To find the set $\mathcal{P}$ of cells such that many hard queries access at
least one cell in $\mathcal{P}$, we should find a set $Q$ of queries such that
the answers to $Q$ are highly correlated with the hard queries and the
_answers_ to the hard queries. Then we let $\mathcal{P}$ be the set of cells
which are accessed by $Q$. Previous works [PV10, LY20, Liu21] apply a proof by
contradiction to show that many hard queries access at least one cell in
$\mathcal{P}$. [PV10] shows that if $\mathcal{P}$ is barely accessed by hard
queries, assuming the space cost is $n+p$ bits. Then we can apply the
following encoding:

  1. 1.

Write down the content of $\mathcal{P}$, which is the cells accessed by $Q$,
in the order of being accessed by the query algorithm.

  2. 2.

The amount of information shared by the answers to hard queries and the
answers to $Q$ is $\omega(p)$ bits. Therefore, we write down the content of
the cells accessed by the hard queries, given the content of $\mathcal{P}$,
with the optimal encoding to save $\omega(p)$ bits of space.

  3. 3.

Write down the contents of the remaining cells in the lexicographical order of
their addresses.

This allows us to encode the data structure with $n-\omega(p)$ bits which is
impossible.

When both $Q$ and the hard queries are fixed and independent of the database,
we only have to write down the content of $\mathcal{P}$ and the cells accessed
by hard queries in the order in which they are accessed by the query
algorithm, as the address of the next cell is automatically revealed by
simulating the query algorithm on previous cells. When $Q$ or the hard queries
are determined by the database, the simple argument in [PV10] does not work
anymore because we cannot find the set of cells we are supposed to compress to
save space. In fact, the information which is shared by the two sets of cells,
i.e., the information we are supposed to compress, may precisely be “what is
the set of cells”, so we cannot simply write the addresses down.

[LY20, Liu21] overcome this. They note that if we can encode $Q$ at low cost,
then we can find an $\ell\in[t]$ such that the contents of the cells, which
are accessed by $Q$ in $\ell$-th round of memory access, share a lot of
information with the answers to the hard queries. The idea works because the
addresses of the $\ell$-th cells are revealed by the contents of the previous
$\ell-1$ cells. They introduce a new encoding argument to use this:

  1. 1.

Write down a few bits to encode $Q$ together with $\ell$.

  2. 2.

Write down the contents of the cells which are accessed by $Q$ in the first
$\ell-1$ rounds of memory access in the order in which they are accessed by
the query algorithm.

  3. 3.

Write down the contents of the remaining cells, except the cells which are
accessed by $Q$ in the $\ell$-th round of memory access, in the
lexicographical order of their addresses. Note that most of the cells which
are accessed by the hard queries are written down in this step because they
barely intersect with the $\ell$-th cells by the assumption.

  4. 4.

Enumerate every query and try to answer them by simulating the query algorithm
on the cells we have written down. We have enumerated many hard queries and
revealed answers to them because of the disjointedness given by the
assumption, and we know a lot of information about the contents of the missing
cells because of the aforesaid correlation. Then we write down the contents of
the missing cells with the known information and the optimal encoding to save
$\omega(p)$ bits of space.

#####  $Q$ depends on the dataset.

An immediate issue arises when one tries to apply [LY20, Liu21]’s technique on
the hard query tuples
$(\operatorname{\mathsf{deg}}(i),\operatorname{\mathsf{adj}}(i,e_{i}),\operatorname{\mathsf{adj}}(i,e_{i}+1))$.
Recall that we would like to utilize $R(i)$, the number of right endpoints
that land before position $i$. It turns out that the only query, which is
correlated with $R(i)$’s and which we could find, is another tuple of hard
queries. In other words, $Q$ cannot be encoded at low cost in our case. We
observe that $e_{i}$ can be computed by a binary search using
$\operatorname{\mathsf{adj}}(i,\cdot)$ queries. Hence, we let all the cells
accessed by the binary search procedure be the published bits. One may think
that $Q$ is fixed in some sense, but we modify the query algorithm so that $Q$
probes a lot of cells, so that the answers to $Q$ reveal a lot of information
about the hard queries and their answers. Specifically, in the original proof,
$Q$ consists of $\approx p$ queries, each access $t\leq\log n$ cells
adaptively according to the query algorithm, forming $\approx p$ sequences of
cells of length $t\leq\log n$. In our case, $Q$ still consists of $\approx p$
queries but each access $t\log n\leq\log^{2}n$ cells adaptively. This forms
$\approx p$ sequences of cells of length $t\log n\leq\log^{2}n$ and each
sequence of cells is obtained by adaptively combining the original query
algorithm. The approach is a natural extension of the idea of [LY20, Liu21].

##### Mutual information.

Another technical issue is to lower bound the mutual information between the
answers to $Q$ and the answers to hard queries. The mutual information is a
significant ingredient in Step 4 of the aforesaid new encoding argument. The
distribution here is very different from the previous ones and is
sophisticated, hence, analyzing it is a highly non-trivial job. Indeed, in the
problem studied by [PV10], in each position the number of ones has a Bernoulli
distribution with parameter $1/2$ and the numbers of ones in different
positions are mutually independent of each other. Therefore, the number of
ones in any range has binomial distribution which we can easily analyze with
standard techniques. In our case, the “number of right endpoints in position
$i$” has Poisson binomial distribution with parameters
$p_{1}=1/n,p_{2}=1/(n-1),\dots,p_{i}=1/(n-i+1)$ and the numbers in different
positions are correlated with each other.

We still adopt the idea from [PV10] that breaking the universe of queries into
$p$ consecutive blocks of length $n/p$, denoted by $q_{1},\dots,q_{p}$, and
letting $Q$ together with answers to $Q$ reveal the number of right endpoints
in each block. Assuming only a few hard queries access some cell accessed by
$Q$, then by an average argument, there is a set of hard queries which break
the universe into $p$ consecutive blocks, denoted by
$q^{\prime}_{1},\dots,q^{\prime}_{p}$, of length $n/p$, with the first and the
last blocks being exceptions we ignore for the overview. Additionally, the
intersection of $q_{i+1}$ and $q^{\prime}_{i}$ is of length $(1-o(1))n/p$ for
any $i$. These are now two different partitions of the same universe $[n]$. In
order to measure the information contained in the numbers of right endpoints
in the blocks, we set a threshold for each of the $2p$ blocks of length $n/p$
in the two partitions and check if the number of right endpoints is larger
than the threshold for each aforesaid block. We use random variable indicators
$T_{i}$’s and $T^{\prime}_{i}$’s to denote these. The proof for lower bounding
mutual information then consists of two components: Showing that the entropy
of $\\{T_{i}\\}$ is $\Omega(p)$, and showing that the entropy of
$\\{T_{i}\\}_{i\in[p]}$ is $o(p)$ given $\\{T^{\prime}_{i}\\}_{i\in[p]}$.

We achieve the first component by the following argument. Let $Y_{i}$ denote
the number of right endpoints before block $q_{i}$. To lower bound
$H(T_{1},\dots,T_{p})$, it suffices to lower bound $H(T_{i}\mid Y_{i})$ by the
chain rule and observing that $H(T_{i}|T_{1},\dots,T_{i-1})\geq
H(T_{i}|Y_{1},\dots,Y_{i})=H(T_{i}|Y_{i})$. Let $Y^{\prime}_{i}$ denote the
number of right endpoints which are in block $q_{i}$ but their corresponding
left endpoints are not. Let $Z_{i}$ denote the number of intervals which are
fully contained in block $q_{i}$. Then $T_{i}$ indicates if
$Y^{\prime}_{i}+Z_{i}$ is large enough. We further observe that
$Y^{\prime}_{i}$ has a binomial distribution as long as $Y_{i}$ is fixed, and
$Y_{i}$ concentrates around its expectation with high probability. Thus, we
are able to prove that $Y^{\prime}_{i}$ acts like a binomial random variable
and, hence, deviates from some fixed value in an approximately symmetric way,
and that $|Z_{i}-\mathbb{E}{[Z_{i}]}|$ is dominated by the former deviation
with high probability.

To upper bound $H(T_{1},\dots|T^{\prime}_{1},\dots)$, it suffices to upper
bound $H(T_{i+1}|T^{\prime}_{i})$ by the chain rule and the sub-additivity of
entropy. Note that the range $q_{i+1}\cup q^{\prime}_{i}$ consists of a common
part of length $(1-o(1))n/p$ and two distinct parts of length $o(n/p)$. We are
going to prove that the number of right endpoints in the common part acts like
a binomial random variable with a similar proof to the one in the previous
paragraph. So it deviates from its expectation like a binomial distribution.
For the “numbers of the right endpoints” in the distinct parts, since they are
sums of a binomial random variable and a Poisson binomial random variable
given fixed $Y_{i}$, and since distinct parts are of length $o(n/p)$, we are
able to prove that their variances are small. This allows us to apply
Chebyshev’s inequality to upper-bound the deviations.

###  2.3 Upper Bound Techniques

[Aca+21] recently provided an $(n\log n+2n)$-bit representation of an interval
graph $G$ as follows: They first represent $G$ as $n$ intervals of $2n$
distinct endpoints from $[2n]$. Here, each vertex is denoted as $i$ if and
only if the corresponding interval’s left endpoint is at the $i$-th leftmost
position among all $n$ left endpoints. The encoding consists of two
components:  (i) A binary sequence of size $2n$ that indicates whether a given
point $i$ is the leftmost or rightmost endpoint, and  (ii) an integer sequence
of size $n$ that stores the right endpoints according to the order of their
leftmost points.  Using this representation, one can decode the interval
$I_{i}$ corresponding to vertex $i$. In addition to this, their data structure
provides efficient support for both $\operatorname{\mathsf{adj}}{}$ and
$\operatorname{\mathsf{deg}}{}$ queries in $O(1)$ time by combining the
representation with an $o(n)$-bit auxiliary structures for supporting RANK and
SELECT queries in $O(1)$ time [CM96].

In order to improve this result by $\Omega(n)$ bits while supporting
individual queries in $O(1)$ time, we introduce mainly two ideas:  (i) As
alluded previously, we assume the input graph is in the universal interval
representation, so that the entropy of the input database is $\log(n!)\approx
n\log n-1.44n$ bits instead of $\approx n\log n-0.44n$ bits, and  (ii) we use
a fairly standard trick of dividing the input into smaller-sized sub-blocks to
encode them even more space-efficiently without compromising the query time.
The previous data structure works with the global information about the input
directly without exploiting the interaction between the intervals in a more
granular fashion. We provide a high-level overview below whereas all the
details can be found in Section 5.

##### Adjacency query:

Recall that we assume that the graph is represented in universal interval
representation. To answer adjacency query $\operatorname{\mathsf{adj}}(i,j)$
with $i\leq j$, it suffices to retrieve the length of interval $i$ and then
compare the right endpoint with $j$. Hence, it suffices to encode an array
$A\in[n]\times[n-1]\cdots[2]\times[1]$ which reminds us of the technique in
[DPT10]. This technique works for encoding an array from $[\Sigma]^{n}$ with
$n\log\Sigma+O(\log n)$ bits. In fact, in the cell-probe model, i.e., assuming
the CPU has unlimited computational power, the array $A$ can be encoded in
$\log(n!)+1$ bits by generalizing [DPT10]. We exhibit this in Appendix A. To
apply the technique from [DPT10] in the word RAM model, we divide the array
into $\sqrt{n}$ blocks of equal length. To encode a block, which is a sub-
array from $[n-k\sqrt{n}]\times\cdots\times[n-(k+1)\sqrt{n}+1]$ for some
$k\in\\{0,\dots,\sqrt{n}-1\\}$, we simply apply [DPT10]’s encoding scheme with
a universe of size $[n-k\sqrt{n}]^{\sqrt{n}}$.

##### Degree query:

$i$-th interval(i)(ii)(iii)(iv) Figure 1: Type of Intervals for Degree Query

To answer degree query, we again apply the trick of block partitioning but
with the block size of $\sqrt[3]{n}$. For an interval $i$ in the $k$-th block,
there are four different intervals which may intersect with interval $i$ (See
Fig. 1).  (i) The left endpoint lands before the $k$-th block, and the right
endpoint lands after the $k$-th block;  (ii) the left endpoint lands in the
interval $i$;  (iii) the left endpoint lands before the $k$-th block, and the
right endpoint lands in the $k$-th block;  (iv) the left endpoint lands in the
$k$-th block but before the position $i$.  For each interval in the same
block, the number of intervals of kind (i) is the same, so we can store them
with an array using $O({n}^{2/3}\log n)$ bits. Assuming there are $b_{k}$
right endpoints land in block $k$, the numbers of the other three kinds of
intervals are at most  (ii) $n-i$,  (iii) $b_{k}$,  (iv) $i-(k-1)\sqrt[3]{n}$,
respectively. Therefore, it suffices to encode an array with universe
$[n+b_{1}]^{\sqrt[3]{n}}\times\cdots\times[n-(k-1)\sqrt[3]{n}+b_{k}]^{\sqrt[3]{n}}\times\cdots$
with constraint $\sum_{k}b_{k}=n$. Finally, we apply [DPT10] and calculate the
space cost carefully to complete the proof.

##  3 Preliminaries

In this section, we state a couple of basic preliminaries which we need for
the upper and lower bounds. First, we want to show that it is possible to
transform any interval graph into our universal interval representation.

######  Proposition 5.

Any interval graph $G$ of $n$ vertices has a universal interval
representation.

###### Proof.

According to [Han82], $G$ has a well-known interval representation $I$, where
all the endpoints in $I$ are distinct integers from the set $[2n]$. We can
then generate a universal interval representation of $G$ using the following
procedure:

Starting from the point $1$, we check each points in $[2n]$ from left to
right. If $i$ is the left endpoint of the interval in $I$, we check the next
point. Otherwise, let $j<i$ be the rightmost left endpoint to the left of $i$.
Then we modify $I$ in two ways. First, we modify all intervals in the set
$\\{[p,q]\in I\mid p<i,q\geq i\\}$ to $[p,q-(j-i)]$. Second, we modify all
intervals in the set $\\{[p,q]\in I\mid\ p>i\text{~{}and~{}}q>i\\}$ to
$[p-(j-i),q-(j-i)]$. We repeat this modification process until $I$ has an
interval with a left endpoint of $i$ or there is no endpoint to the right of
$i-1$. Since this modification process does not alter the intersection
relations among the intervals in $I$, and preserves the uniqueness of the left
endpoints of the intervals in $I$, we can obtain a universal interval
representation of $G$ after completing the procedure. ∎

As mentioned previously, we adopt the convention that any interval graph will
be presented in its universal interval representation throughout the remainder
of this paper. Additionally, sampling an interval graph from its universal
interval representation is straightforward, and we make use of the following
two essential properties crucially in our lower-bound proofs.

######  Proposition 6.

Let the universal interval representation be drawn uniformly at random. Then
for each $i\in[n]$,  (i) $e_{i}$is uniformly distributed over the range
$[i,n]$, and  (ii) $e_{1},e_{2},\dots,e_{n}$are mutually independent.

##### Terminologies for Cell-probe Lower Bounds

Recall that any query can be answered in $t$ adaptive memory accesses by
assumption, and that the word size is $w$ bits. We adopt the notation from
[PV10, LY20] and define the following for a query $q$ or a query set $Q$ on
the input data:

  * •

For a query $q$ and an integer $\ell\in[t]$, the address of the cell probed by
$q$ in $\ell$-th memory access is denoted by $\mathrm{Probe}{}_{\ell}(q)$. We
also define $\mathrm{Probe}{}_{\ell}(Q)\triangleq\cup_{q\in
Q}\mathrm{Probe}{}_{\ell}(q)$,
$\mathrm{Probe}{}_{\leq\ell}(q)\triangleq\cup_{i\leq\ell}\mathrm{Probe}{}_{i}(q)$,
$\mathrm{Probe}{}_{<\ell}(q)\triangleq\cup_{i<\ell}\mathrm{Probe}{}_{i}(q)$
and $\mathrm{Probe}{}_{\leq\ell}(Q)\triangleq\cup_{q\in
Q}\mathrm{Probe}{}_{\leq\ell}(q)$,
$\mathrm{Probe}{}_{<\ell}(Q)\triangleq\cup_{i<\ell}\mathrm{Probe}{}_{i}(Q)$.

  * •

The set of cells probed when answering a query $q$ (resp. all queries in $Q$)
is denoted by
$\mathrm{Probe}{}(q)\triangleq\cup_{i\in[t]}\mathrm{Probe}{}_{i}(q)$ (resp.
$\mathrm{Probe}{}(Q)\triangleq\cup_{q\in Q}\mathrm{Probe}{}(q)$).

  * •

A binary string encoding the content of the $\ell$-th probed cell when
answering the query $q$ is denoted by
$\mathrm{Foot}{}_{\ell}(q)\in\\{0,1\\}^{w}$. We also define
$\mathrm{Foot}{}_{\ell}(Q)\triangleq\mathrm{Foot}{}_{\ell}(q_{1})\cdot\mathrm{Foot}{}_{\ell}(q_{2})\dotsb\in(\\{0,1\\}^{w})^{|Q|}$
as the concatenation of all $\mathrm{Foot}{}_{\ell}(q)$ for $q\in Q$ in
lexicographical order $q_{1}<q_{2}<\dotsb$.

  * •

The binary string obtained by concatenating the contents of the probed cells
when answering a query $q$ is called its _footprint_ , denoted by
$\mathrm{Foot}{}(q)\triangleq\mathrm{Foot}{}_{1}(q)\cdot\mathrm{Foot}{}_{2}(q)\dotsb\in(\\{0,1\\}^{w})^{t}$.
We also define
$\mathrm{Foot}{}(Q)\triangleq\mathrm{Foot}{}(q_{1})\cdot\mathrm{Foot}{}(q_{2})\dotsb$
as the concatenation of the footprints of all queries in $Q$ in
lexicographical order $q_{1}<q_{2}<\dotsb$.

  * •

$\mathrm{Foot}{}_{<\ell}(q)\triangleq\mathrm{Foot}{}_{1}(q)\cdot\mathrm{Foot}{}_{2}(q)\cdots\mathrm{Foot}{}_{\ell-1}(q)$
is obtained by concatenating the contents of the first probed cells up to the
$(\ell-1)$-th probe. We also define
$\mathrm{Foot}{}_{<\ell}(Q)\triangleq\mathrm{Foot}{}_{<\ell}(q_{1})\cdot\mathrm{Foot}{}_{<\ell}(q_{2})\dotsb$
as the concatenation of all $\mathrm{Foot}{}_{<\ell}$ for all queries in $Q$
in lexicographical order $q_{1}<q_{2}<\dotsb$.

Note that the $\ell$-th probe of any query algorithm can be determined based
on the first $\ell-1$ probes, as the algorithm can only act based on the known
information. In other words, $\mathrm{Probe}{}_{\ell}(q)$ (resp.
$\mathrm{Probe}{}_{\ell}(Q)$) is known given $\mathrm{Foot}{}_{<\ell}(q)$
(resp. $\mathrm{Foot}{}_{<\ell}(Q)$) for any $\ell$ and $q$ (resp. $Q$). This
implies that one can decode the address of the next cell to be probed using
$\mathrm{Foot}{}_{<\ell}(q)$. Therefore, one can answer the query $q$ using
its footprint $\mathrm{Foot}{}(q)$ as follows: At each step, one checks
whether the cell to be probed has already been published or not. If the cell
has been published (hence, one knows the contents of the cell), one can simply
read its contents without incurring any additional cost and move on to the
next step. Otherwise, one needs to read the next $w$ bits of
$\mathrm{Foot}{}(q)$, which contains the contents of the cell to be published
as well as the address of the next cell to read. As a result, the length of
$\mathrm{Foot}{}(q)$ is exactly $w\cdot\lvert\mathrm{Probe}{}(q)\rvert$ bits.

##### Useful lemmas

Proving our upper bounds uses the following well-known lemma that gives us a
succinct encoding for integer sequence of arbitrary alphabet size without
losing the constant time accessibility of the data structure.

######  Lemma 7 ([DPT10]).

For any integer sequence of size $n$ with values from some alphabet
$\Sigma=\\{0,1,\dots,|\Sigma|\\}$ can be stored using $\left\lceil
n\log\lvert\Sigma\rvert\right\rceil+O(\log n)$ bits while supporting
$O(1)$-time access to any position of the sequence in the word RAM model.

Finally, we state some well-known probability theory propositions for
completeness.

######  Proposition 8 (Chebyshev’s inequality).

Let $X$ be a random variable with finite mean $\mathbb{E}{[}X]$ and variance
$\sigma^{2}$. Then for any $k>0$,

$\Pr[X-\mathbb{E}{[}X]\leq k\sigma]\leq 1/k^{2}.$

######  Proposition 9 (Chernoff bound).

Let $X=\sum_{i=1}^{n}X_{i}$ be a random variable where each $X_{i}$ has a
Bernoulli distribution with parameter $p_{i}$, and let
$\mathbb{E}{[}X]=\sum_{i=1}^{n}p_{i}$. Then for any constant $\delta\geq 0$,

$\Pr\left[\lvert X-\mathbb{E}{[}X]\rvert\leq\delta\mathbb{E}{[}X]\right]\geq
1-2e^{-\delta^{2}\mathbb{E}{[}X]/3}.$

If we choose $\delta$ as $10/\sqrt{\mathbb{E}{[}X]}$ the right term of the
inequality becomes a constant very close to $1$, i.e., $>0.999$.

######  Proposition 10 (Berry-Essen Theorem for Binomial Distribution).

Let $X\sim B(n,p)$ be a binomial distributed random variable. Then
$Y_{n}=\frac{X-np}{\sqrt{np(1-p)}}$ converges to $N(0,1)$, i.e., the standard
normal distribution. Also, for all $x$ and $n$, the difference between
$\Pr[Y_{n}\leq x]$ and $\Phi(x)$ is at most $O(1/\sqrt{n})$ where $\Phi$
denotes the cumulative distribution functions of $N(0,1)$.

##  4 The Lower Bound

This section proves the lower bound trade-off between the redundancy and query
time for any accessible data structure that supports both
$\operatorname{\mathsf{adj}}$ and $\operatorname{\mathsf{deg}}$ queries on the
interval graph $G$ with $n$ vertices.

See 2

In the above theorem, $r$ represents the redundancy of the data structure
since the optimal size for storing all possible inputs is $\log(n!)$ bits.

In order to prove the lower bound, we begin by defining the tuple of hard
queries $\operatorname{\mathsf{query}}(i)$ for $i\in[n]$, which consists of
three queries:
$\operatorname{\mathsf{deg}}(i),\operatorname{\mathsf{adj}}(i,e_{i}),\operatorname{\mathsf{adj}}(i,e_{i}+1)$.
Note that the answer to $\operatorname{\mathsf{query}}(i)$ is
$(\operatorname{\mathsf{deg}}(i),0,1)$, and recall that $e_{i}$ is the right
endpoint of interval $i$.

To prove Theorem 2, we will revisit our main idea. Our proof is built on the
round elimination strategy outlined in [PV10]. During each round, we divide
the vertices of $G$ into $k$ blocks, each consisting of $n/k$ vertices. Let
$Q_{\Delta}\triangleq\\{\operatorname{\mathsf{query}}(\Delta+1),\operatorname{\mathsf{query}}(n/k+\Delta+1),\operatorname{\mathsf{query}}(2n/k+\Delta+1),\dots,\\}$
be a set of $k$ queries for $\Delta\in[0,n/k-2]$, let
$Q^{\prime}_{\Delta}\triangleq\\{\Delta+1,n/k+\Delta+1,\dots,\\}$. Assuming
the existence of a data structure that can answer
$\operatorname{\mathsf{deg}}$ and $\operatorname{\mathsf{adj}}$ queries in
$t_{1}$ and $t_{2}$ time, respectively, we can utilize this structure to
reveal $e_{i}$ and $\operatorname{\mathsf{deg}}(i)$ in $t_{1}+t_{2}\log n$
time by executing $\operatorname{\mathsf{deg}}(i)$ and binary search to locate
$e_{i}$ with $\operatorname{\mathsf{adj}}$ queries. Thus, for any $i\in[n]$,
we define $\mathrm{Bin}(i)$ which is the set of cells that are accessed by the
aforesaid procedure to reveal $e_{i},\operatorname{\mathsf{deg}}(i)$. We
define $\mathrm{Bin}(Q),\mathrm{Bin}_{\ell}(Q)$, $\mathrm{Bin}_{\leq\ell}(Q)$,
$\mathrm{Bin}_{<\ell}(Q)$, $\mathrm{Foot}(\mathrm{Bin}(Q))$,
$\mathrm{Foot}_{\ell}(\mathrm{Bin}(Q))$,
$\mathrm{Foot}_{<\ell}(\mathrm{Bin}(Q))$ in the same way with the defining of
$\mathrm{Probe}{}(Q)$, $\mathrm{Probe}{}_{\ell}(Q)$,
$\mathrm{Probe}{}_{\leq\ell}(Q)$, $\mathrm{Probe}{}_{<\ell}(Q)$,
$\mathrm{Foot}(Q)$, $\mathrm{Foot}_{\ell}(Q)$, $\mathrm{Foot}_{<\ell}(Q)$.

At the beginning, suppose we have a data structure for answering
$\operatorname{\mathsf{deg}}$ and $\operatorname{\mathsf{adj}}$ using the
optimal $\log(n!)$ bits with $P=o(\log(n!))$ published bits. Then we publish
all the cells in $\mathrm{Bin}(Q^{\prime}_{0})$. After publishing the cells in
$\mathrm{Bin}(Q^{\prime}_{0})$, we use the following lemma which shows that
publishing the cells in $\mathrm{Bin}(Q^{\prime}_{0})$ decreases the average
cell-probe complexity for answering $\operatorname{\mathsf{query}}(i)$ for all
$i\in[n]$ by some constant $c$. This implies that the total average cell-probe
complexity of at least one of
$\operatorname{\mathsf{deg}}(i),\operatorname{\mathsf{adj}}(i,e_{i}),\operatorname{\mathsf{adj}}(i,e_{i}+1)$
for all vertices $i$ in $G$ is also reduced by $c/3$. The proof of the lemma
can be found in Section 4.1.

######  Lemma 11 (Large Overlap).

Let $G$ be an interval graph chosen uniformly at random from all possible
universal interval representations. Let $k\geq\gamma\log^{2}n$ for some
constant $\gamma>0$, which is at most $n/\polylog(n)$. Then for any
$(\log(n!)+P)$-bit (accessible) data structure on $G$ with $P=o(\log n!)$
published bits,

$\Pr_{j\in[n]}[\mathrm{Bin}(Q^{\prime}_{0})\cap\mathrm{Probe}{}(\operatorname{\mathsf{query}}(j))\neq\emptyset]=\Omega(1).$

We adopt an iterative approach whereby we publish the cells in
$\mathrm{Bin}(Q^{\prime}_{0})$ one after the other. It is important to note
that before publishing a total of $\log(n!)$ bits, the average cell-probe
complexity cannot possibly be below zero. Based on this observation, we are
able to derive the desired lower bound. We give a complete proof of Theorem 2
assuming that Lemma 11 is true.

###### Proof of Theorem 2.

The proof of our theorem relies on a similar argument to that presented in
[PV10]. Specifically, we iterate over a sequence of rounds, with each round
publishing a certain number of bits. We denote by $P_{i}$ the total number of
bits published up to and including the $i$-th round.

Initially, we have $P_{0}=r$ published bits, and for each round
$i\in\\{0,1,\dots\\}$, we set $k_{i}=\gamma P_{i}\cdot\log^{2}n$ for some
constant $\gamma>0$, and publish the cells in $\mathrm{Bin}(Q^{\prime}_{0})$
with respect to the blocks of size $n/k_{i}$. We then have $P_{i+1}\leq
P_{i}+k_{i}w(t_{1}+t_{2}\log n)=O(P_{i}\log^{5}n)$ bits. Here, we assume that
$t_{1}+t_{2}\log n$ is at most $\log^{2}n/\log\log n$ since the theorem
statement holds trivially if $t_{1}+t_{2}$ is greater than $\log n/\log\log
n$.

According to Lemma 11, after each round of bit publishing, the total cell-
probe complexity required to answer one $\operatorname{\mathsf{deg}}$ and two
$\operatorname{\mathsf{adj}}$ queries decreases by $\Omega(1)$. Since the
total redundancy of the published bits cannot exceed $\log(n!)$ bits and
average cell-probe complexity cannot be less than zero, we have
$P_{t_{1}+t_{2}}=r(\log n)^{O(t_{1}+t_{2})}\leq\log(n!)=n\log n-\Theta(n)$.
This inequality completes the proof of the theorem. ∎

###  4.1 Proving the Large Overlap

In this section, we prove Lemma 11. The proof is based on the encoding
argument used in [PV10, LY20]. Before giving a complete proof, we first
describe the overall idea.

To begin the proof by contradiction, assume that
$\Pr_{j\in[n]}[\mathrm{Bin}(Q^{\prime}_{0})\cap\mathrm{Probe}{}(\operatorname{\mathsf{query}}(j))\neq\emptyset]\leq\varepsilon^{4}$
for a sufficiently small $0<\varepsilon<1$. Using an average argument, we can
find a $\Delta$ such that $\Pr_{q\in
Q_{\Delta}}[\mathrm{Bin}(Q^{\prime}_{0})\cap\mathrm{Probe}{}(q)\neq\emptyset]\leq\varepsilon$.
Now let $\operatorname{\mathsf{ans}}(\operatorname{\mathsf{query}}(i))$ denote
the number of right endpoints before the position $i$. We will use the
notation of $q_{i}$ and $q^{\prime}_{i}$ consistently to denote queries in
$Q_{0}$ and $Q_{\Delta}$ respectively. We also define
$\operatorname{\mathsf{ans}}(Q_{0})$ and
$\operatorname{\mathsf{ans}}(Q_{\Delta})$ as
$\\{\operatorname{\mathsf{ans}}(q_{i})\mid q_{i}\in Q_{0}\\}$ and
$\\{\operatorname{\mathsf{ans}}(q^{\prime}_{i})\mid q^{\prime}_{i}\in
Q_{\Delta}\\}$, respectively.

Since the input graph $G$ is chosen uniformly at random, both
$\operatorname{\mathsf{ans}}(q)$ and $\operatorname{\mathsf{ans}}(Q_{p})$ are
random variables. To handle them easily, we introduce an indicator random
variable $T(i)$ which we define as
$T(i)\triangleq\mathbf{1}_{\operatorname{\mathsf{ans}}(\operatorname{\mathsf{query}}(i+n/k))-\operatorname{\mathsf{ans}}(\operatorname{\mathsf{query}}(i))\geq
t_{i}}$ for some threshold $t_{i}>0$, which we decide later. Also, we define a
vector random variable $T(Q_{p})$ as $(T(p+1),T(n/k+p+1),\dots)$. Notice that
$T(Q_{p})$ can be computed from $\operatorname{\mathsf{ans}}(Q_{p})$. We
introduce the following lemma that shows that the two vector random variables
$T(Q_{0})$ and $T(Q_{\Delta})$ are highly correlated.

######  Lemma 12 (Mutual Information).

For any $i\in[0.1k,0.9k]$ and $k\in\omega(1)$, suppose
$Q_{0}=\\{q_{1},q_{2},\dots,q_{k}\\}$ and
$Q_{\Delta}=\\{q^{\prime}_{1},q^{\prime}_{2},\dots,q^{\prime}_{k}\\}$, where
$q_{i}$ and $q^{\prime}_{i}$ are $\operatorname{\mathsf{query}}(in/k+1)$ and
$\operatorname{\mathsf{query}}(in/k+\Delta+1)$, respectively. Then, for any
$\Delta\in\\{(1-\varepsilon^{3})n/k,\dots,n/k-2\\}$, the following holds:

  1. (i)

$H(T(q_{i})\mid T(q_{1}),T(q_{2}),\dots,T(q_{i-1}))=\Omega(1)$, but

  2. (ii)

$H(T(q_{i+1})\mid T(q^{\prime}_{i}))=O(\varepsilon)$.

The proof of Lemma 12 can be found in Section 4.2 and is split into Sections
4.2.1 and 4.2.2.

For any $\ell\in[t_{1}+t_{2}\log n]$, let
$\mathrm{Foot}_{<\ell}(\mathrm{Bin}(Q^{\prime}_{0}))$ denote the contents of
the first $\ell-1$ probed cells. Let
$\mathrm{Foot}_{\ell}(\mathrm{Bin}(Q^{\prime}_{0}))$ denote the contents of
just the $\ell$-th probed cell in $\mathrm{Bin}(Q^{\prime}_{0})$. We begin by
encoding the initial $P$ published bits, $\Delta$, and $\ell$ which is
uniformly chosen at random. Next, we write down all the contents of the cells
in the database other than
$\mathrm{Foot}_{\ell}(\mathrm{Bin}(Q^{\prime}_{0}))$. Notice that we have
written down $\mathrm{Foot}_{<\ell}(\mathrm{Bin}(Q^{\prime}_{0}))$, which can
be used to reveal $\mathrm{Bin}_{\ell}(Q_{0})$ but not the contents of
$\mathrm{Foot}_{\ell}(\mathrm{Bin}(Q^{\prime}_{0}))$ itself. Then by the
assumption and the chain rule of mutual information, we can reveal
$(1-\varepsilon/(t_{1}+t_{2}\log n))$-fraction of $T(Q_{\Delta})$ on average
from the current bits that we have written down.

Based on Lemma 12, we observe that this $(1-\varepsilon/(t_{1}+t_{2}\log
n))$-fraction of $T(Q_{\Delta})$ contains sufficient information about
$T(Q_{0})$ on average. This also provides a lower bound on the mutual
information between $\mathrm{Foot}_{\ell}(\mathrm{Bin}(Q^{\prime}_{0}))$ and
$T(Q_{\Delta})$. Therefore, it suffices to write down the unknown parts of
$T(Q_{\Delta})$, then use an optimal encoding scheme to write down
$\mathrm{Foot}_{\ell}(\mathrm{Bin}(Q^{\prime}_{0}))$ while conditioning on the
current bits that we have written down and $T(Q_{\Delta})$. This can save more
than $P$ bits of space. In conclusion, we obtain an encoding of the database
using strictly less than $\log(n!)$ bits overall, which contradicts to fact
that the information-theoretic lower bound of the database is $\log(n!)$ bits.

Let us now restate Lemma 11 and give a complete proof assuming that Lemma 12
is true.

See 11

###### Proof of Lemma 11.

To begin a proof by contradiction, assume that

$\Pr_{j\in[n]}[\mathrm{Bin}(Q^{\prime}_{0})\cap\mathrm{Probe}{}(\operatorname{\mathsf{query}}(j))\neq\emptyset]\leq\varepsilon^{4}$

for a sufficiently small $0<\varepsilon<1$. Then, there exists
$\Delta\in\\{\left\lfloor(1-\varepsilon^{3})n/k\right\rfloor,\dots,n/k-2\\}$
which satisfies $\Pr_{q\in
Q_{\Delta}}[\mathrm{Bin}(Q^{\prime}_{0})\cap\mathrm{Probe}{}(q)\neq\emptyset]\leq\varepsilon$,
by an averaging argument. Now we give an encoding of the data structure that
supports $\operatorname{\mathsf{deg}}$ and $\operatorname{\mathsf{adj}}$ on
$G$ as follows:

  1. 1.

Write down the published bits of size $P$ and write down $\Delta$.

  2. 2.

Sample $\ell\in[t_{1}+t_{2}\log n]$ uniformly at random and write it down.

  3. 3.

Write down $\mathrm{Foot}{}_{<\ell}(\mathrm{Bin}{}(Q^{\prime}_{0}))$ with
$w\cdot|\mathrm{Bin}_{<\ell}(Q^{\prime}_{0})|$ bits.

  4. 4.

Write down all the contents of remaining cells according to the increasing
order of their addresses, except
$\mathrm{Foot}{}_{\ell}(\mathrm{Bin}{}(Q^{\prime}_{0}))$. Note that by
enumerating queries $q$ and simulating query algorithm on $q$, one can recover
some entries of $\operatorname{\mathsf{ans}}(Q_{\Delta})$.

  5. 5.

Write down the unknown entries of $T(Q_{\Delta})$ given the known entries of
$\operatorname{\mathsf{ans}}(Q_{\Delta})$.

  6. 6.

Write down $\mathrm{Foot}{}_{\ell}(\mathrm{Bin}{}(Q^{\prime}_{0}))$ with any
optimal encoding, conditioning on $T(Q_{\Delta})$.

The above encoding allows us to reconstruct the data structure as follows.
Firstly, we decode the values of $P$, $\Delta$, and $\ell$. Next, recall that
$\mathrm{Bin}(Q^{\prime}_{0})$ is the set of cells probed by
$\operatorname{\mathsf{deg}}(i)$ and by binary searching $e_{i}$ for $i\in
Q^{\prime}_{0}$ with $\operatorname{\mathsf{adj}}$ queries, so for any
$\ell\in[t_{1}+t_{2}\log n]$, given
$\mathrm{Foot}_{<\ell}(\mathrm{Bin}(Q^{\prime}_{0}))$ we can compute
$\mathrm{Bin}_{\ell}(Q^{\prime}_{0})$ by simulating the procedure up to step
$\ell-1$ using $\mathrm{Foot}{}_{<\ell}(\mathrm{Bin}{}(Q^{\prime}_{0}))$. We
then decode the contents of all remaining cells not in
$\mathrm{Bin}_{\ell}(Q^{\prime}_{0})\setminus\mathrm{Bin}_{<\ell}(Q^{\prime}_{0})$.

Next, we enumerate all queries
$\operatorname{\mathsf{deg}}(\cdot),\operatorname{\mathsf{adj}}(\cdot,\cdot)$
and simulate the query algorithm on the queries with the decoded information.
When we enumerate and successfully simulate the query algorithm on a hard
query tuple
$\operatorname{\mathsf{deg}}(i),\operatorname{\mathsf{adj}}(i,e_{i}),\operatorname{\mathsf{adj}}(i,e_{i}+1)$,
we recover an answer $\operatorname{\mathsf{ans}}(q_{i})$. Putting all the
recovered $\operatorname{\mathsf{ans}}(q_{i})$ together, we know some entries
of $T(Q_{\Delta})$. Therefore, we can put the known entries together with the
missing entries which are written down in Step 5, then we can fully recover
$T(Q_{\Delta})$. After decoding $T(Q_{\Delta})$ completely, we can decode
$\mathrm{Foot}{}_{\ell}(\mathrm{Bin}{}(Q^{\prime}_{0}))$ by referring to the
encoding in Step 6. At this point, we have decoded every single cells of the
data structure. Therefore, the total number of bits we have written down in
the encoding procedure must be at least the information-theoretic minimum of
$G$, which is $\log(n!)$ bits.

We analyze the space of the encoding. Here, we use $\mathcal{P}$ to denote the
random variable of the published bits, which implies $|\mathcal{P}|=P$.

$\displaystyle P+O(\log{\frac{\varepsilon n}{k}})$ (Step 1)
$\displaystyle+O(\log\log n)$ (Step 2)
$\displaystyle+w\cdot\lvert\mathrm{Bin}{}_{<\ell}(Q^{\prime}_{0})\rvert$ (Step
3)
$\displaystyle+\log(n!)-w\cdot\lvert\mathrm{Bin}{}_{\leq\ell}(Q^{\prime}_{0})\rvert$
(Step 4) $\displaystyle+O(\varepsilon k/(t_{1}+t_{2}\log n))$ (Step 5)
$\displaystyle+w\cdot|\mathrm{Bin}_{\ell}(Q^{\prime}_{0})\setminus\mathrm{Bin}_{<\ell}(Q^{\prime}_{0})|$
(Step 6)
$\displaystyle-I(\mathrm{Foot}{}_{\ell}(\mathrm{Bin}{}(Q^{\prime}_{0}));T(Q_{\Delta})\mid\mathrm{Foot}{}_{<\ell}(\mathrm{Bin}(Q^{\prime}_{0})),\ell,\mathcal{P})$
(Step 6)

The following two claims are used to analyze the space for Step 5 and 6. We
first analyze the space at Step 6.

######  Claim 13.

$\mathbb{E}{[}I(\mathrm{Foot}{}_{\ell}(\mathrm{Bin}{}(Q^{\prime}_{0}));T(Q_{\Delta})\mid\mathrm{Foot}{}_{<\ell}(\mathrm{Bin}(Q^{\prime}_{0})),\ell,\mathcal{P})]\geq\Omega\left(\frac{k}{t_{1}+t_{2}\log
n}\right).$

###### Proof of 13.

Since $T(Q_{0})$ can be computed from the cells in
$\mathrm{Bin}(Q^{\prime}_{0})$, we obtain the following.

$\displaystyle
I\left(\mathrm{Foot}{}(\mathrm{Bin}{}(Q^{\prime}_{0}));T(Q_{\Delta})\right)$
$\displaystyle\geq I(T(Q_{0});T(Q_{\Delta}))$
$\displaystyle=H(T(Q_{0}))-H(T(Q_{0})\mid T(Q_{\Delta}))$
$\displaystyle=\sum_{j\in[k]}H(T(q_{j})\mid
T(q_{1}),\dots,T(q_{j-1}))-\sum_{j\in[k]}H(T(q_{j})\mid
T(q_{1}),\dots,T(q_{j-1});T(q^{\prime}_{1}),T(q^{\prime}_{2}),\dots
T(q_{j-1}))$ $\displaystyle\geq\sum_{j\in[k]}H(T(q_{j})\mid
T(q_{1}),\dots,T(q_{j-1}))-H(T(q_{1}))-\sum_{j\in[0.1k,0.9k]}H(T(q_{j+1})\mid
T(q^{\prime}_{j}))$ $\displaystyle\geq\Omega(k)-\Omega(1)-O(\varepsilon
k)=\Omega(k).$

The last inequality is obtained from Lemma 12. Notice that we can consider
$I(\mathrm{Foot}(\mathrm{Bin}(Q^{\prime}_{0}));T(Q_{\Delta}))$ as
$t_{1}+t_{2}\log n$ random variables. Then we obtain the claim from the chain
rule of mutual information, $I(X_{1},\dots,X_{n};Y)=\sum_{i}I(X_{i};Y\mid
X_{<i})$. ∎

Next, we prove the space used at Step 5.

######  Claim 14.

We write down $O(\varepsilon k/(t_{1}+t_{2}\log n))$ bits in Step 5.

###### Proof of 14.

By an average argument and the assumption the following holds:

$\displaystyle\mathbb{E}{}\left[\left|\\{q\in
Q_{\Delta}:\mathrm{Probe}{}(q)\cap\mathrm{Probe}{}_{\ell}(\mathrm{Bin}{}(Q^{\prime}_{0}))\neq\emptyset\\}\right|\right]\leq\varepsilon
k/(t_{1}+t_{2}\log n).$ (4.1)

This implies that we can recover at least $(1-\varepsilon/(t_{1}+t_{2}\log
n))$-fraction of $\operatorname{\mathsf{ans}}(Q_{\Delta})$ in expectation with
the information we have written down in Step 2-4. By a simply counting, we can
recover at least $(1-2\varepsilon/(t_{1}+t_{2}\log n))$-fraction of
$T(Q_{\Delta})$ in expectation. The proof is completed by noting that the
entries of $T(Q_{\Delta})$ are bits and $|T(Q_{\Delta})|=k$. ∎

In overall, the total expected space of the encoding is at most:

$\displaystyle O\left(\log{\frac{\varepsilon n}{k}}\right)+O(\log\log
n)+\log(n!)+O\left(\frac{\varepsilon k}{t_{1}+t_{2}\log
n}\right)-\Omega\left(\frac{k}{t_{1}+t_{2}\log n}\right).$ (4.2)

For a sufficiently large constant $\gamma>0$, if $k\geq\gamma\log^{2}n$, then
for small enough constant $\varepsilon$, the inequality given above implies
that the value is strictly less than $\log(n!)$. This allows us to construct a
data structure that uses less space than the information-theoretic minimum of
$G$, which leads to a contradiction. ∎

###  4.2 Analysis of the Mutual Information

In this section, we prove Lemma 12. See 12 We begin with describing a high-
level idea of the proof. Recall that we divide the universe $[n]$ into $k$
blocks, each is of length $n/k$. Also, for each $q_{t}\in Q_{0}$ and
$q^{\prime}_{t}\in Q_{\Delta}$, we denote $T(q_{t})$ and $T(q^{\prime}_{t})$
as $T((t-1)n/k+1)$ and $T((t-1)n/k+\Delta+1)$, respectively (recall that
$T(i)$ is an indicator random variable defined as
$T(i)\triangleq\mathbf{1}_{\operatorname{\mathsf{ans}}(\operatorname{\mathsf{query}}(i+n/k))-\operatorname{\mathsf{ans}}(\operatorname{\mathsf{query}}(i))\geq
t_{i}}$). Then for each block $i\in\\{1,\dots,k\\}$, we first define the
following random variables:

  * •

$Y_{i}$: the number of right endpoints that land before position $in/k$.

  * •

$Y^{\prime}_{i}$: the number of intervals whose right endpoints that land in
the $i$-th block, and left endpoints land before block $i$.

  * •

$Z_{i}$: the number of intervals whose right endpoints that land in the $i$-th
block, and left endpoints land in block $i$.

  * •

$A_{i}$: the number of right endpoints that land in the $i$-th block, i.e.,
$A_{i}=Y^{\prime}_{i}+Z_{i}$.

Now in the rest of the paper, we fix the threshold $t_{i}$ as the average
number of right endpoints of the intervals in the $i$-th block, i.e.,
$t_{i}=\mathbb{E}{[}Y^{\prime}_{i}+Z_{i}]$. Then we can observe the
followings:

  1. 1.

$T(q_{i})$ only depends on $Y^{\prime}_{i}$ and $Z_{i}$.

  2. 2.

$Z_{i}$ is independent of $T(q_{1}),T(q_{2}),\dots,T(q_{i-1})$.

  3. 3.

$T(q_{1}),T(q_{2}),\dots,T(q_{i})$ can be computed from $Y_{1},\dots,Y_{i+1}$.

  4. 4.

$Y^{\prime}_{i}$ is independent of $Y_{1},\dots,Y_{i-1}$, given $Y_{i}$.

Hence,

$H(T(q_{i})\mid T(q_{1}),T(q_{2}),\dots,T(q_{i-1}))\geq
H(\mathbf{1}_{Y^{\prime}_{i}+Z_{i}\geq t_{i}}\mid
Y_{1},\dots,Y_{i})=H(\mathbf{1}_{Y^{\prime}_{i}+Z_{i}\geq t_{i}}\mid Y_{i}).$

To prove Lemma 12 (i), it suffices to show that $H(T(q_{i})\mid
Y_{i})=\Omega(1)$ from the above inequality. We first show that $Y_{i}$ is
$\Theta(in/k)$ with high probability using a Chernoff bound. Then when $Y_{i}$
is fixed to $m=c\cdot in/k$ for some constant $c>0$, we show that both
$\Pr[A_{i}\geq t_{i}\mid Y_{i}=m]$ and $\Pr[A_{i}\leq t_{i}\mid Y_{i}=m]$ are
$\Omega(1)$, which proves the first part of the lemma (recall that $A_{i}$ is
$Y^{\prime}_{i}+Z_{i}$, which decides $T(q_{i})$). Note that $Y^{\prime}_{i}$
has a binomial distribution, given $Y_{i}$, whereas $Z_{i}$ does not, which
means we cannot directly use the idea of the proof in [PV10]. To resolve the
issue, we first show that with high probability, the information whether
$Y^{\prime}_{i}$ is at least its expectation or not, dominates the value of
$T(q_{i})$, and show that the information-theoretic lower bound of such
information is $\Omega(1)$.

For the proof of Lemma 12 (ii). We show that with high probability, both
values the $T(q_{i+1})$ and $T(q^{\prime}_{i})$ are basically determined by
the number of right endpoints whose left endpoints land before the $(i+1)$-th
block, and the number of right endpoints land in
$\\{(i+1)n/k+1,\dots,(i+1)n/k+\Delta+1\\}$ (the ‘common’ part of $T(q_{i+1})$
and $T(q^{\prime}_{i})$). In the rest of this section, we assume that
$i\in[0.1k,0.9k]$.

####  4.2.1 Proof of Lemma 12 (i)

We begin with the following lemma, which shows that both $\mathbb{E}{[}Y_{i}]$
and $in/k-\mathbb{E}{[}Y_{i}]$ are $\Omega(in/k)$.

######  Lemma 15.

$\mathbb{E}{[}Y_{i}]$ is $O(in/k)$ and is at least $i^{2}n/(4k^{2})$.

###### Proof.

Since $Y_{i}$ cannot be greater than $in/k-1$, it is clear that
$\mathbb{E}{[}Y_{i}]$ is at most $O(in/k)$. Thus, it suffices to show that the
lower bound of $\mathbb{E}{[}Y_{i}]$ is also in $\Theta(in/k)$. To prove this,
we use an averaging argument as follows:

$\displaystyle\mathbb{E}{[}Y_{i}]$
$\displaystyle\geq\sum_{j=1}^{in/(2k)}\Pr[\text{right endpoint of interval
}j\text{ lands in }[in/(2k),in/k]]$
$\displaystyle\geq\frac{in}{2k}\cdot\frac{in/(2k)}{n}=\frac{i^{2}n}{4k^{2}}.$

Since we only consider the case that $i$ is $\Theta(k)$,
$\frac{i^{2}n}{4k^{2}}$ is in $\Theta(in/k)$. ∎

According to the Chernoff bound, the random variable $Y_{i}$ lies within the
range
$\Big{[}\mathbb{E}{[}Y_{i}]-10\sqrt{\mathbb{E}{[}Y_{i}]},\mathbb{E}{[}Y_{i}]+10\sqrt{\mathbb{E}{[}Y_{i}]}\Big{]}$
with a probability greater than $0.999$. Therefore, it suffices to show that
$H(T(q_{i})\mid Y_{i}=m)$ is $\Omega(1)$ when
$m\in\left[\mathbb{E}{[}Y_{i}]-10\sqrt{\mathbb{E}{[}Y_{i}]},\mathbb{E}{[}Y_{i}]+10\sqrt{\mathbb{E}{[}Y_{i}]}\right]$.
As previously explained, we can establish the lemma by proving $\Pr[A_{i}\geq
t_{i}\mid Y_{i}=m]$ and $\Pr[A_{i}\leq t_{i}\mid Y_{i}=m]$ are $\Omega(1)$.
Since $\mathbb{E}{[}A_{i}]=\mathbb{E}{[}Y^{\prime}_{i}]+\mathbb{E}{[}Z_{i}]$
and $Y^{\prime}_{i}$ and $Z_{i}$ are independent, $\Pr[A_{i}\geq t_{i}\mid
Y_{i}=m]$ is at least

$\Pr\biggl{[}Y^{\prime}_{i}\geq\mathbb{E}{[}Y^{\prime}_{i}]\land
Z_{i}\geq\mathbb{E}{[}Z_{i}]\mid
Y_{i}=m\biggr{]}\geq\Pr\biggl{[}Y^{\prime}_{i}\geq\mathbb{E}{[}Y^{\prime}_{i}]\mid
Y_{i}=m\biggr{]}\cdot\Pr[Z\geq\mathbb{E}{[}Z_{i}]].$

Thus, if (i) $\Pr[Y^{\prime}_{i}\geq\mathbb{E}{[}Y^{\prime}_{i}]\mid Y_{i}=m]$
is $\Omega(1)$, and (ii) $\Pr[Z\geq\mathbb{E}{[}Z_{i}]]$ is $\Omega(1)$, we
can prove $\Pr[A_{i}\geq t_{i}\mid Y_{i}=m]$ is $\Omega(1)$.

Unfortunately, for large values of $k$, the property (ii) does not hold, even
if $k$ is asymptotically smaller than $n$. For instance, when $k$ is
$\Theta(n/\log n)$, the reciprocal of the standard deviation of $Z_{i}$ is
$\omega(1)$, which causes $\Pr[Z\geq\mathbb{E}{[}Z_{i}]]$ to be $o(1)$. Note
that same issue occurs when we compute $\Pr[A_{i}\leq t_{i}\mid Y_{i}=m]$ by
computing $\Pr[Y^{\prime}_{i}<\mathbb{E}{[}Y^{\prime}_{i}]\mid Y_{i}=m]$ and
$\Pr[Z<\mathbb{E}{[}Z_{i}]]$ independently.

To overcome this problem, rather than computing the two probabilities
independently, we establish the subsequent lemma motivated from [PV10]. This
lemma proves that the probability of $Y^{\prime}_{i}$ deviating significantly
larger from its expected value is much higher than that of $Z_{i}$ undergoing
the same occurrence.

######  Lemma 16.

For any $k=\omega(1)$, the following holds for any small constant $0<\kappa<1$
that satisfies $k=\omega(\kappa^{-3})$:

  1. (i)

$\Pr\left[Y^{\prime}_{i}-\mathbb{E}{[}Y^{\prime}_{i}]\geq\kappa\cdot\sqrt{\mathbb{E}{[}Y^{\prime}_{i}]}\mid
Y_{i}=m\right]=1/2-O(\kappa)$,

  2. (ii)

$\Pr\left[Y^{\prime}_{i}-\mathbb{E}{[}Y^{\prime}_{i}]\leq-\kappa\cdot\sqrt{\mathbb{E}{[}Y^{\prime}_{i}]}\mid
Y_{i}=m\right]=1/2-O(\kappa)$, and

  3. (iii)

$\Pr\left[\lvert
Z_{i}-\mathbb{E}{[}Z_{i}]\rvert\geq\kappa\cdot\sqrt{\mathbb{E}{[}Y^{\prime}_{i}]}\right]=O(\kappa)$.

Notice that for some appropriate choice of $\kappa$, we can ensure that
$1/2-O(\kappa)$ is close to $1/2$ and that $O(\kappa)$ is small.

###### Proof.

Let $n^{\prime}=in/k-\mathbb{E}{[}Y_{i}]=in/k-m$. Then by Lemma 15, $c\cdot
in/k<n^{\prime}<d\cdot in/k$ for some constant $0<c<d<1$. By Proposition 6,
$Y^{\prime}_{i}$ has a binomial distribution
$B\left(n^{\prime},\frac{n/k}{n-in/k}\right)=B\left(n^{\prime},\frac{1}{k-i}\right)$
when $Y_{i}=m$.

  1. (i)

We use $p$ to denote $1/(k-i)$. Then by the Berry-Essen theorem and the Taylor
expansion,
$\Pr\left[Y^{\prime}_{i}-\mathbb{E}{[}Y^{\prime}_{i}]\geq\kappa\cdot\sqrt{\mathbb{E}{[}Y^{\prime}_{i}]}\mid
Y_{i}=m\right]$ is approximated by
$1-\left(\Phi\left(\frac{\kappa}{2\pi\sqrt{1-p}}\right)+O\left(\sqrt{1/n^{\prime}}\right)\right)\approx
1/2-O\left(\frac{\kappa}{\sqrt{1-p}}\right)$. Since $p$ is $o(1)$ for any
$k=\omega(1)$, $O\left(\frac{\kappa}{\sqrt{1-p}}\right)$ is $O(\kappa)$, which
completes the proof.

  2. (ii)

This can be proved by the same argument as the proof of Lemma 16 (i).

  3. (iii)

For each interval $j+in/k$ in the $i$-th block, its right endpoint also exists
in $i$-th block with probability $p_{j}=\frac{n/k-j}{n-in/k-j}$. Then by
Proposition 6, $Z_{i}$ has a Poisson binomial distribution with a parameter
$(p_{0},\dots,p_{n/k-1})$. Not let $\sigma_{Z_{i}}$ be a standard deviation of
$Z_{i}$. Since
$\sigma_{Z_{i}}^{2}=\sum_{j=0}^{n/k-1}(1-p_{j})p_{j}\leq\sum_{j=0}^{n/k-1}p_{j}$,
and $p_{j}\leq 1/(k-i-1)$ for all $j$, $\sigma_{Z_{i}}^{2}$ is at most
$\frac{n}{k(k-i-1)}$. By the Chebyshev’s inequality, we obtain the following:

$\displaystyle\Pr\left[\lvert
Z_{i}-\mathbb{E}{[}Z_{i}]\rvert\geq\kappa\cdot\sqrt{\mathbb{E}{[}Y^{\prime}_{i}]}\right]\leq\frac{\sigma_{Z_{i}}^{2}}{\kappa^{2}\cdot\mathbb{E}{[}Y^{\prime}_{i}]}$
$\displaystyle\leq\frac{\frac{n}{k(k-i-1)}}{\kappa^{2}\cdot\frac{1}{k-i}\cdot
c\frac{in}{k}}\leq\frac{k-i}{k-i-1}\cdot\frac{1}{\kappa^{2}\cdot c\cdot
i}\leq\frac{2}{\kappa^{2}\cdot i\cdot c}.$

The above implies that for any $k=\omega(\kappa^{-3})$, $\Pr[\lvert
Z_{i}-\mathbb{E}{[}Z_{i}]\rvert\geq\kappa\cdot\sqrt{\mathbb{E}{[}Y^{\prime}_{i}]}]$
is $O(\kappa)$ since $i=\Theta(k)$. ∎

From Lemma 16, we can prove Lemma 12 (i) as follows. Let $T_{Y}(q_{i})$ be an
indicator random variable defined as $T_{Y}(q_{i})=1$ if and only if
$Y^{\prime}_{i}\geq\mathbb{E}{[}Y^{\prime}_{i}\mid Y_{i}=m]$. Then by Lemma 16
(i) and (ii), it is clear that $H(T_{Y}(q_{i}))$ is $\Omega(1)$. On the other
hand, by Lemma 16 and the reverse union bound, $Y^{\prime}_{i}$ deviates from
expectation more than $\kappa\sqrt{\mathbb{E}{[}Y^{\prime}_{i}]}$ whereas
$Z_{i}$ deviates from expectation at most
$\kappa\sqrt{\mathbb{E}{[}Y^{\prime}_{i}]}$ with probability $1-O(\kappa)$.
Hence, with probability $1-O(\kappa)$, $T(q_{i})=T_{Y}(q_{i})$, which proves
Lemma 12 (i).

####  4.2.2 Proof of Lemma 12 (ii)

The proof of Lemma 12 (ii) follows a similar approach as in the proof of Lemma
16 with some modifications. Let $i+1$ denote $i^{\prime}$, and
$S_{Y^{\prime}_{i^{\prime}}}$ be a set of intervals counted by
$Y^{\prime}_{i^{\prime}}$. We then partition $S_{Y^{\prime}_{i^{\prime}}}$
into two sets $S_{1}$ and $S_{2}$ where  (i) $S_{1}$is a set of intervals
whose right endpoints exist in the range
$\\{(i+1)n/k+1,\dots,(i+1)n/k+\Delta+1\\}$, and  (ii)
$S_{2}=S_{Y^{\prime}_{i^{\prime}}}\setminus S_{1}$.  We refer to $S_{1}$ as
the _common part_ of $Y^{\prime}_{i^{\prime}}$, since all intervals in this
set are used to compute both $T(q_{i+1})$ and $T(q^{\prime}_{i})$. Conversely,
we refer to $S_{2}$ as the _distinct part_ of $Y^{\prime}_{i^{\prime}}$, since
all intervals in this set are only used to compute $T(q_{i+1})$ and not
$T(q^{\prime}_{i})$. We then define two random variables
$\tilde{Y}^{\prime}_{i^{\prime}}$ and $Y^{\prime\prime}_{i^{\prime}}$, which
represent the number of intervals such that their left endpoints land before
block $i$, and their right endpoints are in the common and distinct parts of
$Y^{\prime}_{i^{\prime}}$, respectively.

Similar as in the proof of Lemma 12 (i), we consider $Y_{i^{\prime}}$ to be
fixed to $m$ in
$\Big{[}\mathbb{E}{[}Y_{i^{\prime}}]-10\sqrt{\mathbb{E}{[}Y_{i^{\prime}}]},\mathbb{E}{[}Y_{i^{\prime}}]+10\sqrt{\mathbb{E}{[}Y_{i^{\prime}}]}\Big{]}$,
and denote $\frac{i^{\prime}n}{k}-m$ as $n^{\prime}$. Then
$c\cdot\frac{i^{\prime}n}{k}<n^{\prime}<d\cdot\frac{i^{\prime}n}{k}$ for some
constants $0<c<d<1$ by Lemma 15. We introduce the following lemma, which shows
that the probability of $\tilde{Y}^{\prime}_{i^{\prime}}$ is away from its
expectation is much larger than the probability that
$Y^{\prime\prime}_{i^{\prime}}$ or $Z_{i^{\prime}}$ are away from their
expectations, even in the case that the size of the common part of
$Y^{\prime}_{i^{\prime}}$ is minimal (that is,
$\Delta=(1-\varepsilon^{3})\frac{n}{k}$).

######  Lemma 17.

Suppose $k=\omega(1)$ and $\Delta=(1-\varepsilon^{3})\frac{n}{k}$. Then for
any constant $\kappa$ which satisfies
$\sqrt[3]{\varepsilon^{3}/(1-\varepsilon^{3})}=O(\kappa)$ and
$k=\omega(\kappa^{-3})$, the following holds:

  1. (i)

$\Pr\left[\lvert\tilde{Y}_{i^{\prime}}^{\prime}-\mathbb{E}{[}\tilde{Y}_{i^{\prime}}^{\prime}]\rvert\geq\kappa\cdot\sqrt{\mathbb{E}{[}\tilde{Y}_{i^{\prime}}^{\prime}]}\mid
Y_{i^{\prime}}=m\right]=1-O(\kappa)$,

  2. (ii)

$\Pr\left[\lvert
Y^{\prime\prime}_{i^{\prime}}-\mathbb{E}{[}Y^{\prime\prime}_{i^{\prime}}]\rvert\geq\kappa/2\cdot\sqrt{\mathbb{E}{[}\tilde{Y}_{i^{\prime}}^{\prime}]}\mid
Y_{i^{\prime}}=m\right]=O(\kappa)$, and

  3. (iii)

$\Pr\left[\lvert
Z_{i^{\prime}}-\mathbb{E}{[}Z_{i^{\prime}}]\rvert\geq\kappa/2\cdot\sqrt{\mathbb{E}{[}\tilde{Y}_{i^{\prime}}^{\prime}]}\right]=O(\kappa)$.

Notice that our restriction on $\varepsilon$ gives us an upper bound on
$\varepsilon$ depending on $\kappa$.

###### Proof.

  1. (i)

$\tilde{Y}_{i^{\prime}}^{\prime}\sim B(n^{\prime},\tilde{p})$ where
$\tilde{p}=\frac{(1-\varepsilon^{3})n/k}{n-i^{\prime}n/k}=\frac{1-\varepsilon^{3}}{k-i^{\prime}}$
by Proposition 6. Then by the same argument as the proof of Lemma 16 (i),
$\Pr\left[\tilde{Y}_{i^{\prime}}^{\prime}\leq\mathbb{E}{[}\tilde{Y}_{i^{\prime}}^{\prime}]-\kappa\sqrt{\mathbb{E}{[}\tilde{Y}_{i^{\prime}}^{\prime}]}\right]$
is $1/2-O(\kappa)$ when $k$ is $\omega(1)$.

  2. (ii)

From Proposition 6, $Y^{\prime\prime}_{i^{\prime}}\sim
B\left(n^{\prime},\frac{\varepsilon^{3}}{1-\varepsilon^{3}}\tilde{p}\right)$,
which implies the variance of $Y^{\prime\prime}_{i^{\prime}}$ is
$\frac{\varepsilon^{3}}{1-\varepsilon^{3}}n^{\prime}\tilde{p}\left(1-\frac{\varepsilon^{3}}{1-\varepsilon^{3}}\tilde{p}\right)$.
Then by the Chebyshev’s inequality, we obtain the following when
$\sqrt[3]{\varepsilon^{3}/(1-\varepsilon^{3})}$ is $O(\kappa)$ (recall that
$\mathbb{E}{[}\tilde{Y}_{i^{\prime}}^{\prime}]$ is $n^{\prime}\tilde{p}$):

$\displaystyle\Pr\left[\left|Y^{\prime\prime}_{i^{\prime}}-\mathbb{E}{[}Y^{\prime\prime}_{i^{\prime}}]\right|\geq\kappa/2\cdot\sqrt{\mathbb{E}{[}\tilde{Y}_{i^{\prime}}^{\prime}]}\right]$
$\displaystyle\leq\frac{4\frac{\varepsilon^{3}}{1-\varepsilon^{3}}\left(1-\frac{\varepsilon^{3}}{1-\varepsilon^{3}}\cdot\tilde{p}\right)}{\kappa^{2}}=\frac{4\frac{\varepsilon^{3}}{1-\varepsilon^{3}}\left(1-\frac{\varepsilon^{3}}{k-i}\right)}{\kappa^{2}}$
$\displaystyle\leq\frac{4\varepsilon^{3}}{(1-\varepsilon^{3})\kappa^{2}}=O(\kappa).$

  3. (iii)

Recall that $Z_{i^{\prime}}$ has a Poisson binomial distribution with
$(p_{0},\dots,p_{n/k-1})$ where $p_{j}=\frac{n/k-j}{n-i^{\prime}n/k-j}$. Now
let $\sigma_{Z_{i^{\prime}}}$ be a standard deviation of $Z_{i^{\prime}}$.
Then $\sigma_{Z_{i^{\prime}}}^{2}$ is at most $\frac{n}{k(k-i^{\prime}-1)}$
(see the proof of Lemma 16 (iii)). Then by the Chebyshev’s inequality, we
obtain the following:

$\displaystyle\Pr\left[\lvert
Z_{i^{\prime}}-\mathbb{E}{[}Z_{i^{\prime}}]\rvert\geq\kappa/2\cdot\sqrt{\mathbb{E}{[}\tilde{Y}_{i^{\prime}}^{\prime}]}\right]\leq\frac{4\sigma_{Z_{i^{\prime}}}^{2}}{\kappa^{2}\cdot\mathbb{E}{[}\tilde{Y}_{i^{\prime}}^{\prime}]}$
$\displaystyle\leq\frac{4\frac{n}{k(k-i^{\prime}-1)}}{(1-\varepsilon^{3})\kappa^{2}\cdot\frac{1}{k-i^{\prime}}\cdot
c\frac{in}{k}}\leq\frac{8}{(1-\varepsilon^{3})\kappa^{2}\cdot i^{\prime}\cdot
c}.$

The above implies that for any $k=\omega(\varepsilon^{-3})$,
$\Pr\left[\left\lvert
Z_{i^{\prime}}-\mathbb{E}{[}Z_{i^{\prime}}]\right\rvert\geq\kappa\cdot\sqrt{\mathbb{E}{[}\tilde{Y}_{i^{\prime}}^{\prime}]}\right]$
is $O(\kappa)$.

∎

Let us proceed to the final step of the proof. We can observe that the number
of right endpoints falling within the $i$-th block is given by the sum of
three random variables: $\tilde{Y}_{i^{\prime}}^{\prime}$,
$Y_{i^{\prime}}^{\prime\prime}$, and $Z_{i^{\prime}}$. Similarly, for the
interval $[(i-1)n/k+\Delta+1,in/k+\Delta]$, which we refer to as the
$(i,\Delta)$-th block, the number of right endpoints falling within this
interval is given by the sum of three random variables:
$\tilde{Y_{i^{\prime}}^{\prime}}$, $Y_{i,\Delta}^{\prime\prime}$, and
$Z_{i,\Delta}$. Here, we define $Y_{i,\Delta}^{\prime\prime}$ as the number of
intervals whose left endpoints land before the $(i,\Delta)$-th block and whose
right endpoints land before the $i$-th block. On the other hand,
$Z_{i,\Delta}$ represents the number of intervals whose both left and right
endpoints fall within the $(i,\Delta)$-th block.

Note that we cannot directly apply Lemma 17 (ii) and (iii) to
$Y^{\prime\prime}_{i,\Delta}$ and $Z_{i,\Delta}$, as they have different
distributions from $Y^{\prime\prime}_{i^{\prime}}$ and $Z_{i^{\prime}}$,
respectively. However, the following lemma implies that we can still make the
same argument as Lemma 17 (ii) and (iii) for $Y^{\prime\prime}_{i,\Delta}$ and
$Z_{i,\Delta}$, by replacing the variances of $Y^{\prime\prime}_{i^{\prime}}$
and $Z_{i^{\prime}}$ in the proofs into the variances of
$Y_{i,\Delta}^{\prime\prime}$ and $Z_{i,\Delta}$, respectively:

######  Lemma 18.

(a)
$\sigma_{Y^{\prime\prime}_{i,\Delta}}^{2}=O(\sigma_{Y^{\prime\prime}_{i^{\prime}}}^{2})$,
and (b) $\sigma_{Z_{i,\Delta}}^{2}$ is at most $\frac{n}{k(k-i^{\prime}-1)}$.

###### Proof.

  1. (i)

Recall that $Y^{\prime\prime}_{i^{\prime}}$ has a binomial distribution
$B(n^{\prime},\frac{\varepsilon^{3}}{k-i^{\prime}})$, and the difference
between the leftmost position of the $i^{\prime}$-th block and the
$(i,\Delta)$-th block is $(n/k-\Delta)\leq\varepsilon^{3}\cdot n/k$. This
implies $Y^{\prime\prime}_{i,\Delta}$ has a binomial distribution
$B(n^{\prime}_{i,\Delta},\tilde{p}_{i,\Delta})$ where
$n^{\prime}_{i,\Delta}=O(n^{\prime})$, and
$\frac{\varepsilon^{3}}{k-i^{\prime}}\leq\tilde{p}_{i,\Delta}\leq\varepsilon^{3}\frac{n/k}{n-(i+\varepsilon^{3})n/k}=\frac{\varepsilon^{3}}{k-i-\varepsilon^{3}}\leq\frac{\varepsilon^{3}}{2(k-i)}$,
which proves the lemma.

  2. (ii)

$Z_{i,\Delta}$ has a Poisson binomial distribution with
$p_{j,\Delta}=\frac{n/k-j}{n-(i+\Delta)n/k-j}\leq\frac{n/k-j}{n-i^{\prime}n/k-j}$
for $j\in\\{0,\dots,n/k-1\\}$, which proves the lemma (see the proof of Lemma
16 (iii)).

∎

Now we prove Lemma 12 (ii) as follows: We first choose a constant $\kappa$
that satisfies the conditions of Lemma 17. Then by Lemmas 17 and 18,  (i)
$\tilde{Y}_{i^{\prime}}^{\prime}$deviates from its expectation more than
$\kappa\sqrt{\mathbb{E}{[}\tilde{Y}_{i^{\prime}}^{\prime}]}$, and  (ii) both
$Y^{\prime\prime}_{i^{\prime}}+Z_{i^{\prime}}$ and
$Y^{\prime\prime}_{i,\Delta}+Z_{i,\Delta}$ deviate from their expectations at
most $\kappa\sqrt{\mathbb{E}{[}\tilde{Y}_{i^{\prime}}^{\prime}]}$ with
probability $1-O(\kappa)$ by applying the reverse union bound. Hence,
$T(q_{i+1})$ and $T(q^{\prime}_{i})$ are the same with probability
$1-O(\kappa)=1-\sqrt[3]{\varepsilon^{3}/(1-\varepsilon^{3})}$, which is
$1-O(\varepsilon)$ for small enough constant $\varepsilon$. This completes the
proof of Lemma 12 (ii).

##  5 Data Structures for Individual Queries

In this section, we propose two accessible data structures on interval graph
with $n$ vertices as follows. First, we show that there exists a data
structure that can answer $\operatorname{\mathsf{adj}}$ queries in $O(1)$ time
with $O(\sqrt{n}\log n)$-bit redundancy in the RAM model (Theorem 3).
Afterward, we show that there exists a data structure that can answer
$\operatorname{\mathsf{deg}}$ queries in $O(1)$ time with $O(n^{2/3}\log
n)$-bit redundancy in the RAM model (Theorem 4). Note that all data structures
are _non-systematic (encoding)_ [FH11]. In a non-systematic data structure,
one cannot access the input graph after preprocessing so that only the data
structure can be used for answering queries333Note that this does not mean
that one cannot reconstruct the input with any non-systematic data structure.
For example, we can reconstruct the input graph using the data structure of
Theorem 3 by checking all possible $\operatorname{\mathsf{adj}}$ queries.. In
the rest of the paper, we ignore all floors and ceilings which do not affect
the main result.

See 3

###### Proof.

We first divide an interval $[1,n]$ into blocks of size $\sqrt{n}$. If the
vertex $i$ has its right endpoint in the $k$-th block at position $j$, we can
store the length of $i$ using the block number $k$ along with the offset $j$.
Then the length of each interval in $G$ is enough to check adjacency since the
left endpoint of $I_{i}$ is fixed to $i$. Notice that each interval within the
$k$-th block can only contain the right endpoints in the $j$-th block where
$j\geq i$. Additionally, we only have to store the offset for the last block.
Therefore, by using the encoding of Lemma 7 ([DPT10]) to encode the lengths of
intervals in the same block, the total space required to store all interval
lengths can be expressed as follows:

$\displaystyle\sum_{k=1}^{\sqrt{n}}\underbrace{\sqrt{n}}_{\text{vertices per
block}}\left(\underbrace{\log(\sqrt{n}-k)}_{\text{block
index}}+\underbrace{\log\sqrt{n}}_{\text{offset}}\right)+O(\sqrt{n}\log n).$

Let us now show that $\sum_{k=1}^{\sqrt{n}}\sqrt{n}(\log(\sqrt{n}-k)\sqrt{n})$
is $(\log(n!)+O(\sqrt{n}\log n))$, which proves the theorem.

$\displaystyle\sqrt{n}\sum_{k=1}^{\sqrt{n}}\log((\sqrt{n}-k)\sqrt{n})$
$\displaystyle=\sqrt{n}\sum_{k=\sqrt{n}}^{1}\log(k\sqrt{n})$
$\displaystyle=\sum_{k=\sqrt{n}}^{2}\sum_{i=1}^{\sqrt{n}}\log(k\sqrt{n}-i+i)+\sqrt{n}\log(\sqrt{n})$
$\displaystyle=\sum_{k=\sqrt{n}}^{2}\sum_{i=1}^{\sqrt{n}}\left(\log(k\sqrt{n}-i)+\log(1+\frac{i}{k\sqrt{n}-i})\right)+\sqrt{n}\log(\sqrt{n})$
$\displaystyle\leq\log(n!)+\sum_{k=\sqrt{n}}^{2}\sum_{i=0}^{\sqrt{n}}\log(1+\frac{i}{k\sqrt{n}-i})+\sqrt{n}\log
n$
$\displaystyle<\log(n!)+\sum_{k=\sqrt{n}}^{2}\sum_{i=2}^{\sqrt{n}}\log(1+\frac{i}{k\sqrt{n}-i})+2\sqrt{n}\log
n.$

The summation with $k=1$ is at most $1/2\sqrt{n}\log{n}$.

$\displaystyle<\log(n!)+\sum_{k=\sqrt{n}}^{2}\sum_{i=0}^{\sqrt{n}}\frac{i}{(k\sqrt{n}-i)}+O(\sqrt{n}\log{n})$
$\displaystyle\leq\log(n!)+\sqrt{n}\sum_{k=\sqrt{n}}^{2}\frac{\sqrt{n}}{(k\sqrt{n}-\sqrt{n})}+O(\sqrt{n}\log{n}).$

Note that $i\leq\sqrt{n}$. Hence, we can bound the above by

$\displaystyle\log(n!)+\sqrt{n}\sum_{k=2}^{\infty}\frac{1}{k-1}+O(\sqrt{n}\log{n})$
$\displaystyle\leq\log(n!)+O(\sqrt{n}\log n).$

∎

Notice the data structure of Theorem 3 can support
$\operatorname{\mathsf{deg}}(i)$ queries in $O(n)$ time by answering the
number of corresponding intervals of vertices in $\\{1,\dots,e_{i}\\}$ that
intersect with $[i,e_{i}]$. Also, in the cell-probe model, we can support
$\operatorname{\mathsf{adj}}{}$ queries in $O(1)$ probes while using $\log
n!+O(1)$ bits of space (see Appendix A).

See 4

###### Proof.

As mentioned in Section 2.3, We first divide the intervals into blocks of size
$n^{1/3}$. For each interval $i$ in the $k$-th block, then all the intervals
that intersect with $i$ are within exactly one of the four following cases
(See Fig. 1):

  1. (i)

the left endpoint lands before the $k$-th block, and the right endpoint lands
after the $k$-th block;

  2. (ii)

the left endpoint lands in the interval $i$;

  3. (iii)

the left endpoint lands before the $k$-th block, and the right endpoint lands
in the $k$-th block;

  4. (iv)

the left endpoint lands in the $k$-th block but before the position $i$.

For any two intervals which are in the same block, the number of intersecting
intervals in the case (i) are always the same. Hence, we can store the number
of intervals in the case (i) using $O({n}^{2/3}\log n)$ bits in total. Next,
assume that there are $b_{k}$ right endpoints that land in the $k$-th block.
Then the numbers of intervals in other three cases are at most  (ii) $n-i$,
(iii) $b_{k}$,  (iv) $i-(k-1)n^{1/3}$,  respectively, which implies the total
number of intervals in the cases (ii)-(iv) intersecting with $i$ is at most
$n-(k-1)n^{1/3}+b_{k}$. Therefore, for each interval $i$ in the $k$-th block,
we can encode $\operatorname{\mathsf{deg}}(i)$ using the $O({n}^{2/3}\log
n)$-bit encoding for storing the number of intersecting intervals with the
case (i), along with $n^{2/3}$ arrays of integers which store the number of
intersecting intervals in the cases (ii)-(iv), where the $k$-th array is of
universe $[n-(k-1)n^{1/3}+b_{k}]^{\sqrt[3]{n}}$. We store the sizes of the
alphabets of the $n^{2/3}$ arrays with an extra array of $O(n^{2/3}\log n)$
bits, so that we can use Lemma 7 to encode the $n^{2/3}$ arrays. Overall, we
obtain a data structure of
$\sum_{k=n^{2/3}}^{1}n^{1/3}\log{(n-(k-1)n^{1/3}+b_{k})}+O(n^{2/3}\log n)$
bits in total. Now let $k^{\prime}=n^{2/3}-k+1$ which we use to replace
$b_{k}$. Then the following shows that
$\sum_{k=n^{2/3}}^{1}n^{1/3}\log{(n-(k-1)n^{1/3}+b_{k})}\leq\sum_{k=n^{2/3}}^{1}n^{1/3}\log{(kn^{1/3}+b_{k^{\prime}})}$
is $O(n^{2/3}\log n)$, which proves the theorem:

$\displaystyle\sum_{k=n^{2/3}}^{1}n^{1/3}\log(kn^{1/3}+b_{k^{\prime}})$
$\displaystyle=\sum_{k=n^{2/3}}^{1}\sum_{i=0}^{n^{1/3}-1}\log(kn^{1/3}-i+i+b_{k^{\prime}})$
$\displaystyle=\sum_{k=n^{2/3}}^{1}\sum_{i=0}^{n^{1/3}-1}\log(kn^{1/3}-i)+\log\left(1+\frac{i+b_{k^{\prime}}}{kn^{1/3}-i}\right)$
$\displaystyle=\log(n!)+\sum_{k=n^{2/3}}^{1}\sum_{i=0}^{n^{1/3}-1}\log\left(1+\frac{i+b_{k^{\prime}}}{kn^{1/3}-i}\right)$
$\displaystyle\leq\log(n!)+\sum_{k=n^{2/3}}^{1}n^{1/3}\log\left(1+\frac{n^{1/3}+b_{k^{\prime}}}{kn^{1/3}-n^{1/3}+1}\right)$
$\displaystyle\leq\log(n!)+O(n^{1/3}\log
n)+\sum_{k=n^{2/3}}^{2}n^{1/3}\log\left(1+\frac{n^{1/3}+b_{k^{\prime}}}{kn^{1/3}-n^{1/3}+1}\right).$

We used that $n^{1/3}+b_{n^{2/3}}$ is $O(n)$. Let us now bound the remaining
sum form and set $a_{k}=n^{1/3}+b_{k^{\prime}}$.

$\displaystyle\sum_{k=n^{2/3}}^{2}n^{1/3}\log\left(1+\frac{n^{1/3}+b_{k^{\prime}}}{kn^{1/3}-n^{1/3}+1}\right)$
$\displaystyle\leq n^{1/3}\sum_{\ell=\frac{2}{3}\log
n}^{0}\sum_{k=2^{\ell}}^{2^{\ell-1}}\log\left(1+\frac{a_{k}}{(k-1)n^{1/3}}\right)$
$\displaystyle\leq n^{1/3}\sum_{\ell=\frac{2}{3}\log
n}^{0}\sum_{k=2^{\ell}}^{2^{\ell-1}}\log\left(1+\frac{a_{k}}{(2^{\ell-1}-1)n^{1/3}}\right).$

As for all $\ell\in\\{0,\dots,\frac{2}{3}\log n\\}$,
$\sum_{k=2^{\ell}}^{2^{\ell-1}}a_{k}=\sum_{k=2^{\ell}}^{2^{\ell-1}}(n^{1/3}+b_{k^{\prime}})\leq
2n$ (notice that $\sum_{k^{\prime}}b_{k^{\prime}}=n$). Also, by the concavity
of logarithm and Jensen’s inequality,
$\sum_{i=1}^{n}\frac{\log(1+x_{i})}{n}\leq\log(1+(\sum_{i}x_{i})/n)$.
Therefore, the above equation is at most

$n^{1/3}\sum_{\ell=\frac{2}{3}\log
n}^{0}2^{\ell-1}\cdot\log\left(1+\frac{2n/2^{\ell-1}}{(2^{\ell-1}-1)n^{1/3}}\right).$

Now for $\ell\in\\{0,\dots,\frac{2}{3}\log n\\}$, we define
$g(\ell)=2^{\ell-1}\log(1+\frac{n^{2/3}}{2^{2\ell-2}})$. If $2^{2\ell-2}\leq
n^{2/3}$, i.e., $\ell\leq\frac{1}{3}\log n+O(1)$, we have
$g(\ell)=O(n^{1/3}\log n)$. On the other hand, if $2^{2\ell-2}>n^{2/3}$, i.e.,
$\ell\geq\frac{1}{3}\log n+\Omega(1)$, we have $g(\ell)\leq
O(\frac{n^{2/3}}{2^{\ell}})$, as $\log(1+x)\leq x$. So we have $g(\ell)\leq
2^{\ell-1}\frac{n^{2/3}}{2^{2\ell-2}}$ in this case. Hence, $g(\ell)$ is
maximized when $\ell$ is $\frac{1}{3}\log n\pm O(1)$. In this case, the above
equation is at most $\Theta(n^{2/3}\log n)$.

∎

Notice that the data structure of Theorem 4 can also support
$\operatorname{\mathsf{adj}}(i,j)$ queries in $O(n)$ time by completely
reconstructing the graph. This is done as follows. To address the query
$\operatorname{\mathsf{adj}}(i,j)$, we utilize the degrees of vertices from
$1$ to $\max{}(i,j)$ and decode the corresponding intervals. Initially, we
compute $\operatorname{\mathsf{deg}}(1)$, which allows us to decode $I_{1}$ as
$[1,\operatorname{\mathsf{deg}}(1)]$ (note that all intervals in $I$ intersect
with $I_{1}$ should have their left endpoints in $[2,e_{i}]$). For
$k\in\\{2,\dots,\max\\{i,j\\}\\}$, we can decode $I_{k}$ using
$\operatorname{\mathsf{deg}}(k)$ and the intervals ${I_{1},\dots,I_{k-1}}$.
Specifically, $I_{k}=[k,\operatorname{\mathsf{deg}}(k)-k^{\prime}]$, where
$k^{\prime}$ represents the number of intervals in ${I_{1},\dots,I_{k-1}}$
that cross the point $k$. Finally, to determine
$\operatorname{\mathsf{adj}}(i,j)$, we check whether $I_{i}$ and $I_{j}$
intersect or not.

## References

  * [Aca+21] Hüseyin Acan, Sankardeep Chakraborty, Seungbum Jo and Srinivasa Rao Satti  “Succinct Encodings for Families of Interval Graphs”  In _Algorithmica_ 83.3, 2021, pp. 776–794  DOI: 10.1007/S00453-020-00710-W
  * [ADS08] Luca Castelli Aleardi, Olivier Devillers and Gilles Schaeffer  “Succinct representations of planar maps”  In _Theor. Comput. Sci._ 408.2-3, 2008, pp. 174–187  DOI: 10.1016/j.tcs.2008.08.016
  * [Bar+01] Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor and Baruch Schieber  “A unified approach to approximating resource allocation and scheduling”  In _J. ACM_ 48.5, 2001, pp. 1069–1090  DOI: 10.1145/502102.502107
  * [Ben59] S. Benser  “On the topology of the genetic fine structure”  In _Proc. Nat. Acad. Sci._ 45, 1959, pp. 1607–1620
  * [BL13] Karl Bringmann and Kasper Green Larsen  “Succinct Sampling from Discrete Distributions”  In _Proceedings of the Forty-Fifth Annual ACM Symposium on Theory of Computing_ , STOC ’13  New York, NY, USA: Association for Computing Machinery, 2013, pp. 775–782  DOI: 10.1145/2488608.2488707
  * [BJ22] Boris Bukh and R. Amzi Jeffs  “Enumeration of interval graphs and $d$-representable complexes”, 2022  arXiv:2203.12063 [math.CO]
  * [CR10] Amit Chakrabarti and Oded Regev  “An Optimal Randomized Cell Probe Lower Bound for Approximate Nearest Neighbor Searching”  In _SIAM J. Comput._ 39.5, 2010, pp. 1919–1940  DOI: 10.1137/080729955
  * [CKL18] Diptarka Chakraborty, Lior Kamma and Kasper Green Larsen  “Tight Cell Probe Bounds for Succinct Boolean Matrix-Vector Multiplication”  In _Proceedings of the 50th Annual ACM SIGACT Symposium on Theory of Computing_ , STOC 2018  New York, NY, USA: Association for Computing Machinery, 2018, pp. 1297–1306  DOI: 10.1145/3188745.3188830
  * [Cha+23] Sankardeep Chakraborty, Roberto Grossi, Kunihiko Sadakane and Srinivasa Rao Satti  “Succinct representation for (non)deterministic finite automata”  In _J. Comput. Syst. Sci._ 131, 2023, pp. 1–12  DOI: 10.1016/j.jcss.2022.07.002
  * [CM96] David R. Clark and J. Ian Munro  “Efficient Suffix Trees on Secondary Storage (extended Abstract)”  In _Proceedings of the Seventh Annual ACM-SIAM Symposium on Discrete Algorithms, 28-30 January 1996, Atlanta, Georgia, USA_ ACM/SIAM, 1996, pp. 383–391  URL: http://dl.acm.org/citation.cfm?id=313852.314087
  * [CGL15] Raphaël Clifford, Allan Grønlund and Kasper Green Larsen  “New Unconditional Hardness Results for Dynamic and Online Problems”  In _IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015_ IEEE Computer Society, 2015, pp. 1089–1107  DOI: 10.1109/FOCS.2015.71
  * [DPT10] Yevgeniy Dodis, Mihai Pǎtraşcu and Mikkel Thorup  “Changing base without losing space”  In _Proceedings of the 42nd ACM Symposium on Theory of Computing, STOC 2010, Cambridge, Massachusetts, USA, 5-8 June 2010_ ACM, 2010, pp. 593–602  DOI: 10.1145/1806689.1806771
  * [FK14] Arash Farzan and Shahin Kamali  “Compact Navigation and Distance Oracles for Graphs with Small Treewidth”  In _Algorithmica_ 69.1, 2014, pp. 92–116  DOI: 10.1007/S00453-012-9712-9
  * [FM13] Arash Farzan and J. Ian Munro  “Succinct encoding of arbitrary graphs”  In _Theor. Comput. Sci._ 513, 2013, pp. 38–52  DOI: 10.1016/j.tcs.2013.09.031
  * [FH11] Johannes Fischer and Volker Heun  “Space-Efficient Preprocessing Schemes for Range Minimum Queries on Static Arrays”  In _SIAM J. Comput._ 40.2, 2011, pp. 465–492  DOI: 10.1137/090779759
  * [FS09] Philippe Flajolet and Robert Sedgewick  “Analytic combinatorics”  cambridge University press, 2009
  * [GNP20] Travis Gagie, Gonzalo Navarro and Nicola Prezza  “Fully Functional Suffix Trees and Optimal Text Searching in BWT-Runs Bounded Space”  In _J. ACM_ 67.1, 2020, pp. 2:1–2:54  DOI: 10.1145/3375890
  * [GM07] Anna Gál and Peter Bro Miltersen  “The cell probe complexity of succinct data structures”  In _Theor. Comput. Sci._ 379.3, 2007, pp. 405–417  DOI: 10.1016/J.TCS.2007.02.047
  * [Gol04] M. C. Golumbic  “Algorithmic Graph Theory and Perfect Graphs”, 2004
  * [Gol85] Martin Charles Golumbic  “Interval graphs and related topics”  In _Discret. Math._ 55.2, 1985, pp. 113–121  DOI: 10.1016/0012-365X(85)90039-1
  * [GS93] Martin Charles Golumbic and Ron Shamir  “Complexity and Algorithms for Reasoning about Time: A Graph-Theoretic Approach”  In _J. ACM_ 40.5, 1993, pp. 1108–1133  DOI: 10.1145/174147.169675
  * [Gol09] Alexander Golynski  “Cell probe lower bounds for succinct data structures”  In _Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009_ SIAM, 2009, pp. 625–634  DOI: 10.1137/1.9781611973068.69
  * [GL16] Allan Grønlund and Kasper Green Larsen  “Towards Tight Lower Bounds for Range Reporting on the RAM”  In _43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy_ 55, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, pp. 92:1–92:12  DOI: 10.4230/LIPICS.ICALP.2016.92
  * [Haj57] G. Hajós  “Über eine Art von Graphen”  In _Int. Math. Nachr._ 11, 1957, pp. 1607–1620
  * [Han82] P. Hanlon  “Counting Interval Graphs”  In _Transactions of the American Mathematical Society_ 272.2 American Mathematical Society, 1982, pp. 383–426  DOI: 10.2307/1998705
  * [Jac89] Guy Jacobson  “Space-efficient Static Trees and Graphs”  In _30th Annual Symposium on Foundations of Computer Science, Research Triangle Park, North Carolina, USA, 30 October - 1 November 1989_ IEEE Computer Society, 1989, pp. 549–554  DOI: 10.1109/SFCS.1989.63533
  * [Lar12] Kasper Green Larsen  “Higher Cell Probe Lower Bounds for Evaluating Polynomials”  In _53rd Annual IEEE Symposium on Foundations of Computer Science, FOCS 2012, New Brunswick, NJ, USA, October 20-23, 2012_ IEEE Computer Society, 2012, pp. 293–301  DOI: 10.1109/FOCS.2012.21
  * [Lar12a] Kasper Green Larsen  “The cell probe complexity of dynamic range counting”  In _Proceedings of the 44th Symposium on Theory of Computing Conference, STOC 2012, New York, NY, USA, May 19 - 22, 2012_ ACM, 2012, pp. 85–94  DOI: 10.1145/2213977.2213987
  * [LNN15] Kasper Green Larsen, Jelani Nelson and Huy L. Nguyên  “Time Lower Bounds for Nonadaptive Turnstile Streaming Algorithms”  In _Proceedings of the Forty-Seventh Annual ACM on Symposium on Theory of Computing, STOC 2015, Portland, OR, USA, June 14-17, 2015_ ACM, 2015, pp. 803–812  DOI: 10.1145/2746539.2746542
  * [LWY20] Kasper Green Larsen, Omri Weinstein and Huacheng Yu  “Crossing the Logarithmic Barrier for Dynamic Boolean Data Structure Lower Bounds”  In _SIAM J. Comput._ 49.5, 2020  DOI: 10.1137/18M1198429
  * [Li+23] Tianxiao Li, Jingxun Liang, Huacheng Yu and Renfei Zhou  “Tight Cell-Probe Lower Bounds for Dynamic Succinct Dictionaries”  In _CoRR_ abs/2306.02253, 2023  DOI: 10.48550/ARXIV.2306.02253
  * [Liu21] Mingmou Liu  “Nearly Tight Lower Bounds for Succinct Range Minimum Query”  In _CoRR_ abs/2111.02318, 2021  arXiv: https://arxiv.org/abs/2111.02318
  * [LPY18] Mingmou Liu, Xiaoyin Pan and Yitong Yin  “Randomized Approximate Nearest Neighbor Search with Limited Adaptivity”  In _ACM Trans. Parallel Comput._ 5.1, 2018, pp. 3:1–3:26  DOI: 10.1145/3209884
  * [LY20] Mingmou Liu and Huacheng Yu  “Lower bound for succinct range minimum query”  In _Proccedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020, Chicago, IL, USA, June 22-26, 2020_ ACM, 2020, pp. 1402–1415  DOI: 10.1145/3357713.3384260
  * [Mil+98] Peter Bro Miltersen, Noam Nisan, Shmuel Safra and Avi Wigderson  “On Data Structures and Asymmetric Communication Complexity”  In _J. Comput. Syst. Sci._ 57.1, 1998, pp. 37–49  DOI: 10.1006/jcss.1998.1577
  * [MN16] J. Ian Munro and Patrick K. Nicholson  “Succinct Posets”  In _Algorithmica_ 76.2, 2016, pp. 445–473  DOI: 10.1007/s00453-015-0047-1
  * [Mun+12] J. Ian Munro, Rajeev Raman, Venkatesh Raman and S. Srinivasa Rao  “Succinct representations of permutations and functions”  In _Theor. Comput. Sci._ 438, 2012, pp. 74–88  DOI: 10.1016/J.TCS.2012.03.005
  * [MR04] J. Ian Munro and S. Srinivasa Rao  “Succinct Representations of Functions”  In _Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings_ 3142, Lecture Notes in Computer Science  Springer, 2004, pp. 1006–1015  DOI: 10.1007/978-3-540-27836-8“˙84
  * [MW18] J. Ian Munro and Kaiyu Wu  “Succinct Data Structures for Chordal Graphs”  In _29th International Symposium on Algorithms and Computation, ISAAC 2018, December 16-19, 2018, Jiaoxi, Yilan, Taiwan_ 123, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2018, pp. 67:1–67:12  DOI: 10.4230/LIPIcs.ISAAC.2018.67
  * [Nav16] Gonzalo Navarro  “Compact Data Structures - A Practical Approach”  Cambridge University Press, 2016  URL: http://www.cambridge.org/de/academic/subjects/computer-science/algorithmics-complexity-computer-algebra-and-computational-g/compact-data-structures-practical-approach?format=HB
  * [NN14] Gonzalo Navarro and Yakov Nekrich  “Optimal Dynamic Sequence Representations”  In _SIAM J. Comput._ 43.5, 2014, pp. 1781–1806  DOI: 10.1137/130908245
  * [NS14] Gonzalo Navarro and Kunihiko Sadakane  “Fully Functional Static and Dynamic Succinct Trees”  In _ACM Trans. Algorithms_ 10.3, 2014, pp. 16:1–16:39  DOI: 10.1145/2601073
  * [PTW10] Rina Panigrahy, Kunal Talwar and Udi Wieder  “Lower Bounds on Near Neighbor Search via Metric Expansion”  In _51th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2010, October 23-26, 2010, Las Vegas, Nevada, USA_ IEEE Computer Society, 2010, pp. 805–814  DOI: 10.1109/FOCS.2010.82
  * [PT09] Mihai Puatracscu and Mikkel Thorup  “Higher Lower Bounds for Near-Neighbor and Further Rich Problems”  In _SIAM J. Comput._ 39.2, 2009, pp. 730–741  DOI: 10.1137/070684859
  * [PT06] Mihai Pǎtraşcu and Mikkel Thorup  “Time-space trade-offs for predecessor search”  In _Proceedings of the 38th Annual ACM Symposium on Theory of Computing, Seattle, WA, USA, May 21-23, 2006_ ACM, 2006, pp. 232–240  DOI: 10.1145/1132516.1132551
  * [PT07] Mihai Pǎtraşcu and Mikkel Thorup  “Randomization does not help searching predecessors”  In _Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2007, New Orleans, Louisiana, USA, January 7-9, 2007_ SIAM, 2007, pp. 555–564  URL: http://dl.acm.org/citation.cfm?id=1283383.1283443
  * [PV10] Mihai Pǎtraşcu and Emanuele Viola  “Cell-Probe Lower Bounds for Succinct Partial Sums”  In _Proceedings of the Twenty-First Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2010, Austin, Texas, USA, January 17-19, 2010_ SIAM, 2010, pp. 117–122  DOI: 10.1137/1.9781611973075.11
  * [RR18] Sivaramakrishnan Natarajan Ramamoorthy and Anup Rao  “Lower Bounds on Non-Adaptive Data Structures Maintaining Sets of Numbers, from Sunflowers”  In _33rd Computational Complexity Conference (CCC 2018)_ 102, Leibniz International Proceedings in Informatics (LIPIcs)  Dagstuhl, Germany: Schloss Dagstuhl–Leibniz-Zentrum für Informatik, 2018, pp. 27:1–27:16  DOI: 10.4230/LIPIcs.CCC.2018.27
  * [SV08] Pranab Sen and Srinivasan Venkatesh  “Lower bounds for predecessor searching in the cell probe model”  In _J. Comput. Syst. Sci._ 74.3, 2008, pp. 364–385  DOI: 10.1016/j.jcss.2007.06.016
  * [Sie89] Alan Siegel  “On Universal Classes of Fast High Performance Hash Functions, Their Time-Space Tradeoff, and Their Applications”  In _Proceedings of the 30th Annual Symposium on Foundations of Computer Science_ , SFCS ’89  IEEE Computer Society, 1989, pp. 20–25  DOI: 10.1109/SFCS.1989.63450
  * [Spi95] Jeremy P. Spinrad  “Nonredundant 1’s in Gamma-Free Matrices”  In _SIAM J. Discret. Math._ 8.2, 1995, pp. 251–257  DOI: 10.1137/S0895480191197210
  * [Spi03] Jeremy P. Spinrad  “Efficient graph representations” 19, Fields Institute monographs  American Mathematical Society, 2003  URL: http://www.ams.org/bookstore-getitem/item=fim-19
  * [Yao81] Andrew Chi-Chih Yao  “Should Tables Be Sorted?”  In _J. ACM_ 28.3, 1981, pp. 615–628  DOI: 10.1145/322261.322274
  * [Yin16] Yitong Yin  “Simple Average-Case Lower Bounds for Approximate Near-Neighbor from Isoperimetric Inequalities”  In _43rd International Colloquium on Automata, Languages, and Programming, ICALP 2016, July 11-15, 2016, Rome, Italy_ 55, LIPIcs  Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2016, pp. 84:1–84:13  DOI: 10.4230/LIPICS.ICALP.2016.84
  * [Zha+94] Peisen Zhang, Eric A. Schon, Stuart G. Fischer, Eftihia Cayanis, Janie Weiss, Susan Kistler and Philip E. Bourne  “An algorithm based on graph theory for the assembly of contigs in physical mapping of DNA”  In _Comput. Appl. Biosci._ 10.3, 1994, pp. 309–317  DOI: 10.1093/BIOINFORMATICS/10.3.309

##  Appendix A Data structure for $\operatorname{\mathsf{adj}}{}$ query in the
cell-probe model

In this section, we give a data structure for $\operatorname{\mathsf{adj}}{}$
queries on interval graph with $n$ vertices in the cell-probe model. We use
the following lemma from [DPT10] which gives us more control over the mapping
than their main theorem.

######  Lemma 19 ([DPT10, Lemma 4]).

Let $X,Y\leq 2^{w}$. Then for some values $M$ and $S$ we can injectively map
$(x,y)\in[X]\times[Y]$ to $(m,s)\in[2^{M}]\times[S]$ with the following
properties:

  * •

$S$ and $M$ are chosen as functions of $X$ and $Y$ but satisfy
$S=O(\sqrt{X})$, $2^{M}=O(Y\sqrt{X})$.

  * •

The map can be evaluated in time $O(1)$.

  * •

$x$ can be decoded from $m$ and $s$ in $O(1)$ time.

  * •

$y$ can be decoded from $m$ alone in $O(1)$ time.

  * •

The redundancy is $(M+\log S)-(\log X+\log Y)=O(1/\sqrt{X})$.

The details of this can be found in [DPT10].

######  Theorem 20.

There is a cell-probe data structure for $n$-vertex interval graphs in
universal interval representation, supporting adjacency query in constant time
using $\log(n!)+O(1)$ bits of space.

###### Proof.

Let $x_{i}$ be the length of the interval whose left endpoint is $i$, which is
from $[n-i+1]$. We then encode the length of each interval iteratively using
Lemma 19. In other words, we would like to encode an array
$(x_{1},\dots,x_{n})\in[n]\times[n-1]\times\dots\times[1]$.

We start with grouping the numbers in the following way, so that each group
can be viewed as an element from a universe of size $\Theta(n^{2})$. For this,
the first group consists of the first two numbers, so the first group is of
universe $[n]\times[n-1]$ of size $\approx n^{2}$. We iteratively group the
elements to reach universes of size $\approx n^{2}$, and some groups may
consist of more than two elements as the size of the universe of the element
is decreasing. At the end of the grouping procedure, we obtain an array of
groups such that each group is from a universe of size $\approx n^{2}$, except
the last group. Note that each size of the universe of $i$-th group can be
computed without knowing anything about the input, as it is a function of $i$
and $n$. Also note that the number of the groups, denoted by $n^{\prime}$, is
a function of $n$.

We encode each group trivially by the multiplication, i.e.,
$(x_{i},\dots,x_{j})$ is written as a number
$\sum_{k=i}^{j}(x_{k}\prod_{l=k+1}^{j}(n-l+1))$,444We let
$\prod_{l=j+1}^{j}(n-l+1)=1$. resulting in $y_{i^{\prime}}$, so that we can
fully decode $(x_{i},\dots,x_{j})$ from $y_{i^{\prime}}$. From now on, given
the grouping, we want to encode an array $(y_{1},\dots,y_{n^{\prime}})$ such
that each element is from a universe of size $\Theta(n^{2})$. First trivially
apply the lemma (Lemma 19) with $(x,y)=(y_{0},y_{1})$, where $y_{0}\in[1]$ is
a dummy element, obtain $(m_{1},s_{1})$. Then we iteratively apply the lemma
for $i\in[2,n^{\prime}]$ with $(x,y)=(s_{i-1},y_{i})$ and obtain
$(m_{i},s_{i})$. We write down memory block $m_{i}$ for $i\in[n^{\prime}]$ one
by one and, finally, $s_{n^{\prime}}$.

Let us now analyze the redundancy for $\sum_{i<n^{\prime}}M_{i}$. The
redundancy is given by $\sum_{i}O(1/\sqrt{X_{i}})$, where
$X_{i}=\Theta(n^{2})$ (except $X_{n^{\prime}}$) is the size of the universe of
aforesaid $y_{i}$ determined by the lemma. We can see this sum as
$n^{\prime}\cdot O(1/\sqrt{n^{2}})=O(n^{\prime}/n)=O(1)$ as $n^{\prime}\leq
n$. We use $\lceil\log S_{n^{\prime}}\rceil$ bits to write down
$s_{n^{\prime}}$, where $[S_{n^{\prime}}]$ is the universe of
$s_{n^{\prime}}$, that incurs $1$ bits of redundancy.

Now we want to answer a query. To reconstruct the length of interval $i$, we
simulate the compression algorithm to find the sizes of the groups and the
$M_{i}$s. As the sizes of the groups and the $M_{i}$’s are independent of the
actual bits stored, this does not require any knowledge about the input and
can be done for free in the cell-probe model. We then retrieve the memory
block $m_{i^{\prime}}$ which maintains the $i$-th interval length since
$\sum_{i<i^{\prime}}M_{i}$ is known. We also reconstruct the spill
$s_{i^{\prime}}$ from the bits $m_{i^{\prime}+1}$ ($s_{n^{\prime}}$, if
$i^{\prime}=n^{\prime}$) which by Lemma 19 can be reconstructed. From this we
have the corresponding tuple $(m_{i^{\prime}},s_{i^{\prime}})$. From this we
can decode the tuple $y_{i^{\prime\prime}}$ which encodes
$(x_{j},\dots,x_{i},\dots,x_{k})$. As the tuple is encoded trivially, we can
retrieve the actual number $x_{i}$. This shows a time complexity of $O(1)$
probes in total, as retrieving $m_{i^{\prime}},m_{i^{\prime}+1}$ takes $O(1)$
probes. As for correctness, knowing the length of interval $i$ allows us to
know $\operatorname{\mathsf{adj}}(i,\cdot)$. ∎