# Complexity class of efficient streaming algorithms

Consider the class of problems $$\mathsf{StreamL}$$ which can be solved in logarithmic space reading the input in a single pass from left to right. In other words:

$$L \in \mathsf{StreamL}$$ if there exists a Turing machine $$M$$ which decides $$L$$, where:

• There are two tapes, the read-only input tape and the working tape

• $$M$$ moves only to the left on the input tape, and uses at most $$O(\log n)$$ space on the working tape.

Has this class been studied?

My assumption is that the answer is yes, but I'm not yet aware of a definition of the class in the literature.

Most literature on streaming algorithms that I am aware of considers the complexity of solving specific algorithmic problems, and does not tackle structural complexity i.e. defining classes such as the above and determining their relationships.

There is also a large body of work on communication complexity classes. In this domain there is a relevant class called $$\mathsf{P}^{cc}$$ (see Babai, Frankl, and Simon 1986: Complexity classes in communication complexity theory), which contains functions of two variables $$f(x,y)$$ where they can be solved using a small amount of communication between $$x$$ and $$y$$. This is related to $$\mathsf{StreamL}$$ above (for functions of two variables, $$\mathsf{StreamL}$$ is contained in $$\mathsf{P}^{cc}$$), but the class above is not limited to functions of two variables and enforces a stricter computational requirement.

The obvious inclusions are $$\mathsf{REG} \subseteq \mathsf{StreamL} \subseteq \mathsf{L}$$, and no apparent inclusion either way between $$\mathsf{StreamL}$$ and $$\mathsf{NC}^1$$.

• I don't think there are many studies on this. It seems to me that for most purposes, we still study the one-way communication complexity which can be applied to proving lower bound for streaming algorithms.
– HTV
Apr 24 '20 at 2:47
• Using the diajointness function (an AND of ORs) you can construct functions in NC1, even in AC0, that is not in StreamL (for communication complexity reasons). StreamL would be a very weak class indeed. Apr 24 '20 at 7:23

## 1 Answer

Along with my comment above (noting that not even AC0 is in "StreamL"), let me say that that this class has been studied before; you just need to know what they used to call it.

Search for "one-way logspace" and you will find plenty of references. (Typically, past work treats it as a reducibility concept.) The papers that those papers reference should cover what you need.

• Thank you for the answer. Indeed, the class is called $1L$ and is studied by Hartmanis and others, e.g. Hartmanis and Mahaney, 1981: Languages simultaneously complete for one-way and two-way log-tape automata. Here is a related question.
– 6005
Apr 25 '20 at 2:04