#  On the Problem of Undirected st-connectivity

Shilun Li
Dept. of Computer Science
Stanford University
<EMAIL_ADDRESS>
&Alex Lee
Dept. of Computer Science
Stanford University
<EMAIL_ADDRESS>

###### Abstract

In this paper, we discuss an algorithm for the problem of undirected st-
connectivity that is deterministic and log-space, namely that of Reingold
within his 2008 paper "Undirected Connectivity in Log-Space" Rei (08). We
further present a separate proof by Rozenman and Vadhan of
$\textsc{Ustconn}\in\textbf{L}$ RV (05) and discuss its similarity with
Reingold’s proof. Undirected st-connectively is known to be complete for the
complexity class SL–problems solvable by symmetric, non-deterministic, log-
space algorithms. Likewise, by Aleliunas et. al. AKL+ (79), it is known that
undirected st-connectivity is within the RL complexity class, problems
solvable by randomized (probabilistic) Turing machines with one-sided error in
logarithmic space and polynomial time. Finally, our paper also shows that
undirected st-connectivity is within the L complexity class, problems solvable
by deterministic Turing machines in logarithmic space. Leading from this
result, we shall explain why $\textbf{SL}=\textbf{L}$ and discuss why is it
believed that $\textbf{RL}=\textbf{L}$.

##  1 Introduction

In this report, we shall prove that the problem Ustconn, or st-connectivity on
undirected graphs, can be solved with a log-space algorithm. We then explore
the implications of such a result.

We can define the problem of st-connectivity by considering a graph $G$ and
two vertices $s$ and $t$ in $G$. The st-connectivity problem answers whether
or not the two vertices $s$ and $t$ are connected with each other by a path in
$G$. Similarly, the Ustconn problem decides the Stconn problem, but on a graph
$G$ that is specified to be undirected. (In this case, Ustconn is a special
case of Stconn and all algorithms that solve Stconn would be able to solve
Ustconn.) The problem of connectivity is one of the most fundamental problems
within graph theory, and algorithms to solve Stconn and Ustconn has been used
to construct more complex graph algorithms. Indeed, a solution to the Stconn
or Ustconn problem within a certain complexity class would similarly imply a
solution within the complexity class for a much larger body of computational
problems.

The time complexity of Ustconn has been well understood and solved: it is
clear to see that the minimum time complexity must be linear (as the length of
a path from $s$ to $t$ would be linear), and it is also clear that such a time
complexity would be achievable by depth-first search (DFS) or breadth-first
search (BFS).

Most recent study of the Ustconn problem thus, revolves around its space
complexity. It is clear that the space complexity of Ustconn must be at least
$\log$ space, which is the space required to store any $O(n)$ sized variables
within the problem. In 1970, Savistch provided a $\log^{2}{n}$ space
complexity solution to the Stconn (and Ustconn). A randomized algorithm of
log-space complexity was also developed in 1979 by Aleliunas, Karp, Lipton,
Lovasz, and Rackoff AKL+ (79). Following the result, work has been done on
derandomizing the randomized algorithm in hopes of creating a deterministic
algorithm with decreasing space complexity. In 1992, Nisan, Szemeredi and
Wigderson presented an algorithm of $\log^{1.5}$ space NSW (92). In 1999,
Armoni, et, al showed that Ustconn can be solved by an algorithm in
$\log^{\frac{4}{3}}$ space ATSWZ (00). In 2005, Trifonov developed an
algorithm of $\log{n}\log\log{n}$ space for Ustconn Tri (05). Finally, in
2008, Omer Reingold presented a deterministic algorithm that solves Ustconn in
log-space complexity Rei (08).

We shall begin our paper by presenting the result of $\textsc{Ustconn}\in L$
through Omer Reingold’s method in his paper "Undirected Connectivity in Log-
Space". Rei (08). More specifically, we shall begin by explaining expander
graphs and some transformations used to convert any graph to an expander
graph. We shall then show that these transformations can be performed in log
space and that connectivity can be computed from these expander graphs in log
space too. This would prove that $\textsc{Ustconn}\in\textbf{L}$.

We would then present a separate proof from Rozenman and Vadhan of
$\textsc{Ustconn}\in\textbf{L}$ and discuss its similarity to Reingold’s
proof.

Finally, we shall explore the implications of this result on the relations
between the complexity classes of L, SL, and RL. L refers to problems solvable
by a deterministic log space Turing machine, SL refers to problems solvable by
symmetric log space Turing machines, and RL refers to problems solvable by
probabilistic log space Turing machines with one sided error. These three
complexity classes are closely tied to Ustconn and we shall show that
$\textbf{SL}=\textbf{L}$ and discuss why it is believed that
$\textbf{RL}=\textbf{L}$.

##  2 Preliminaries

In this section, we will introduce some properties of graphs using adjacency
matrix representation, along with procedures such as graph powering.

###  2.1 Graph Adjacency Matrix

For any graph $G$, common representations include adjacency list, adjacency
matrix, and incidence matrix. There exist log-space algorithms which
transforms between the common representations, so the problem of Ustconn does
not rely on the input graph representations. In this paper, we will use the
adjacency list representation.

######  Definition 2.1.

The adjacency matrix $A$ of a graph $G=(V,E)$ is the $|V|\times|V|$ matrix
such that the entry $(u,v)$ of $A$ written $A_{u,v}$ is equal to the number of
number of edges from vertex $u$ to vertex $v$ in $G$.

We allow $G$ to contain self loops and parallel edges.

######  Definition 2.2.

For a graph $G=(V,E)$ with adjacency matrix $A$. $G$ is undirected if $A$ is
symmetric, where we have $A=A^{T}$. An undirected graph $G$ is D-regular if
there are exactly $D$ edges incident to every vertex, equivalently,
$\sum_{v\in V}A_{u,v}=D$ for all $u\in V$.

For any undirected D-regular graph $G$ with $N$ vertices, let us label each
outgoing edge of every vertex of $G$ by a number from 1 to D in a fixed way.
Then we define the rotation map of $G$ as follows:

######  Definition 2.3.

For an undirected D-regular graph $G$ with $N$ vertices, let the rotation map
$\text{Rot}_{G}$ be a permutation of $[N]\times[D]$ defined by
$\text{Rot}_{G}(v,i)=(w,j)$ if edge $i$ from $v$ leads to $w$ and is the same
edge as edge $j$ of $w$.

The rotation map defines how the vertices and edges of $G$ are labeled. The
rotation map will play a crucial role in transforming any undirected graph $G$
into a regular graph. The adjacency matrix can be expressed by the rotation
map in the following way:

$A_{u,v}=|\\{(i,j)\in[D]^{2}:\text{Rot}_{G}(u,i)=(v,j)\\}|$ (1)

To solve Ustconn, we would like the graph to be highly connected but at the
same time sparse so that the diameter is small. We call such highly connected
sparse graphs expanders. We will define expanders using properties of its
adjacency matrix.

######  Proposition 2.1.

For an undirected D-regular graph $G$ with $N\times N$ adjacency matrix $A$,
$A$ is diagonalizable with eigenvalues $\lambda_{1}\geq...\geq\lambda_{N}$.
Furthermore, $\lambda_{1}=D$ and $\lambda_{N}\geq-D$.

###### Proof.

The first part of the statement follows from spectral theorem for symmetric
matrices. For the second part of the proposition, given any eigenvector
$\lambda$ of $A$ with eigenvector $v=(v_{1},...,v_{n})$, consider the index
$k$ such that $|v_{k}|$ achieves the maximum among all $v_{1},...,v_{i}$. Now
since $Av=\lambda v$, the $k^{th}$ component satisfies

$|(Av)_{k}|=|\sum_{i=1}^{n}A_{k,i}v_{i}|\leq\sum_{i=1}^{n}|v_{k}|A_{k,i}=D|v_{k}|.$

But we also have $|(Av)_{k}|=|\lambda||v_{k}|$. So $|\lambda|\leq D$ for any
eigenvalue $\lambda$ of $A$. Now note that for the vector $v=(1,...,1)^{T}$,
we have $Av=Dv$. So $v$ is a eigenvector of $A$ with eigenvalue $D$. Thus
$\lambda_{1}=D$ and $\lambda_{N}\geq-D$ as desired. ∎

Now, let us define the normalized adjacency matrix $M$ of an undirected
D-regular graph $G$ as the adjacency matrix divided by $D$.

######  Definition 2.4.

For any graph $G$, let $\lambda(G)$ be the second largest eigenvalue of the
normalized adjacency matrix. $G$ is an expander graph if
$\lambda(G)\leq\frac{1}{2}$. $G$ is an $(N,D,\lambda)$-graph if it is
undirected D-regular with $N$ vertices and $\lambda(G)<\lambda$.

The second largest eigenvalue of $G$ captures its expansion properties. It is
shown by AlonAlo (86) that second-eigenvalue expansion is equivalent to the
standard vertex expansion. In particular, we have the following

######  Proposition 2.2.

Fix any fixed $\lambda<1$, for any $(N,D,\lambda)$-graph $G_{N}$. For any two
vertices $s,t\in G_{G}$, there exists a path of length $O(\log N)$.

###### Proof.

By the result of AlonAlo (86), for any $\lambda<1$, there exist $\epsilon>0$
such that for any $(N,D,\lambda)$-graph $G_{N}$ and any set $S$ of vertices of
$G_{N}$ such that $|S|\geq\frac{N}{2}$, we have $|\partial S|\geq\epsilon|S|$
where $\partial S=\\{(u,v)\in E(G_{N}):u\in S,v\in V(G_{N})\setminus S\\}$.
Now for any two vertices $s,t\in G_{N}$, for some $l=O(\log N)$ with constant
only depending on $\epsilon$, since the edge expansion factor is at least
$\epsilon$, both $s$ and $t$ can have more than $\frac{N}{2}$ vertices of at
most distance $l$. Then there exist a vertex $v$ within distance $l$ from both
$s$ and $t$. Thus there exist a path of length $2l=O(\log N)$ from $s$ to $t$.
∎

One may notice that the vertex expansion property of an undirected
$(N,D,\lambda)$-graphs with $\lambda<1$ implies it is connected. We can also
directly see this as for any undirected D-regular graph with multiple
connected components, each component will contribute an orthogonal eigenvector
of the normalized adjacency matrix with eigenvalue 1 via the indicator of that
component. Thus the graph will have the second largest eigenvalue of
normalized adjacency matrix being 1 if it has more than one connected
component. With the result above, we can now solve the undirected st-
connectivity problem for constant-degree expanders using log-space.

######  Lemma 2.3.

For any fixed $\lambda<1$, there exist a space $O(\log D\log N)$ algorithm
$\mathcal{A}_{\lambda}$ such that on an input of an undirected D-regular graph
$G$ with $N$ vertices and two vertices $s,t\in G$:

  * •

Outputs "connected" only if $s$ and $t$ are connected in $G$.

  * •

If $s$ and $t$ are in the same connected component which is a
$(N^{\prime},D,\lambda)$-graph, then the algorithm outputs "connected".

###### Proof.

Consider the algorithm of simply enumerating all paths of length $l$ from $s$,
where we take $l=O(\log N)$ given by Proposition2.2, with the constant only
depending on $\lambda$. Such enumeration can be done via the ordering of edges
of each vertex.
The algorithm outputs "connected" if there is a path of at most length $l$ to
$t$. The algorithm runs in $O(l\log D)=O(\log D\log N)$ space as each edge of
a vertex requires $\log D$ space and each path of length $l$ can be stored in
$O(\log N)$ space. The algorithm satisfies the requirements stated above due
to Proposition2.2. ∎

By the explicit construction given by Alon and Roichman AR (94) using Cayley
graph of the group $\mathbb{F}_{2}^{m}$ which is $m$ dimensional vector space
of the field $\mathbb{F}_{2}$, we have existence of expander graphs with
desired parameters.

######  Proposition 2.4.

There exist an undirected $D_{0}$-regular
$((D_{0})^{16},D_{0},\frac{1}{2})$-graph for some $D_{0}$.

The value $1-\lambda(G)$ is called the spectral gap of a graph. We have shown
that for a disconnected graph, the spectral gap is 0. Due to result by Alon AS
(00), the converse holds for non-bipartite graphs:

######  Proposition 2.5 (Alon).

For every D-regular connected non-bipartite graph $G$ with $N$ vertices, the
spectral gap is at least $\frac{1}{DN^{2}}$. Equivalently, $\lambda(G)\leq
1-\frac{1}{DN^{2}}$.

###### Proof.

This is Theorem 1.1 in AS (00). ∎

###  2.2 Graph Powering and Zig-zag Products

We will now introduce operations of graphs to change its degree and spectral
gap, i.e. its expansion properties. We will first introduce graph powering,
which reduces its second eigenvalue and increases its spectral gap, but also
increases its degree. We will then define the zig-zag product of two graphs,
which was first introduced by Reingold, Vadhan and Wigderson RVW (00). This
operation reduces the degree of a graph without significantly varying the
spectral gap.

Recall that the labeling of edges of an undirected D-regular graph is given by
the rotation map. Equivalently, the graph is defined by the rotation map. So
let us define graph powering via rotation maps.

######  Definition 2.5.

For a undirected $D$-regular graph $G$ with $N$ vertices given by the rotation
map $\text{Rot}_{G}$, the $t^{th}$ power of of $G$ is the $D^{t}$-regular
graph $G^{t}$ defined by the rotation map

$\text{Rot}_{G^{t}}(v_{0},(a_{1},...,a_{t}))=(v_{t},(b_{t},...,b_{1}))$

for any $v_{0},v_{t}\in[N]$ and $a_{1},...,a_{t}\in[D]$ where
$b_{1},...,b_{t}$ are computed by
$(v_{i},b_{i})=\text{Rot}_{G}(v_{i-1},a_{i})$.

One can view the vector $(a_{1},...,a_{t})\in[D^{t}]$ as a path from $v_{0}$
to $v_{t}$ where each $a_{i}$ is the action of taking edge $a_{i}$ of the
current vertex during traversal of the path. The vector
$(b_{t},...,b_{1})\in[D^{t}]$ is simply the same path backwards, starting from
$v_{t}$ and ending in $v_{0}$. This definition coincides with the usual
definition of graph powering where two vertices is adjacent in the $t^{th}$
power if there is a path of length $t$ in the original graph.

######  Proposition 2.6.

The normalized adjacency matrix of $G^{t}$ is given by $M^{t}$ where $M$ is
the normalized adjacency matrix of $G$. Consequently, if $G$ is a
$(N,D,\lambda)$-graph, then $G^{t}$ is a $(N,D^{t},\lambda^{t})$-graph.

###### Proof.

From the above discussion, for any two vertices $v_{0},v_{t}\in G^{t}$, the
number of edges between $v_{0}$ and $v_{t}$ in $G^{t}$ is equal to the number
of length $t$ paths from $v_{0}$ to $v_{t}$, where paths are defined using
edges instead of vertices. The number of paths from $v_{0}$ to $v_{t}$ is in
turn equal to $(A^{t})_{v_{0},v_{t}}$, where $A$ is the adjacency matrix of
$G$. So $A^{t}$ is the adjacency matrix of $G^{t}$. Thus the normalized
adjacency matrix of $G^{t}$ is given by $D^{-t}A^{t}=M^{t}$ where $M$ is the
normalized adjacency matrix of $G$.
If $G$ is a $(N,D,\lambda)$-graph with normalized adjacency matrix $M$. Since
the normalized adjacency matrix of $G^{t}$ is given by $M^{t}$, we have
$\lambda(G^{t})=\lambda(G)^{t}$. Thus $G^{t}$ is a
$(N,D^{t},\lambda^{t})$-graph. ∎

For a $(N,D,\lambda)$-graph, powering increases the spectral gap
exponentially, but the degree of the graph also increases exponentially. On
the other hand, the zig-zag product reduces the degree of the graph but
remains the spectral gap nearly unchanged.

######  Definition 2.6.

Let $G$ be a D-regular graph on $[N]$ with rotation map $\text{Rot}_{G}$, $H$
be a d-regular graph on $[D]$ with rotation map $\text{Rot}_{H}$. Then their
zig-zag product $G\mathbin{\raisebox{0.86108pt}{ $\bigcirc${\rm z}\hskip
1.49994pt}}H$ is a $d^{2}$-regular graph on $[N]\times[D]$ with rotation map
$\text{Rot}_{G\mathbin{\raisebox{0.60275pt}{ $\bigcirc${\rm z}\hskip
1.04996pt}}H}$ defined by:

$\text{Rot}_{G\mathbin{\raisebox{0.60275pt}{ $\bigcirc${\rm z}\hskip
1.04996pt}}H}((v,a),(i,j))=((w,b),(j^{\prime},i^{\prime}))$

where $w,b,j^{\prime},i^{\prime}$ satisfies: there exist
$a^{\prime},b^{\prime}\in[N]$ such that

  * •

$\text{Rot}_{H}(a,i)=(a^{\prime},i^{\prime})$

  * •

$\text{Rot}_{G}(v,a^{\prime})=(w,b^{\prime})$

  * •

$\text{Rot}_{H}(b^{\prime},j)=(b,j^{\prime})$

Reingold et al. showed that this product is well defined and
$\lambda(G\mathbin{\raisebox{0.86108pt}{ $\bigcirc${\rm z}\hskip
1.49994pt}}H)$ is bounded as a function of $\lambda(G)$ and $\lambda(H)$.RVW
(00) This product replaces each vertex of $G$ via a copy of $H$. The edges of
the product correspond to length 3 paths with two edges in $H$ and the middle
edge in $G$. See Figure 1 below:

Figure 1: On the left hand side is the edge $((v,a),(i,j))$ in
$G\mathbin{\raisebox{0.77498pt}{ $\bigcirc${\rm z}\hskip 1.34995pt}}H$.
$H_{v}$ is the copy of $H$ for vertex $v$ and $H_{w}$ is the copy of $H$ for
vertex $w$. The edge $((v,a),(i,j))$ correspond a length 3 path composed by
$(a,i)$ in $H_{v}$, $(v,a^{\prime})$ in $G$ and $(b^{\prime},j)$ in $H_{w}$.
The rotation map of the edge correspond to the same path traversing backwards.
On the right hand side is the projection of the path on $G$, which correspond
to the middle edge of the length 3 path.

To reduce the degree of the graph $G$ while remaining the spectral gap, we
want $d$, the degree of $H$ to be much smaller than $D=deg(G)$ so that
$d^{2}=deg(G\mathbin{\raisebox{0.86108pt}{ $\bigcirc${\rm z}\hskip
1.49994pt}}H)$ is smaller than $D$. We also want
$1-\lambda(G\mathbin{\raisebox{0.86108pt}{ $\bigcirc${\rm z}\hskip
1.49994pt}}H)>k(1-\lambda(G))$ for some constant $k\in(0,1)$ independent of
$G$. These estimates on the spectral gap of the zig-zag product are given by
Reingold et al. in RVW (00).

######  Theorem 2.7 (Reingold).

If $G$ is an $(N,D,\lambda)$-graph and $H$ is a $(D,d,\alpha)$-graph, then
$G\mathbin{\raisebox{0.86108pt}{ $\bigcirc${\rm z}\hskip 1.49994pt}}H$ is an
$(ND,d^{2},f(\lambda,\alpha))$ graph where

$f(\lambda,\alpha)=\frac{1}{2}(1-\alpha^{2})\lambda+\frac{1}{2}\sqrt{(1-\alpha^{2})^{2}\lambda^{2}+4\alpha^{2}}$

###### Proof.

This is Theorem 4.3 in RVW (00). ∎

######  Corollary 2.7.1.

If $G$ is an $(N,D,\lambda)$-graph and $H$ is a $(D,d,\alpha)$-graph, then

$1-\lambda(G\mathbin{\raisebox{0.86108pt}{ $\bigcirc${\rm z}\hskip
1.49994pt}}H)\geq\frac{1}{2}(1-\alpha^{2})(1-\lambda).$

###### Proof.

Since $\lambda\leq 1$, we have

$\frac{1}{2}\sqrt{(1-\alpha^{2})^{2}\lambda^{2}+4\alpha^{2}}\leq\frac{1}{2}\sqrt{(1-\alpha^{2})^{2}+4\alpha^{2}}=1-\frac{1}{2}(1-\alpha^{2}).$

This Corollary is then a direct consequence of Theorem 2.7. ∎

##  3 Expander Transforms of Graphs

In this section, we will introduce the Main Transform given by ReingoldRei
(08) which uses log-space to transform each connected component of a graph
into an expander. This is the main part of the log-space algorithm for
Ustconn.

######  Definition 3.1.

For a $D^{16}$-regular graph $G$ on $[N]$ and $D$-regular graph $H$ on
$[D^{16}]$. Then let the transformation $\mathcal{T}$ outputs the rotation map
of $G_{l}$ where $G_{l}$ is defined recursively by:

$G_{i}=(G_{i-1}\mathbin{\raisebox{0.86108pt}{ $\bigcirc${\rm z}\hskip
1.49994pt}}H)^{8},\quad i=1,...,l$

where $G_{0}=G$ and $l=2\left\lceil\log DN^{2}\right\rceil$. We will denote
$\mathcal{T}_{i}(G,H)=G_{i}$ and $\mathcal{T}(G,H)=G_{l}$.

From the properties of zig-zag product and graph powering, the graph $G_{i}$
is a $D^{16}$-regular graph over $[N]\times([D^{16}])^{i}$. If $D$ is
constant, then $l=O(\log N)$ and $G_{l}$ has $poly(N)$ vertices. We will first
show that this transformation can transform $G$ into an expander.

######  Lemma 3.1.

For a $D^{16}$-regular connected and non-bipartite graph $G$ over $[N]$, and
$(D^{16},D,\lambda)$ graph $H$ with $\lambda\leq\frac{1}{2}$, we have
$\lambda(\mathcal{T}(G,H))\leq\frac{1}{2}$.

###### Proof.

Since $G$ is connected and non-bipartite, by Proposition 2.7,

$\lambda(G_{0})\leq 1-\frac{1}{DN^{2}}.$

By Corollary 2.7.1, as $\lambda(H)\leq\frac{1}{2}$, we have

$\lambda(G_{i-1}\mathbin{\raisebox{0.86108pt}{ $\bigcirc${\rm z}\hskip
1.49994pt}}H)\leq
1-\frac{3}{8}(1-\lambda(G_{i-1}))<1-\frac{1}{3}(1-\lambda(G_{i-1})),\quad
i=1,...,l.$

So by Proposition 2.6 we have

$\lambda(G_{i})=\lambda((G_{i-1}\mathbin{\raisebox{0.86108pt}{ $\bigcirc${\rm
z}\hskip 1.49994pt}}H)^{8})<(1-\frac{1}{3}(1-\lambda(G_{i-1})))^{8}.$

When $\lambda(G_{i-1})\leq\frac{1}{2}$, we have
$\lambda(G_{i})<(\frac{5}{6})^{8}<\frac{1}{2}$. If we have
$\lambda(G_{i})\leq\frac{1}{2}$ for some $i=0,...,l$, then be induction, we
would have $\lambda(\mathcal{T}(G,H))=\lambda(G_{l})\leq\frac{1}{2}$ as
desired. So let us suppose otherwise, $\lambda(G_{i})>\frac{1}{2}$ for all i.
Then it is easy to show
$\lambda(G_{i})=(1-\frac{1}{3}(1-\lambda(G_{i-1})))^{8}\leq\lambda(G_{i-1})^{2}$.
So

$\lambda(G_{l})\leq(1-\frac{1}{DN^{2}})^{2^{l}}.$

Since $(1-\frac{1}{x})^{x}<e^{-1}$ for all $x\geq 1$, we have

$\lambda(G_{l})\leq(1-\frac{1}{DN^{2}})^{2^{l}}\leq e^{-2}<\frac{1}{2}.$

So $\lambda(\mathcal{T}(G,H))\leq\frac{1}{2}$. ∎

While the analysis in the previous lemma assumes $G$ is connected and non-
bipartite, we will extend this analysis of $\mathcal{T}$ to any undirected
graph $G$. Note that zig-zag product $G\mathbin{\raisebox{0.86108pt}{
$\bigcirc${\rm z}\hskip 1.49994pt}}H$ and graph powering operates separately
on each connected component, $\mathcal{T}(G,H)$ operates on each connected
component of $G$ separately. Let define the restriction of a graph:

######  Definition 3.2.

For any graph $G$ and subset $S$ of its vertices $V$. Let $G|_{S}$ be the the
subgraph of $G$ induced by $S$, which has vertices $S$ and edges arising from
edges in $G$ which has both endpoints in $S$.

Note that $S$ is a connected component of $G$ if $G|_{S}$ is connected and $S$
is disconnected to vertices of $V\setminus S$. Now let us show that
restriction to a connected component of $G$ commutes with taking the
transformation $\mathcal{T}$. A crucial observation is that both
$\mathcal{T}_{i}(G|_{S},H)$ and $\mathcal{T}_{i}(G,H)$ are $D^{16}$-regular,
with the same vertices. In addition, $\mathcal{T}_{i}(G|_{S},H)$ is a subgraph
of $\mathcal{T}_{i}(G,H)$. So we should have
$\mathcal{T}(G|_{S},H)=\mathcal{T}(G,H)|_{S\times([D^{16}])^{l}}$. An formal
proof using induction is given by Reingold which makes use of this
observation.

######  Lemma 3.2.

For a $D^{16}$-regular graph $G$ on $[N]$ and $D$-regular graph $H$ on
$[D^{16}]$. If $S$ is a connected component of $G$, then

$\mathcal{T}(G|_{S},H)=\mathcal{T}(G,H)|_{S\times([D^{16}])^{l}}.$

###### Proof.

See Lemma 3.3 of Rei (08). ∎

Finally, we will show that $\mathcal{T}$ can be computed in log-space when $D$
is constant. This is essentially due to the fact that during each step of the
inductive calculation of $\mathcal{T}_{i}(G,H)$, only constant addition amount
of memory is needed. We will shot the space complexity of $\mathcal{T}$ in the
follow lemma:

######  Lemma 3.3.

For any constant $D$. Consider a $D^{16}$-regular graph $G$ over $[N]$ and
$D$-regular graph $H$ over $[D^{16}]$, then $\mathcal{T}(G,H)$ can be computed
in $\log(N)$ space. Equivalently, there exist an $O(\log N)$ space algorithm
$\mathcal{A_{T}}$ on input $(G,H,(v,a))$ outputs
$\text{Rot}_{\mathcal{T}(G,H)}(v,a)$ where $v\in[N]\times([D^{16}])^{l}$ and
$a\in[D^{16}]$.

###### Proof.

The algorithm $\mathcal{A_{T}}$ will first allocate variables $v\in[N]$ and
$a_{0},...,a_{l}\in[D^{16}]$. We will denote each $a_{i}=k_{i,1}...k_{i,16}$
where $k\in[D]$ correspond to edge labels of $H$. Now on input
$(G,H,(v_{in},a_{in}))$, the algorithm will first copy
$v_{in}=(\hat{v},\hat{a}_{0},...,\hat{a}_{l-1})\in[N]\times[D^{16}]^{l}$ into
the allocated variables $v,a_{0},...,a_{l-1}$ and
$a_{in}=\hat{a}_{l}\in[D^{16}]$ into $a_{l}$. These variables will store the
the output of $\text{Rot}_{G_{i}}$ on $\hat{v},\hat{a}_{0},...,\hat{a}_{i}$
where $G_{i}=\mathcal{T}_{i}(G,H)$. We will recursively update the variables
$v,a_{0},...,a_{l}$ such that after the $i^{th}$ iteration, the variables
$v,a_{0},...,a_{i}$ will store the result of
$\text{Rot}_{G_{i}}((\hat{v},\hat{a}_{0},...,\hat{a}_{i-1}),\hat{a}_{i})$. For
the base case, when $i=0$, $G_{0}=G$, so we can search in the input tape for
the edge $(\hat{v},\hat{a}_{0})$ and write down
$\text{Rot}_{G_{0}}(\hat{v},\hat{a}_{0})$ in $v,a_{0}$. Now for $i=1,...,l$,
we evaluate
$\text{Rot}_{G_{i}}((\hat{v},\hat{a}_{0},...,\hat{a}_{i-1}),\hat{a}_{i})$ via
the following procedure:

For j = 1 to 16:

  * •

Set $a_{i-1},k_{i,j}=\text{Rot}_{H}(a_{i-1},k_{i,j})$

  * •

If $j$ is odd, recursively compute and set
$v,a_{0},...,a_{i-1}=\text{Rot}_{G_{i-1}}((v,a_{0},...,a_{i-2}),a_{i-1})$.

  * •

If $j=16$, reverse the order of the labels in $a_{i}$: set
$k_{i,1},...,k_{i,16}=k_{i,16},...,k_{i,1}$

The first two operations correspond to finding a a path of length eight on
$G_{i-1}\mathbin{\raisebox{0.86108pt}{ $\bigcirc${\rm z}\hskip 1.49994pt}}H$,
which is a step on $(G_{i-1}\mathbin{\raisebox{0.86108pt}{ $\bigcirc${\rm
z}\hskip 1.49994pt}}H)^{8}$. The third bullet reverses the order of labels of
$a_{i}$ to fit the definition of zig-zag and powering. The correctness of the
induction follows from the definition of zig-zag product and powering. Thus
the correctness of $\mathcal{A_{T}}$ follows from the inductive definition of
$\mathcal{T}$.
Now note that within each level of the recursion tree, there are at most $16$
recursive calls, and the recursion tree has depth $l+1=O(\log N)$. So we can
maintain the recursive calls with $O(\log N)$ space. Furthermore, the
operations of evaluating $\text{Rot}_{G}$, $\text{Rot}_{H}$ and reversing
labels can be done in $O(\log N)$ space. The space required to store the
variables in $O(\log N)$ as $v$ requires $\log N$ space and $a_{i}$ can be
stored in constant space. Thus the total space needed to store $a_{i}$’s is
$O((l+1)*\log 16)=O(\log N)$. Therefore the algorithm $\mathcal{A_{T}}$ runs
in $O(\log N)$ space. ∎

##  4 $\textsc{Ustconn}\in\textbf{L}$

In this section, we will provide an log-space algorithm for Ustconn using the
by transforming the input graph $G$ into an appropriate expander.

######  Theorem 4.1.

For any undirected graph $G$ over $[N]$, there exists an $O(\log N)$ space
algorithm $\mathcal{A}_{con}$ which computes $\textsc{Ustconn}(G,s,t)$ where
$s,t\in[N]$.

###### Proof.

As we can transform between common representations of graphs in log-space,
without loss of generality we can assume $G$ is given via the adjacency matrix
representation.
By Proposition 2.4, for some constant $D_{0}$, there exists a
$((D_{0})^{16},D_{0},\frac{1}{2})$-graph $H$. Let us hard-code the rotation
map of $H$ to the memory of $\mathcal{A}_{con}$. This takes only constant
memory.
Now we would like to transform $G$ into $D^{16}$-regular graph $G_{reg}$
(which is defined by its rotation map) so that we can apply $\mathcal{T}$ on
$(G_{reg},H)$. Let $G_{reg}$ be the graph constructed by replacing each vertex
of $G$ with with a cycle of length N, and there is an edge between $(v,w)$ and
$(w,v)$ in $G_{reg}$ if there is an edge between $v$ and $w$ in $G$. Self
loops are added so that the degree of each vertex is $D_{0}^{16}$. The
rotation map
$\text{Rot}_{G_{reg}}:([N])^{2}\times[D_{0}^{16}]\rightarrow([N])^{2}\times[D_{0}^{16}]$
is given by:

$\text{Rot}_{G_{reg}}((v,w),i)=\begin{cases}((v,(w+1)\mod N),2),\quad i=1\\\
((v,(w-1)\mod N),1),\quad i=2\\\ ((w,v),3),\quad i=3\text{ and there is an
edge between v and w in G}\\\ ((v,w),3),\quad i=3\text{ and there is an edge
between v and w in G}\\\ ((v,w),i),\quad i=4,...,16\\\ \end{cases}.$

The first two cases are the edges of the cycle of length $N$ for vertex $v$.
The last case are the self loops so that $G_{reg}$ is $D_{0}^{16}$ regular.
Also note that every vertex of $G_{reg}$ has self loops, so $G_{reg}$ is non-
bipartite. It is easy to see that $v$ and $w$ are in the same connected
component of $G$ if and only if $v\times[N]$ and $w\times[N]$ are in the same
connected component of $G_{reg}$. This in turn is equivalent to $(v,1)$ and
$(w,1)$ are connected in $G_{reg}$.
Now let $G_{exp}=\mathcal{T}(G_{reg},H)$, where $l=O(\log N)$ defined in
Definition 3.1. Let $S$ be the connected component of $s$ in $G$. Then
$S\times[N]$ is a connected component of $G_{reg}$ where
$G_{reg}|_{S\times[N]}$ is non-bipartite $D_{0}^{16}$-regular. So by Lemma
3.2, $S\times[N]\times([D_{0}^{16}])^{l}$ is a connected component of
$G_{exp}$ and

$\mathcal{T}(G_{reg}|_{S\times[N]},H)=G_{exp}|_{S\times[N]\times([D_{0}^{16}])^{l}}.$

Thus by Lemma 3.1, we get

$\lambda(G_{exp}|_{S\times[N]\times([D_{0}^{16}])^{l}})\leq\frac{1}{2}.$

Now let us run the $O(\log N)$ space algorithm $\mathcal{A}_{\lambda}$ with
$\lambda=\frac{1}{2}$ on $G_{exp}$ and $(s,1^{l+1})$ and $(t,1^{l+1})$ given
by Proposition 2.3. The algorithm $\mathcal{A}_{con}$ will output "connected"
if $\mathcal{A}_{\lambda}$ outputs connected, else it will output
"disconnected".
The correctness of $\mathcal{A_{T}}$ follows from the discussion above, as $s$
and $t$ are connected in $G$ if and only if
$s\times[N]\times([D_{0}^{16}])^{l}$ and $t\times[N]\times([D_{0}^{16}])^{l}$
are connected in $G_{exp}$. The algorithm runs in $O(\log N)$ space as
computing $\text{Rot}_{G_{reg}}$, the main transform $G_{exp}$ and running
$\mathcal{A}_{\lambda}$ can be done using $O(\log N)$ space. So
$\mathcal{A}_{con}$ computes $\textsc{Ustconn}(G,s,t)$ using $O(\log N)$
space. ∎

##  5 An alternative proof of $\textsc{Ustconn}\in\textbf{L}$

This section will contain an alternative proof of
$\textsc{Ustconn}\in\textbf{L}$ given by Rozenman and VadhanRV (05). In both
proofs, the key idea is that Ustconn is solvable in log-space on bounded-
degree graphs with logarithmic diameter by enumerating over all paths.
Bounded-degree Expander graphs (graphs with second eigenvalue less than
$\frac{1}{2}$) are instances of such graphs, both proofs transform the graph
into an expander with bounded degree to solve Ustconn.

In the proof of Reingold, given any undirected graph with $N$ vertices,
Reingold first transforms the graph into a regular graph and then used a
combination of graph powering and zig-zag product to transform the regular
graph into an expander graph with constant degree over $poly(N)$ vertices,
while maintaining the connectivity properties of vertices. Graph powering
increases the connectivity of the graph, decreases $\lambda(G)$ while
increasing the degree and number of vertices polynomially. Zig-zag product
decreases the degree while keeping $\lambda(G)$ approximately still. The
combination of both decreases $\lambda(G)$ to $\frac{1}{2}$ while maintaining
the degree constant.

One the other hand, Rozenman and Vadhan’s proofRV (05) shares the same overall
process as Reingold, but used derandomized squaring instead of graph powering
and zig-zag products to increase the connectivity of the graph. Iterating
derandomized squaring yields highly connected graphs with relatively small
degree compared graph powering while maintain the same number of vertices.

######  Definition 5.1.

Let $G$ be an undirected $D$-regular graph over $[N]$, let $H$ be an
undirected d-regular graph over $[D]$. The derandomized square graph
$G\mathbin{\raisebox{0.86108pt}{ $\bigcirc${\rm s}\hskip 1.49994pt}}H$ is an
undirected $Dd$-regular graph over $[N]$ with rotation map

$\text{Rot}_{G\mathbin{\raisebox{0.60275pt}{ $\bigcirc${\rm s}\hskip
1.04996pt}}H}(v,(x,a))=(w,(h,b))$

where

  * •

$(u,y)=\text{Rot}_{G}(v,x)$

  * •

$(z,b)=\text{Rot}_{H}(y,a)$

  * •

$(w,h)=\text{Rot}_{G}(u,z)$

for any $v\in[N],x\in[D],a\in[d]$.

An edge in $G\mathbin{\raisebox{0.86108pt}{ $\bigcirc${\rm s}\hskip
1.49994pt}}H$ corresponds to a length 2 path in $G$. The following figure
illustrates an edge of the derandomized square
$G\mathbin{\raisebox{0.86108pt}{ $\bigcirc${\rm s}\hskip 1.49994pt}}H$:

Figure 2: The figure on the left shows the edge $(v,(x,a))\in
G\mathbin{\raisebox{0.77498pt}{ $\bigcirc${\rm s}\hskip 1.34995pt}}H$.
Variables in black correspond to vertex labels and red labels corresponds to
edge indices.

Similar to the zig-zag product, the derandomized product operates separately
on the connected components of $G$. The derandomized square
$G\mathbin{\raisebox{0.86108pt}{ $\bigcirc${\rm s}\hskip 1.49994pt}}H$
increases the connectivity of $G$ and increases the spectral gap. The
following theorem by Rozenman and Vadhan gives an upper bound on
$\lambda(G\mathbin{\raisebox{0.86108pt}{ $\bigcirc${\rm s}\hskip
1.49994pt}}H)$:

######  Theorem 5.1 (Rozenman-Vadhan).

If $G$ is an undirected $(N,D,\lambda)$-graph and $H$ is an undirected
$(D,d,\alpha)$-graph, then $G\mathbin{\raisebox{0.86108pt}{ $\bigcirc${\rm
s}\hskip 1.49994pt}}H$ is an $(N,Dd,f(\lambda,\alpha))$-graph where

$f(\lambda,\alpha)=1-(1-\lambda^{2})(1-\alpha)\leq\lambda^{2}+\alpha$

###### Proof.

See Theorem 6.3 in RV (05). ∎

To prove $\textsc{Ustconn}\in\textbf{L}$ in a manner similar to Theorem 4.1,
we require a family of undirected constant degree expander graphs to apply
derandomized squaring with. In addition, these graphs need to be computed in
log-space. This is possible by ReingoldRVW (00) and GabberGG (81)

######  Lemma 5.2.

For some constant $d=16^{q}$, there exists a family
$\\{X_{m}\\}_{m\in\mathbb{N}}$ of undirected graphs where $X_{m}$ is an
$(d^{m},d,\frac{1}{100})$-graph. Furthermore, $\text{Rot}_{X_{m}}$ can be
computed in space $O(m)$.

######  Definition 5.2.

Let $X_{m}$ be the family of constant degree graphs in Lemma 5.2, let $m_{0}$
be some fixed constant, define

$\displaystyle H_{m}$ $\displaystyle=X_{m},$ $\displaystyle\text{when }m\leq
m_{0}$ $\displaystyle H_{m}$
$\displaystyle=(X_{m_{0}-1+2^{m-m_{0}}})^{2^{m-m_{0}}},$
$\displaystyle\text{when }m>m_{0}$

$\text{Rot}_{G_{m}}$ can be computed in space $O(m+2^{m-m_{0}})$.

With the existence of such family of expanders, Rozenman and Vadhan takes a
similar approach as Reingold to prove $\textsc{Ustconn}\in\textbf{L}$. For any
input graph $G$ over $[N]$, it can be transformed to a 16-regular graph
$G_{reg}$, then by powering, it can be turned to a $d$-regular graph
$G_{0}=(G_{reg})^{q}$, where $d=16^{q}$ is the constant in Lemma 5.2. Then he
recursively defined $G_{m+1}=G_{m}\mathbin{\raisebox{0.86108pt}{
$\bigcirc${\rm s}\hskip 1.49994pt}}H_{m}$. Taking $m_{0}$ to be $\left\lceil
100\log N\right\rceil$ and $m_{1}=m_{0}+\log\log N+10$, Rozenman and Vadhan
showed that $\lambda(G_{m_{0}}|_{S})<\frac{3}{4}$ and
$\lambda(G_{m_{1}}|_{S^{\prime}})\leq\frac{1}{2N^{3}}$ for each connected
component $S$ of $G_{m_{0}}$ and $S^{\prime}$ of $G_{m_{1}}$. In addition, he
showed that $G_{m_{1}}$ has degree $poly(N)$ and can be constructed in $O(\log
N)$ space, i.e. $\text{Rot}_{G_{m_{1}}}$ can be computed using $O(\log N)$
space. As all transformations in this procedure operates separately on each
connected component, we can solve Ustconn of $G$ by running the algorithm of
Lemma 2.3 on $G_{m_{1}}$.

##  6 $\textbf{SL}=\textbf{L}$

The section will contain a proof of $\textbf{SL}=\textbf{L}$. Let us first
define the space SL.

A Turing machine can be defined by the 7-tuple
$(K,\Sigma,\Sigma_{0},k,\Delta,s,F)$. Specifically, $K$ is a finite set of
states, $\Sigma$ is the finite tape alphabet, $\Sigma_{0}\subseteq\Sigma$ is
the input alphabet, $k>0$ is the number of tapes, $s\in K$ is the initial
state, $F\subseteq K$ is the set of final states, and $\Delta$ is the finite
set of transitions.

Using this definition, we define transitions for the Turing machine with form
$(p,(ab,D,cd),q)$ where $a,b,c,d\in\Sigma$ and $D\in{1,-1}$. A transition of
the form $(p,ab,1,cd,q)$ means that if a Turing machine in state $p$, scans
$a$ and symbol $b$ is contained in the square to the right of the scanned
square, the Turing machine moves the tape head one square to the right,
rewrite the squares with symbol $a$ and symbol $b$ with symbol $c$ and symbol
$d$, respectively, and changes to state $q$. On the other hand, a transition
of the form $(p,ab,-1,cd,q)$ means that if a Turing machine in state $p$ scans
symbol $b$ and symbol $a$ is contained in the square to the left of the
scanned square, the Turing machine moves the tape head one square to the left,
rewrite the square with symbol $b$ and symbol $a$ to symbol $d$ and symbol
$c$, respectively, and changes to state $q$.

For Turing machines with multiple tapes, we define the transition form
$\delta=(p,t_{1},t_{2},\cdots,t_{k},q)$, where $k$ is the number of tapes.
Each $t_{i}$ is a 3-tuple $(ab,D,cd)$, which specifies the transition as
described above for tape $i$.

For a non-deterministic Turing machine, there can be multiple transitions from
each possible configuration. For each of these possible choices, the non-
deterministic Turing machine creates a branch in its configuration path. A
non-deterministic Turing machine accepts a configuration if any of the
branches within its configuration path ends at an accepting state.

We note that our definition of Turing machine is equivalent to that of a
standard Turing machine. Our "peeking" Turing machine can be reduced to the
big-headed Turing machine as defined by Hennie Hen (79), which has been shown
to be equivalent to a standard Turing machine.

Now, let us define symmetrical Turing machines using the definition by Lewis
and Papadimitriou in "Symmetric Space-Bounded Computation" LP (82).

######  Definition 6.1.

For a transition $\delta=(p,t_{1},t_{2},\cdots,t_{k},q)$, with
$t_{i}=(a_{i}b_{i},D_{i},c_{i}d_{i})$, we define its inverse
$\delta^{-1}=(q,t_{1}^{-1},t_{2}^{-1},\cdots,t_{k}^{-1},p)$, where
$t_{i}^{-1}=(c_{i}d_{i},-D_{i},a_{i}b_{i})$.

######  Definition 6.2.

A Symmetrical Turing Machine is a non-deterministic Turing machine whose
transition functions $\Delta$ is invariant under taking inverse, namely, for
every non-deterministic transition $\sum p_{i}\delta_{i}\in\Delta$, we have
$\sum p_{i}\delta_{i}^{-1}\in\Delta$.

######  Definition 6.3.

The space SL is the set of all languages which can be determined by a
symmetrical log-space Turing machine.

We note that a symmetric Turing machine has a number of special transitions,
from which it is always possible to revert from these transitions (since the
symmetric Turing machine includes the inverse of these transitions).

To prove that Ustconn is SL-complete, we shall use a lemma from the paper
Symmetric Space-Bounded Computation by Lewis and PapadimitriouLP (82). We
begin by defining relevant terms in the lemma.

######  Definition 6.4.

If there exists a transition from configuration $C_{1}$ to $C_{2}$, we write
$C_{1}\vdash_{M}C_{2}$ or equivalently $C_{2}\dashv_{M}C_{1}$.

Let us define the reflexive, transitive closure of $\vdash$, denoted
$\vdash^{*}_{M}$ and the transitive closure of $\vdash$, denoted
$\vdash^{+}_{M}$. For any $M$, let $\mathcal{A}$ be a subset of all possible
configurations on $M$. If for some possible configurations $C_{0},...,C_{n}$
of $M$, we have $C_{0}\vdash_{M}C_{1}\vdash_{M}\cdots\vdash_{M}C_{n}$ for some
$n\geq 0$ and $C_{1},C_{2},C_{3},\cdots C_{n}\not\in\mathcal{A}$, we write
$C_{0}\vdash_{M}^{*\mathcal{A}}C_{n}$ (equivalently
$C_{n}\dashv_{M}^{*\mathcal{A}}C_{0}$). Note that if $C_{0}\in\mathcal{A}$ and
$C_{0}\vdash_{M}C_{0}$, we have $C_{0}\vdash_{M}^{*\mathcal{A}}C_{0}$. If
$A_{1}\vdash_{M}^{*\mathcal{A}}B\vdash_{M}A_{2}$ for
$A_{1},A_{2}\in\mathcal{A}$ and $B$ a possible configuration of $M$, we write
$A_{1}\vdash_{M}^{+\mathcal{A}}A_{2}$ (equivalently
$A_{2}\dashv_{M}^{+\mathcal{A}}A_{1}$).

For a Turing machine $M$, define the Turing machine $M*$, which is the same as
$M$ except that one can’t re-enter its initial state, leave its final state
nor write blanks on its tapes. We also define $\overline{M}*$ as the
symmetrically closed $M*$, i.e. translations of $\overline{M}*$ is the union
of the transition of $M*$ and its inverse.

######  Lemma 6.1.

For a non-deterministic Turing machine $M=(K,\Sigma,\Sigma_{0},k,\Delta,s,F)$,
let $\mathcal{A}$ be a subset of all possible configurations of $M$. If the
following conditions hold:

  1. (a)

For any $A_{1},A_{2}\in\mathcal{A}$, if $A_{1}\vdash_{M}^{+\mathcal{A}}A_{2}$,
then $A_{2}\vdash_{M}^{+\mathcal{A}}A_{1}$.

  2. (b)

For any $A$ in the union of $\mathcal{A}$ and possible initial configurations
of $M$, any $B\not\in\mathcal{A}$, and any $C_{1},C_{2},C_{3}$, if
$A\vdash_{M}^{*\mathcal{A}}C_{1}\dashv_{M}^{*\mathcal{A}}C_{2}\dashv_{M}B\vdash_{M}C_{3}$,
then $C_{2}=C_{3}$.

  3. (c)

For any $A_{1}$ in the union of $\mathcal{A}$ and possible initial
configurations of $M$, any $A_{2}\in\mathcal{A}$, and any $B$, if
$A_{1}\vdash_{M}^{*\mathcal{A}}B\dashv_{M}^{*\mathcal{A}}A_{2}$, then
$A_{1}=A_{2}$.

Then, the symmetrical non-deterministic Turing machine $\overline{M}*$ would
accept the same language as $M$ in the same space as $M$.

###### Proof.

This is Lemma 1 in LP (82). ∎

Using this lemma, we can now prove that Ustconn is SL-complete.

######  Theorem 6.2.

Ustconn is SL-complete.

###### Proof.

We begin by proving that $\textsc{Ustconn}\in\textbf{NL}$. In other words, we
describe a non-deterministic Turing machine that can solve Ustconn.

Let us define a non-deterministic Turing machine $M$ with 2 tapes. Given an
undirected graph $G$ and nodes $s,t\in G$, $M$ begins by writing $s$ and $t$
on its two tapes. Let the tape containing $t$ be the tape containing the
destination node and the tape containing $s$ be the tape containing the
current node. At the start of each step, we non-deterministically choose a
neighbor of the current node, rewrite the neighbor into the tape containing
the current node, and check if the node in the tape containing the current
node is the same as the destination node. If the current node is the same as
the destination node, $M$ accepts, else $M$ continues the process. For our
non-deterministic process of choosing a neighbor, we move through the edges
from left to right. For each edge, we check if the edge contains the current
node. If it does, with probability $\frac{1}{2}$, we update the current node
by the other node in the edge. We move from the leftmost edge to the rightmost
edge in the input tape to maintain a constant order in choosing neighbors of
the current node.

Since both of our tapes only store $1$ node, it is clear that our non-
deterministic Turing machine run in log-space.

Now, we shall show that our non-deterministic Turing machine satisfies the
conditions in Lemma 6.1. Let $\mathcal{A}$ be the configuration in the Turing
machine where the tapes contain $t$ and the current node and the tape head
reading the inputs is at the start of an edge (about to choose a neighbor of
the current node).

Now, let us consider condition $(a)$ of the Lemma. For any
$A_{1},A_{2}\in\mathcal{A}$, where $A_{1}\vdash_{M}^{+\mathcal{A}}A_{2}$, let
the current node in configuration $A_{1}$ be $c_{1}$ and let the current node
in configuration $A_{1}$ be $c_{2}$. Since we have
$A_{1}\vdash_{M}^{+\mathcal{A}}A_{2}$, we know that $c_{1}$ and $c_{2}$ must
be neighbors (since we wouldn’t go through another configuration in
$\mathcal{A}$ before we arrive at the configuration $A_{2}$, i.e. we would not
be choosing any other node to get to $c_{2}$). Furthermore, since all the
edges in graph $G$ are undirected, it is clear that we can go back from
$c_{2}$ to $c_{1}$ with the same path. Thus, we have
$A_{2}\vdash_{M}^{+\mathcal{A}}A_{1}$.

Next, let us consider condition $(b)$ of the Lemma. Take any $A$ in the union
of $\mathcal{A}$ and possible initial configurations of $M$,
$B\not\in\mathcal{A}$, and $C_{1},C_{2},C_{3}$, such that
$A\vdash_{M}^{*\mathcal{A}}C_{1}\dashv_{M}^{*\mathcal{A}}C_{2}\dashv_{M}B\vdash_{M}C_{3}$.
From
$A\vdash_{M}^{*\mathcal{A}}C_{1}\dashv_{M}^{*\mathcal{A}}C_{2}\dashv_{M}B\vdash_{M}C_{3}$,
it is clear that $B$ is either $A$ or $\not\in\mathcal{A}$. Thus,
$C_{1},C_{2},C_{3}\not\in\mathcal{A}$, and are configurations of $M$ when non-
deterministically choosing the neighbors of the current node in configuration
$A$. Since we always choose neighbors by checking from the leftmost edge to
the rightmost, there is only one possible linear process to non-
deterministically choose the neighbors of the current node, i.e. for any
configuration while choosing neighbors of the current node, $M$ can only be
coming from one possible configuration and can only transition to one possible
configuration. Thus, it is clear that $C_{2}=C_{3}$.

Finally, let us consider condition $(c)$ of the Lemma. Take any $A_{1}$ in the
union of $\mathcal{A}$ and possible initial configurations of $M$,
$A_{2}\in\mathcal{A}$, and any $B$, such that
$A_{1}\vdash_{M}^{*\mathcal{A}}B\dashv_{M}^{*\mathcal{A}}A_{2}$. Let the
current node in $A_{1}$ be $c_{1}$. It is clear that $B$ is a configuration of
$M$ while $M$ is choosing the neighbors for $c_{1}$. It is also clear that to
return to another configuration with a current node that is not $c_{1}$, $M$
must first return to configuration $A_{1}$. Thus, $A_{1}=A_{2}$.

Since $M$ satisfied all three condisions of Lemma 6.1, by the lemma, the
symmetrical Turing machine $\overline{M}^{*}$ determines Ustconn in log-space.
So $\textsc{Ustconn}\in\textbf{SL}$.

Using Savitch’s argument in Sav (70) and noting that the graph generated from
a Symmetric Machine is undirected (since we can revert from any transition),
we have that Ustconn is SL-complete.

More specifically, consider any problem in SL which is solved by the symmetric
Turing machine $M$. Since $M$ can be computed in log-space, there are
polynomially many states for $M$. We can construct a graph $G$, where the
nodes are the possible states of $M$, and the edges are transitions between
the possible states. Since $M$ is a symmetric Turing machine, we note that the
edges are undirected. Thus, solving the problem using $M$ would be equivalent
to checking if there’s a path that connects the node of a starting state to
the node of an accepting state. Thus, we have shown that all problems in SL
can be reducible to Ustconn and Ustconn is SL-complete. ∎

######  Theorem 6.3.

$\textbf{SL}=\textbf{L}$

###### Proof.

This is a direct consequence of Theorem 4.1 and Theorem 6.2. ∎

##  7 Discussion

In this section, we will discuss the importance of the paper by ReingoldRei
(08) and some further research based on the paper.

The paper by Reingold has made progress towards discovering the relationship
between L and RL. Let us begin by defining RL.

######  Definition 7.1.

RL is the space of all languages $L$ such that there exists a randomized
Turing machine $T$ which runs in log-space and polynomial time and satisfies

$P(T\text{ accepts }x)>\frac{2}{3},\quad x\in L$ $P(T\text{ rejects
}x)=1,\quad x\not\in L$

Notice that we can choose any constant $0<c<1$ replacing $\frac{2}{3}$. We can
also increase the probability of accepting $x$ when $x\in L$ to
$1-2^{-poly(|x|)}$ by repeating the algorithm $poly(|x|)$ times.

It has been shown by Aleliunas et al, in 1979 that
$\textsc{Stconn}\in\textbf{RL}$ AKL+ (79) In particular, Ustconn, as a
specific case of Stconn is contained in RL. Furthermore, it has been shown
that random walks can be generated by a randomized Turing machine of RL in
polynomial time and log space. Thus, Reingold’s proof that
$\textsc{Ustconn}\in\textbf{L}$ has brought forth major areas of research into
the properties of RL.

Building upon this research, Reingold, Trevisan, and Vadhan has shown in
2005RTV (05) that a subset of Stconn (Stconn for graphs whose random walks are
of polynomial mixing time) is RL complete and a deterministic log-space Turing
Machine can be used to simulate random walks for biregular graphs.

Some areas of future research into the relationship between L and RL could be
to investigate whether one can describe a deterministic log-space Turing
Machine that can simulate random walks for all regular directed graphs.

## References

  * AKL+ (79) Romas Aleliunas, Richard Karp, Richard Lipton, László Lovász, and Charles Rackoff.  Random walks, universal traversal sequences, and the complexity of maze problems.  Foundations of Computer Science, 1979.

  * Alo (86) Noga Alon.  Eigenvalues and expanders.  Combinatorica, 6(2):83–96, 1986.
  * AR (94) Noga Alon and Yuval Roichman.  Random cayley graphs and expanders.  Random Structures & Algorithms, 5(2):271–284, 1994.
  * AS (00) Noga Alon and Benny Sudakov.  Bipartite subgraphs and the smallest eigenvalue.  Combinatorics, Probability and Computing, 9(1):1–12, 2000.
  * ATSWZ (00) Roy Armoni, Amnon Ta-Shma, Avi Wigderson, and Shiyu Zhou.  An o(log(n)4/3) space algorithm for (s, t) connectivity in undirected graphs.  J. ACM, 47:294–311, 2000.
  * GG (81) Ofer Gabber and Zvi Galil.  Explicit constructions of linear-sized superconcentrators.  Journal of Computer and System Sciences, 22(3):407–420, 1981.
  * Hen (79) Fred Hennie.  Introduction to computability.  Addison-Wesley, 1979.
  * LP (82) Harry R. Lewis and Christos H. Papadimitriou.  Symmetric space-bounded computation.  Theoretical Computer Science, 19(2):161–187, 1982.
  * NSW (92) Noam Nisan, E. Szemeredi, and Avi Wigderson.  Undirected connectivity in o(log1.5n) space.  pages 24 – 29, 11 1992.
  * Rei (08) Omer Reingold.  Undirected connectivity in log-space.  Journal of the ACM (JACM), 55(4):1–24, 2008.
  * RTV (05) Omer Reingold, Luca Trevisan, and Salil Vadhan.  Pseudorandom walks in biregular graphs and the rl vs. l problem.  Electronic Colloquium on Computational Complexity (ECCC), 01 2005\.
  * RV (05) Eyal Rozenman and Salil Vadhan.  Derandomized squaring of graphs.  In Approximation, Randomization and Combinatorial Optimization. Algorithms and Techniques, pages 436–447. Springer, 2005.
  * RVW (00) Omer Reingold, Salil Vadhan, and Avi Wigderson.  Entropy waves, the zig-zag graph product, and new constant-degree expanders and extractors.  In Proceedings 41st Annual Symposium on Foundations of Computer Science, pages 3–13. IEEE, 2000.
  * Sav (70) Walter J. Savitch.  Relationships between nondeterministic and deterministic tape complexities.  Journal of Computer and System Sciences, 4(2):177–192, 1970.
  * Tri (05) Vladimir Trifonov.  An o(log n log log n) space algorithm for undirected st-connectivity.  In Proceedings of the Thirty-Seventh Annual ACM Symposium on Theory of Computing, STOC ’05, page 626–633, New York, NY, USA, 2005. Association for Computing Machinery.


# EEG-GPT: Exploring Capabilities of Large Language Models for EEG
Classification and Interpretation

Jonathan W. Kim, BS
Carle Illinois College of Medicine
Urbana-Champaign, IL
<EMAIL_ADDRESS>
Ahmed Alaa, PhD
Department of EECS
UC Berkeley
Berkeley, CA
Danilo Bernardo, MD
Department of Neurology
UC San Fracisco
San Francisco, CA
<EMAIL_ADDRESS>

###### Abstract

Rationale In conventional machine learning (ML) approaches applied to
electroencephalography (EEG), this is often a limited focus, isolating
specific brain activities occurring across disparate temporal scales (from
transient spikes in milliseconds to seizures lasting minutes) and spatial
scales (from localized high-frequency oscillations to global sleep activity).
This siloed approach limits the development EEG ML models that exhibit multi-
scale electrophysiological understanding and classification capabilities.
Moreover, typical ML EEG approaches utilize black-box approaches, limiting
their interpretability and trustworthiness in clinical contexts. Thus, we
propose EEG-GPT, a unifying approach to EEG classification that leverages
advances in large language models (LLM). EEG-GPT achieves excellent
performance comparable to current state-of-the-art deep learning methods in
classifying normal from abnormal EEG in a few-shot learning paradigm utilizing
only 2% of training data. Furthermore, it offers the distinct advantages of
providing intermediate reasoning steps and coordinating specialist EEG tools
across multiple scales in its operation, offering transparent and
interpretable step-by-step verification, thereby promoting trustworthiness in
clinical contexts.

_Keywords_ Large language models $\cdot$ EEG $\cdot$ machine learning

##  1 Introduction

Large language models (LLMs) such as ChatGPT have garnered substantial
attention in the media and among the machine learning (ML) community. LLMs
represent a pivotal paradigm shift in artificial intelligence (AI), consisting
of transformer architectures substantially larger in scale compared to their
predecessors, such as Recurrent Neural Networks (RNNs) and Long Short-Term
Memory (LSTM) networks [1], and leverage internet-scale text corpora, thus
excelling not only on text completion tasks but demonstrating emergent
capabilities in rudimentary language reasoning [2, 3].

LLMs display several features conducive to the small data regime present in
most EEG datasets, where the largest datasets typically have on the order of
only thousands of EEGs. Primarily, LLMs have the capability to perform few-
and even zero-shot learning [4]. Recent research has investigated how LLMs can
perform few-shot learning in domains ranging from cancer drug synergy
prediction to cardiac signal analysis [5, 6]. Other work has demonstrated the
ability of LLMs to outperform experts in annotating political Twitter messages
with zero-shot learning [7]. Additionally, previous work has shown that
transformer architectures are capable of utilizing in-context learning for
zero-shot tasks – in other words, utilizing information provided in the prompt
in order to yield better performance on various tasks [8].

Figure 1: Diagram depicting the process of fine-tuning large language models
[9]

LLMs also appear to have the ability to plan and carry out intermediate
reasoning steps when asked to solve complex problems. Lightman et al.
investigate this property by training an LLM to solve complex competition-
level math problems in a stepwise manner that is transparent and human-
interpretable [2]. Previous work has investigated using prompting strategies
such as Chain of Thought [3], which have been shown to improve the ability of
LLMs to perform multi-step computations. More recently, Yao et al. developed a
framework called Tree of Thoughts, an extension of Chain of Thought approaches
which constructs a decision tree to be explored by an LLM in order to
facilitate solving complex problems requiring strategic lookahead and
backtracking [10].

Finally, LLMs appear to be capable of synergizing inputs from other
computational “experts” as a human might. In other words, when asked to solve
a complex problem, if given access to other specialized computational tools,
LLMs exhibit the capability to coordinate passing appropriate inputs to those
specialist tools then synergizing their outputs to come to a result. Yang et
al. developed a system paradigm known as MM-REACT which integrated ChatGPT
with a pool of computational "experts" in order to perform vision-based tasks
in a zero-shot regime [10].

Previous work has investigated the application of LLMs to EEG-related tasks.
Cui et al. report NeuroGPT, an LLM-based framework used to generate and
predict embeddings of EEG signal [11]. They demonstrate that this framework
shows improved performance on the task of classifying motor imagery from EEG
signal relative to other machine learning modalities. Other work includes the
BENDR framework by Kostas et al., which applied a transformer architecture
towards the task of EEG-based sleep stage classification [12].

Human EEG classification and interpretation is highly subjective, with prior
studies in interrater reliability demonstrating widely variable Cohen’s kappa
($\kappa_{c}$) ranging from 0.3 to 0.7 amongst trained epileptologists[13].
Moreover, recent evaluations of current state-of-the-art (SOTA) EEG
interpretation systems such as Persyst which utilizes deep neural networks
have demonstrated subpar performance, with significant rates of false
negatives and false positives raising questions about the current utility of
DL EEG systems in clinical practice[14]. Here, we aim to evaluate the
potential of LLMs to aid clinicians in the tasks of EEG classification and
interpretation. We investigate whether an LLM-based approach may offer
advantages over current DL-based EEG interpretation and classification methods
in performance as well as in transparency.

##  2 Methods

We utilized two approaches to explore the capabilities of LLMs as they apply
to clinical EEG tasks, specifically the task of classifying EEG as normal or
abnormal. In both, we utilize the Temple University Hospital Abnormal Corpus,
which consists of a total of 1140 hours of EEG data collected from 2993
subjects, is roughly evenly balanced between normal and abnormal recordings,
and is pre-split into train and evaluation sets for consistency of evaluation
across different experiments [15].

###  2.1 Few- and zero-shot Learning

We hypothesize that, given a relatively small amount of training data, a fine-
tuned LLM (from here on referred to as EEG-GPT) will be able to classify EEG
as normal or abnormal at a high level of performance relative to other machine
learning modalities. We also hypothesize that with zero-shot learning, the
base LLM will be able to perform significantly better than chance on the
normal / abnormal classification task. Our pipeline for this experiment is
shown in Figure 2.

Figure 2: Pipeline for few-shot experiment

#### Feature selection and fine-tuning

For a given EEG file, we subdivide the file into non-overlapping 20-second
epochs. For each epoch, we calculate per-channel features (the subset of
channels used is shown in Table 2 and the set of features used is shown in
Table 1). The same set of features are calculated for each channel in order to
yield a 30-feature (6 features times 5 channels) sample for each epoch. Each
feature sample is labeled as normal or abnormal according to whether its
parent file was labeled as normal or abnormal.

We then convert these features to a verbal representation and then use these
verbal representations both to fine-tune and evaluate the da Vinci GPT-3 base
LLM from OpenAI on the resulting feature set. More specifically, we use
OpenAI’s Completions API in order to fine-tune and evaluate EEG-GPT; to fine-
tune an LLM using this API, we provide prompt and completion pair examples,
with the prompt being a verbal representation of features, and the completion
being the normal / abnormal label (an example prompt-completion pair is shown
in Figure 2.1). OpenAI’s API then fine-tunes the LLM to learn to "complete" a
prompt with the corresponding completion, in this case the prediction of
whether a given file is normal or abnormal.

Features calculated (over 20-second epoch)
---
90th percentile of voltage amplitudes
standard deviation
kurtosis
alpha:delta power ratio
theta:alpha power ratio
delta:theta power ratio

Table 1: Features calculated per channel

Channels used for feature calculation
---
Cz
T5
T6
O1
O2

Table 2: Channels used for feature calculation

        {"prompt":
            " Quantitative EEG: In a 20 second period,
                at channel Cz:[
                    the 90th percentile of voltage amplitudes = 0.35 microvolts,
                    standard deviation = 0.27,
                    kurtosis = 0.33,
                    alpha:delta power ratio = 0.22,
                    theta:alpha power ratio = 9.11,
                    delta:theta power ratio = 0.49];
                at channel T5:[
                    the 90th percentile of voltage amplitudes = 0.10 microvolts,
                    standard deviation = 0.09,
                    kurtosis = 1.53,
                    alpha:delta power ratio = 0.13,
                    theta:alpha power ratio = 2.43,
                    delta:theta power ratio = 3.13];
                at channel T6:[
                    the 90th percentile of voltage amplitudes = 0.18 microvolts,
                    standard deviation = 0.20,
                    kurtosis = 9.47,
                    alpha:delta power ratio = 0.09,
                    theta:alpha power ratio = 3.80,
                    delta:theta power ratio = 2.95];
                at channel O1:[
                    the 90th percentile of voltage amplitudes = 0.34 microvolts,
                    standard deviation = 0.28,
                    kurtosis = 0.11,
                    alpha:delta power ratio = 0.82,
                    theta:alpha power ratio = 1.33,
                    delta:theta power ratio = 0.92];
                at channel O2:[
                    the 90th percentile of voltage amplitudes = 0.30 microvolts,
                    standard deviation = 0.26,
                    kurtosis = 2.47,
                    alpha:delta power ratio = 0.39,
                    theta:alpha power ratio = 1.35,
                    delta:theta power ratio = 1.89];.

                Cumulative Effect Category:",

        "completion":" normal"}

Figure 3: Example prompt-completion pair (formatted for readability)

#### Few- and zero-shot learning

Using our derived feature set, we explore EEG-GPT’s performance on the
normal/abnormal classification task in a few-shot context, and compare its
performance against traditional machine learning approaches as well as against
more recent deep-learning based methods. We also explore EEG-GPT’s performance
in a zero-shot context – in other words, we evaluate how EEG-GPT performs on
the normal/abnormal task with no fine-tuning whatsoever, both with and without
in-context learning.

###  2.2 Evaluation of reasoning capability in EEG tool usage

We also hypothesize that an LLM-based framework will be able to effectively
utilize specialized software tools to classify EEG as abnormal or normal,
emulating how EEG readers systematically evaluate for signs of seizure,
spikes, and/or slowing when making a classification. To develop this
framework, we consider how clinical epileptologists analyze a given EEG file
for abnormalities.We conceptualize this process as a decision tree, which is
depicted in Figure 4. In this conceptualization, the epileptologist may first
evaluate the file for evidence of seizures, then check for spikes, then check
for signs of slowing – at any point, if there is strong evidence that any of
these phenomena are occurring, the epileptologist can confidently claim that
the file is abnormal. This is an overly simplified view of how clinical
epileptologists analyze EEG, but is appropriate for initial investigations
into how LLMs might utilize a similar step-wise, decision-tree-based process
when coming to an analytical decision of a file.

Figure 4: Simplified diagram of clinical epileptologist workflow

#### Tree of Thought

In order to adapt LLMs to solve complex problems requiring exploration and
strategic lookahead, Yao et al. developed the Tree-of-Thought framework, which
allows LLMs to explore and backtrack along a decision-tree style exploration
space when solving a complex problem [16]. This approach maps nicely onto our
simplified decision tree depicted in Figure 4, in which a clinical
epileptologist or LLM will explore the decision tree space in order to
classify a file as normal or abnormal.

#### Specialized software tools

In order to enable exploration of the decision tree we provide an agentic LLM
with access to three software tools: an automated seizure detection model, an
automated spike detection model, and an automated qEEG feature comparison
tool. When given a particular EEG file to evaluate, the framework will explore
the decision tree space, using the automated software tools available to it at
each branching point, deciding whether or not to proceed based on the input
from each software tool. These software tools are described in greater detail
below.

#### Automated seizure detection model

Using the Temple University Hospital seizure corpus [17], we trained an
automated EEG-based seizure detection model using a convolutional neural
network architecture. We ensure that there is no overlap between the subjects
used to train the seizure detection model and the subjects used to evaluate
the overall framework. This model takes in 10-second epochs and returns a
yes/no decision as to whether a given epoch contains seizure activity or not.
The model’s architecture and performance on a held-out set (pulled from a set
of subjects that does not overlap with the subjects used to evaluate the
overall framework) are depicted below.

#### Automated spike detection model

We use an automated spike detection algorithm based on Esteller’s work
investigating line length as a computational biomarker for EEG spikes [18].

#### qEEG feature comparison tool

As a final check for abnormality, we provide the framework with a qEEG feature
comparison tool. For this tool, we calculate a reference of age-based
normative ranges for a subset of qEEG features (statistical moments and power
ratios). Then, when given a particular EEG file, this tool calculates the set
of qEEG features and calculates a cosine similarity score to the age-matched
normative reference. If the cosine similarity score is higher than a
particular threshold, it will return a result of "similar to a reference of
normal files," and vice versa. This tool is also capable of providing a
confidence score associated with its prediction based on calculating positive
and negative predictive values derived from a held-out set.

##  3 Results

###  3.1 EEG-GPT demonstrates few- and zero-shot learning proficiency

We evaluate EEG-GPT in both few- and zero-shot contexts against both
traditional machine learning approaches and more recent deep-learning based
approaches. For the comparison against traditional machine learning
approaches, we utilize the same set of training features in order to
facilitate appropriate comparisons between the performance profiles of each.
Comparisons against deep-learning based approaches utilize the performance
metrics reported in their respective papers given that their deep learning
architectures utilize the raw EEG inputs instead of the limited feature set
used by EEG-GPT, and therefore their models would not be able to utilize the
same feature set.

Figure 5: Resulting AUROCs of normal/abnormal classification task, plotted
against proportion of training data used to fit model

When trained on 2% of available data, EEG-GPT achieves an AUROC of 0.86, as
shown in Figure 5 (EEG-GPT’s performance depicted with the pink "X"). This is
better than traditional machine learning approaches (linear regression,
logistic regression, and XGBoost), which improve performance when given
increasing amounts of training data, but plateau at an AUROC of roughly 0.8.
In the zero-shot context, EEG-GPT’s performance remains better than chance,
and improves to an AUROC of 0.63 when provided with in-context learning. When
trained on 2% of available train data, EEG-GPT even matches the performance of
a deep-learning based approach trained on all available data [19], although it
is still outperformed by more recent approaches such as those by Saab et al.
and Khan et al. [20, 21].

###  3.2 EEG-GPT navigates EEG tool usage with tree-of-thought reasoning

We present two exemplars of the tree-of-thought approach here. In the first
demo, shown in Figure 6, we pass an EEG file which is known to contain
seizures to our framework. Stepping through the solving procedure we see that
the automated seizure detector immediately detects a seizure, indicating that
the file is abnormal and allowing for early stoppage of the solving procedure.

Figure 6: Framework’s analysis of EEG file known to contain seizure

In the second demo, shown in Figure 7, we pass an EEG file which is known to
be abnormal yet not contain seizures to the framework. Stepping through the
solve procedure, we see that the seizure detector does not find any seizures –
the framework then decides to evaluate the file with another tool, the qEEG
feature comparison tool. The framework then finds that the file is similar to
a reference of normal EEGs, with a confidence measure of 0.54 provided by the
qEEG tool itself. Presumably given the low confidence, the framework decides
it needs still more information before classifying this file, and proceeds to
use the automated spike detection tool – which does indeed detect spikes,
indicating that this file is abnormal. At this point the framework decides it
has enough information and confidence to make a final classification, and
halts execution.

Figure 7: Framework’s analysis of abnormal EEG file known to be seizure-free

##  4 Discussion & Future Work

In this work we demonstrate the proficiency of EEG-GPT within a few-shot
learning paradigm for EEG interpretation and classification tasks. In
addition, we demonstrate a pilot exploration of EEG-GPT’s reasoning ability in
its capacity to navigate usage of specialist EEG tools across multiple
temporal scales in a step-wise, transparent fashion. For the normal/abnormal
classification task, EEG-GPT demonstrates performance that surpasses
traditional machine learning methods at all amounts of training data. EEG-GPT
also matches at least one previous deep-learning based approach, even when
trained on 50 times less data. It is also worth noting that while all the deep
learning approaches evaluated (ChronoNet, StanfordCNN, and HybridCNN)
outperform or match EEG-GPT, these approaches are trained on all available
training data, and utilize the raw EEG signal, which is a much richer feature
space than the relatively limited set of features used by EEG-GPT. EEG-GPT’s
few- and zero-shot learning abilities may be partially explained by the likely
presence of normative EEG data in the large data corpus used to train the base
LLM.

Clinical medicine has traditionally been relatively slow to adopt machine
learning techniques for clinical practice due to various ethico-legal reasons,
as well as the fact that many state-of-the-art machine learning models
function as "black boxes," with very little insight into how models come to a
particular prediction or decision. By utilizing structured reasoning
strategies such as tree-of-thought, LLMs are capable of demonstrating logical
flows in their problem-solving processes. However, a significant limitation of
current LLMs is their propensity to generate non-factual or "hallucinated"
information[22], which limits their reliability and trustworthiness in high-
stakes, clinical settings. To address this limitation, step-wise verifiability
of clinical LLM systems coupled with a human in the loop or human oversight
emerges as a strategy to identify LLM errors or hallucinations. This
explainable AI (XAI) approach allows for monitoring and rectification of LLM
system outputs, thereby mitigating the risks associated with hallucinations
and easing the path to clinical adoption of AI.

Future investigation is warranted to develop and validate the potential of LLM
systems for EEG interpretation and classification. Future work would involve
further exploration of the clinical EEG feature space in order to further
optimize performance. Given our results which seem to indicate LLMs’
usefulness in performing tasks with relatively small amounts of training data,
there is reason to hypothesize that LLMs may be particularly useful for rare
disease applications, where training data is relatively expensive or difficult
to obtain. Further study is needed in evaluating the reasoning capabilities,
such as in tree-of-thought, to identify potential failure modes such as
"hallucinations". In addition, as current LLMs may have poorer performance
with more complex reasoning tasks[23], more work is necessary to appraise the
validity of LLM logical reasoning in EEG interpretation and classification
problems. Further investigation would also involve continuing to add
specialized software tools to the framework and further building out the
system’s ability to appropriately recognize edge cases that may merit
specialized software tools.

LLMs represent a promising approach for EEG interpretation and classification,
and their potential to demonstrate emergent AI-reasoning abilities warrants
further development and investigation. However, it is crucial that future work
recognize limitations of LLMs’ nascent "reasoning" capabilities especially
their tendency to hallucinate. Consequently, a step-by-step verifiability with
human oversight is highly recommended, as it enhances the reliability and
interpretability of LLMs in clinical applications, aligning with the crucial
need for trust and accountability in medical decision-making.

## References

  * [1] Ashish Vaswani et al.  “Attention is all you need”  In _Advances in neural information processing systems_ 30, 2017
  * [2] Hunter Lightman et al.  “Let’s Verify Step by Step”, 2023  arXiv:2305.20050 [cs.LG]
  * [3] Maxwell Nye et al.  “Show Your Work: Scratchpads for Intermediate Computation with Language Models”, 2021  arXiv:2112.00114 [cs.LG]
  * [4] Yaqing Wang, Quanming Yao, James T. Kwok and Lionel M. Ni  “Generalizing from a Few Examples: A Survey on Few-Shot Learning”  In _ACM Comput. Surv._ 53.3 New York, NY, USA: Association for Computing Machinery, 2020  DOI: 10.1145/3386252
  * [5] Xin Liu et al.  “Large Language Models are Few-Shot Health Learners”, 2023  arXiv:2305.15525 [cs.CL]
  * [6] Tianhao Li et al.  “CancerGPT: Few-shot Drug Pair Synergy Prediction using Large Pre-trained Language Models”, 2023  arXiv:2304.10946 [cs.CL]
  * [7] Petter Törnberg  “ChatGPT-4 Outperforms Experts and Crowd Workers in Annotating Political Twitter Messages with Zero-Shot Learning”, 2023  arXiv:2304.06588 [cs.CL]
  * [8] Shivam Garg, Dimitris Tsipras, Percy S Liang and Gregory Valiant  “What Can Transformers Learn In-Context? A Case Study of Simple Function Classes”  In _Advances in Neural Information Processing Systems_ 35 Curran Associates, Inc., 2022, pp. 30583–30598  URL: https://proceedings.neurips.cc/paper_files/paper/2022/file/c529dba08a146ea8d6cf715ae8930cbe-Paper-Conference.pdf
  * [9] Tomaz Bratanic  “Knowledge Graphs & LLMs: Fine-Tuning vs. Retrieval-Augmented Generation”, 2023  URL: https://neo4j.com/developer-blog/fine-tuning-retrieval-augmented-generation/
  * [10] Zhengyuan Yang et al.  “MM-REACT: Prompting ChatGPT for Multimodal Reasoning and Action”, 2023  arXiv:2303.11381 [cs.CV]
  * [11] Wenhui Cui et al.  “Neuro-GPT: Developing A Foundation Model for EEG”, 2023  arXiv:2311.03764 [cs.LG]
  * [12] Demetres Kostas, Stéphane Aroca-Ouellette and Frank Rudzicz  “BENDR: Using Transformers and a Contrastive Self-Supervised Learning Task to Learn From Massive Amounts of EEG Data”  In _Frontiers in Human Neuroscience_ 15, 2021  DOI: 10.3389/fnhum.2021.653659
  * [13] Arthur C Grant et al.  “EEG interpretation reliability and interpreter confidence: a large single-center study”  In _Epilepsy & Behavior_ 32 Elsevier, 2014, pp. 102–107
  * [14] Taneeta Mindy Ganguly et al.  “Seizure detection in continuous inpatient EEG: a comparison of human vs automated review”  In _Neurology_ 98.22 AAN Enterprises, 2022, pp. e2224–e2232
  * [15] S. Lopez  “Automated Identification of Abnormal EEGs.”, 2017  Temple University
  * [16] Shunyu Yao et al.  “Tree of Thoughts: Deliberate Problem Solving with Large Language Models”, 2023  arXiv:2305.10601 [cs.CL]
  * [17] Iyad Obeid and Joseph Picone  “The Temple University Hospital EEG Data Corpus”  In _Frontiers in Neuroscience_ 10, 2016  DOI: 10.3389/fnins.2016.00196
  * [18] R. Esteller et al.  “Line length: an efficient feature for seizure onset detection”  In _2001 Conference Proceedings of the 23rd Annual International Conference of the IEEE Engineering in Medicine and Biology Society_ 2, 2001, pp. 1707–1710 vol.2  DOI: 10.1109/IEMBS.2001.1020545
  * [19] Subhrajit Roy, Isabell Kiral-Kornek and Stefan Harrer  “ChronoNet: A deep recurrent neural network for abnormal EEG identification”  In _Artificial Intelligence in Medicine: 17th Conference on Artificial Intelligence in Medicine, AIME 2019, Poznan, Poland, June 26–29, 2019, Proceedings 17_ , 2019, pp. 47–56  Springer
  * [20] Khaled Saab et al.  “Weak supervision as an efficient approach for automated seizure detection in electroencephalography”  In _NPJ digital medicine_ 3.1 Nature Publishing Group UK London, 2020, pp. 59
  * [21] Imran Ullah Khan, Sitara Afzal and Jong Weon Lee  “Human activity recognition via hybrid deep learning based model”  In _Sensors_ 22.1 MDPI, 2022, pp. 323
  * [22] Lei Huang et al.  “A survey on hallucination in large language models: Principles, taxonomy, challenges, and open questions”  In _arXiv preprint arXiv:2311.05232_ , 2023
  * [23] Ruocheng Wang et al.  “Hypothesis search: Inductive reasoning with language models”  In _arXiv preprint arXiv:2309.05660_ , 2023