Corpus-compressed Streaming and the Spotify Problem
Aubrey Alston (ada2145@columbia.edu)

arXiv:1707.00080v1 [] 1 Jul 2017

1

Overview

In this work, we describe a problem which we refer to as the Spotify problem and explore a potential
solution in the form of what we call corpus-compressed streaming schemes.
Spotify is a digital music streaming service that gives users access to music on demand. One of its
most prominent features is the ‘playlist’ feature: Spotify (and other Spotify users) maintain and update
lists of songs that other users may listen to at any time. The process of listening to these playlists is
generally seamless on home networks due to the lack of significant bandwidth limitations, but this is not
necessarily the case for some mobile users whose mobile broadband networks are less than reliable. The
Spotify problem simply names the problem of improving the reliability of streaming playback for users
who spend time in these constrained networks.
More generally, the Spotify problem applies in any number of practical domains where devices may be
periodically expected to experience degraded communication or storage capacity. One obvious solution
candidate which comes to mind immediately is standard compression. Though obviously applicable, standard compression does not in any way exploit all characteristics of the problem; in particular, standard
compression is oblivious to the fact that a decoder has a period of virtually unrestrained communication. Towards applying compression in a manner which attempts to stretch the benefit of periods of
higher communication capacity into periods of restricted capacity, we introduce as a solution the idea of
a corpus-compressed streaming scheme.
This report begins with a formal definition of a corpus-compressed streaming scheme. Following a discussion of how such schemes apply to the Spotify problem, we then give a survey of specific corpus-compressed
scheming schemes guided by an exploration of different measures of description complexity within the
Chomsky hierarchy of languages. 1

Contents
1 Overview

1

2 Definition of a Corpus-compressed Streaming Scheme
2.1 Application to the Spotify Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

2
3

3 Corpus-compressed Streaming Schemes: Concrete Constructions using Regular Output Automata
4
3.1 Formalizing our Restriction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
3.2 Restricting Schematics to Acyclic Moore Machines . . . . . . . . . . . . . . . . . . . . . . . . . 5
3.2.1 An Exact AMM-restricted (0, ⌈log n⌉, 0)-Corpus-compressed Streaming Scheme . . . 6
3.2.1.1 Proving (0, log n, 0)-CCSS Validity . . . . . . . . . . . . . . . . . . . . . . . . 7
3.2.1.2 Runtime Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11
1 This

work is the project report produced for the Advanced Algorithms course at Columbia University.

1

Advanced Algorithms Project Report, Spring 2017
Aubrey Alston (ada2145@columbia.edu)
3.2.1.3 A Note on Optimality and a Worked Example . . . . . . . . . . . . . . . .
On the Hardness of Maintaining Minimality for a p(n, z) > ⌈log n⌉ AMM-restricted
CCSS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2.1 Considering δ > 0-Minimality . . . . . . . . . . . . . . . . . . . . . . . . . . .
3.2.2.2 Relaxing the Problem: from f (⋅)-Minimality to E[f (⋅)]-Minimality . . . .
Restricting Schematics to General Moore Machines . . . . . . . . . . . . . . . . . . . . . . .
An Equivalent Formulation of the Construction Problem . . . . . . . . . . . . . . . . . . . .

. 11

3.2.2

3.3
3.4

.
.
.
.
.

13
15
16
16
17

4 Future Work

18

5 Conclusion

19

2

Definition of a Corpus-compressed Streaming Scheme

We define a corpus-compressed streaming scheme in a setting consisting of two parties, an encoder
A and a decoder B. A holds a finite set of n distinct binary strings C = {c1 , ..., cn }, called a corpus set, in
which B is interested. Following a setup phase, A has need to convey some stream of strings within this
corpus set ci1 , ci2 , ... to B with the following constraints:
• During the setup phase, A and B may communicate freely.
• During the stream, communication between A and B is costly.
• During the entire exchange, memory is costly for B, meaning that B desires not to store the entire
corpus set.
• There is no characterization of the stream beyond the fact that all strings come from the corpus set.
We give a general definition of a corpus-compressed streaming scheme as well as a formal parameterization
of the function of such a scheme:
Definition 2.1. corpus-compressed streaming scheme Let C be a corpus set containing n distinct strings.
A corpus-compressed streaming scheme (CCSS), is a triplet of algorithms (Construct(C), Encode(D, x), Decode(D, x̂))
respectively defined as follows:
1. Construct(C) takes as input a corpus set and returns a schematic object D along with (potentially
empty) auxiliary output A. A schematic object is a data structure used to encode and decode
elements of the corpus set.
2. Encode(D, A, x) takes as input a valid schematic D and associated auxiliary input A and a string
x ∈ C and returns either an encoding of x or ⊥ if x is invalid with respect to D.
3. Decode(D, x̂) takes as input a valid schematic D and an encoding x̂ and returns some string x ∈ C
(where D is a valid schematic for C).
Definition 2.2. δ-minimal p(n, z) − -corpus-compressed streaming scheme Let C be a corpus set containing n strings; let z = maxci ∈C ∣ci ∣ be the length of the longest string in C. A δ-minimal p(n, z) − corpus-compressed streaming scheme, shorthand (δ, p(n, z), )-CCSS, is a corpus-compressed streaming
scheme (Construct, Encode, Decode) with the following properties:
1. Compression: For D = Construct(C),
∀ci ∈ C, ∣Encode(D, ci )∣ ≤ p(n, z)
As defined, the parameter p(n, z) gives the maximum length of the streaming code for any individual ci ∈ C as a function of the size of the corpus and the maximum element size.
Page 2

Advanced Algorithms Project Report, Spring 2017
Aubrey Alston (ada2145@columbia.edu)

2. Correctness: For D = Construct(C),
∀ci ∈ C,

ham(Decode(D, Encode(D, A, ci )), ci )
≤
∣ci ∣

and where ham(⋅, ⋅) denotes Hamming distance. As defined, the parameter  parameterizes the
maximum reconstruction error of the scheme.
3. Minimality: For D = Construct(C),
∣D∣
≤1+δ
∣D∗∣
where D∗ is the minimum-length satisfactory schematic among some restriction of possible objects
D. As defined, δ defines the factor by which the output of Construct(D) is off from some definition of
minimal. We will see in later sections that this notion of minimality has some interesting connections
to concepts in algorithmic information theory.
Because this is a first presentation of corpus-compressed streaming, this work will explore only schemes
guaranteeing exact reconstruction (in other words, we fix  to be 0 in all explorations). We additionally
provide the following trivial lower bound on the minimum achievable streaming code length of any CCSS
which we will use in our exploration:
Theorem 2.1. Let S be a valid (⋅, p(n, z), 0) corpus-compressed scheming scheme. The maximum streaming code length for any corpus set must obey the inequality p(n, z) ≥ log(n + 1) − 1.
Proof: Assume not. Assume p(n, z) < log(n + 1) − 1. Even if the scheme makes use of variable length
streaming codes, the scheme may only encode

<

log(n+1)−1

∑

2i

i=1
log(n+1)−1+1

<2

−1

<n+1−1
<n
distinct strings. Since C includes n distinct strings but can encode only less than that number, we conclude
that S cannot possibly be  = 0-correct.◻.

2.1

Application to the Spotify Problem

We see immediately that the existence of a (δ, p(n, z), )-CCSS with reasonably sized schematics yields
an effective solution to the Spotify problem. For the sake of illustration, say that we have a (δ, p(n, z), )CCSS, (Construct, Encode, Decode). In the setting of the Spotify problem, we may apply the scheme in
the following straight-forward manner:
1. Before leaving his or her home network, the user indicates to Spotify that he or she wishes to listen
to playlist P = {s1 , ..., sn }.
2. Spotify then treats the playlist of songs as a corpus set and sends D = Construct(P ) to the user’s
device.
3. The user leaves his or her home network, entering a bandwidth-constrained mobile network.

Page 3

Advanced Algorithms Project Report, Spring 2017
Aubrey Alston (ada2145@columbia.edu)

4. In perpetuity, then, when the user requests song i, Spotify now sends Encode(D, si ) (of length less
than or equal to p(n, z)) rather than the entirety of si .
Consider the effect such an application would have on the music streaming process. In essence, the
user ultimately utilizes his or her temporarily unconstrained bandwidth in the second step to receive a
reasonably sized data structure that will allow him to stream music at a reduced cost in perpetuity; note
that by choosing p(n, z) as conservatively as zr , where mobile bandwidth is 1r -fraction of home bandwidth
(often, r < 2), we would negate any difference in playback he or she might otherwise observe, thus solving
the problem.

3

Corpus-compressed Streaming Schemes: Concrete Constructions using Regular Output Automata

In this section, we attempt to design corpus-compressed streaming schemes by taking inspiration from
elements of algorithmic information theory. Among these elements is the notion of the Kolmogorov
complexity of an object, one of the most prevalent ideas in algorithmic information theory [4], defined as
the length of the shortest Turing machine description which produces said object.
For our purposes, we both project this idea onto the notion of a corpus-compressed streaming scheme
and direct our analysis to consider another segment of the Chomsky hierarchy of languages. In particular,
where Kolmogorov complexity is interested in the length of the shortest Turing machine which outputs a
string x, we would be interested in the shortest general output Turing machine M which has the following
property for a corpus set C:
∀ci ∈ C, ∃ei , ∣ei ∣ ≤ p(n, z), M (ei ) = ci
We make two observations and derive one question which guides our exploration in this section. We
first note that the decision variant of determining Kolmogorov complexity is undecidable, and so there
is no algorithmic solution (in the way of Construct) capable of constructing M given C. We also note
that output Turing machines correspond to the most encompassing point in the Chomsky hierarchy of
languages. These observations lead us to ask the following question: what if instead we restrict schematics
to output automata corresponding to less encompassing points in the hierarchy?
This question guides the CCSS constructions we derive. This work begins to answer this question by
considering corpus-compressed streaming schemes with schematics restricted to the least encompassing
point in the Chomsky hierarchy: that of regular languages. A regular language may be defined as a
language which may be recognized by a finite state machine; as we are interested in machines with
output, in this work we will consider the schemes we may derive when we restrict schematics to the set of
finite state machines with per-state output, known as Moore machines. More specifically, we first consider
schemes with schematics restricted to Moore machines whose underlying acyclic graphs are acyclic and
then use these results to make connections to the general (cyclic) case.

3.1

Formalizing our Restriction

In this section, we are interested in schemes (Construct, Encode, Decode) where the output of Construct(C)
is a Moore machine defined by the tuple (S, S0 , Σ, Γ, T, G) with the following properties:
1. S0 is the unique start state of the machine.
2. Σ, the input alphabet, is the set {0, 1, ⊥}. ⊥ is a special end-of-input symbol that is read only at
the end of every string.
3. Γ = Σ is the output alphabet. In the case of the output alphabet, ⊥ is a special blank symbol which
only ever occurs at a starting or final state.

Page 4

Advanced Algorithms Project Report, Spring 2017
Aubrey Alston (ada2145@columbia.edu)

4. T ∶ S × Σ ⇒ S is a deterministic transition function mapping states to successor states given an
input symbol. With respect to the transition function of a Moore machine, we use the convention
of a unconditional transition, which is a transition which is taken regardless of whether or not
the next input symbol is 0 or 1. Absent the presence of an explicit ⊥-transition, this transition is
taken even if there is no next input symbol.
5. G is an output function mapping states to their outputs.
The output of Construct must satisfy the further stipulation that a (δ, p(n, z), )-CCSS maintain
p(n, z)-compression and -correctness for the following fixed, universal Decode procedure utilized by
schemes under this restriction:
Algorithm 1 Fixed Decoding Procedure
procedure Decode(D = (S, S0 , Σ, Γ, T, G), x)
Beginning at S0 , run D on input x. If ever there is a next input symbol but no successor state,
return ⊥.
3:
return the sequence of 0 and 1 outputs of D.
4: end procedure

1:

2:

(Note: while this restriction does not necessarily stipulate a universal Encode procedure, the requirement
remains that it must exist and be efficiently computable.)
Under this restriction of schematics, we define δ-minimality with respect to the number of states in a
machine. For a given corpus set C, the minimal schematic is the Moore machine with the smallest number
of states of any Moore machine satisfying the stated requirements.
In the remainder of this section, we refer to a CCSS under this restriction as a MM (Moore
machine)-restricted CCSS.

3.2

Restricting Schematics to Acyclic Moore Machines

In [1], Bryant presented the binary decision diagram (BDD) data structure as a means of representing and
manipulating Boolean functions. The core mechanism underlying applications of BDDs is their function
as read-once branching programs: functions are represented as rooted, directed acyclic graphs consisting
of decision junctions and terminal nodes. Each transition from a decision junction corresponds to a
final assignment to exactly one variable, and terminal nodes correspond to function evaluations given
assignments so far. The end result is a graph in which every distinct path corresponds to a distinct
⃗ ending with a terminal node having a label corresponding to whether it satisfies
variable assignment x
the formula.
Perhaps more importantly, BDDs are especially useful with respect to Boolean function representation
because they are amenable to compression through the use of simple reduction rules. Given a formula
Φ in n variables and an ordering of those variables, there exists the notion of a reduced-ordered BDD
(ROBDD) which is able to represent every assignment (and its image in Φ) in a diagram having often far
fewer than 2n nodes for many practical instances.
Considering once more our interests in this work, there is at least one significant direct parallel between BDDs and the goals of corpus-compressed streaming schemes. In particular, consider a Moore
machine schematic in which there are no cycles of states. If we view the graph created by the set of states
S and the transition function T , we see that we also have a rooted, directed acyclic graph with decision
junctions at states having transition options for both input symbols 0 and 1 in which distinct paths lead
to distinct outputs.
While BDDs and Moore machine schematics are obviously not exactly analogous with respect to
goals and structure, these observable similarities naturally lead us to question whether similar reduction
methods in corpus-compressed streaming might yield practical schemes. Inspired by this prospect, in this
Page 5

Advanced Algorithms Project Report, Spring 2017
Aubrey Alston (ada2145@columbia.edu)

section, we study corpus-compressed streaming in our chosen restriction with the additional requirement
that the graphs underlying schematics be acyclic. We denote a valid CCSS under this restriction by the
term ‘AMM (Acyclic Moore machine) -restricted CCSS’.
3.2.1

An Exact AMM-restricted (0, ⌈log n⌉, 0)-Corpus-compressed Streaming Scheme

One of the most powerful reduction rules discussed in [1] is the merging of isomorphic subgraphs within
non-reduced binary decision diagrams. We extend and apply this idea on order to derive an exact AMMrestricted (0, log n, 0)-CCSS. This section proceeds as follows: we (1) present our scheme, (2) provide a
proof of this scheme’s validity, (3) note a fact about the streaming code length achieved, and (4) provide
a worked example.
Scheme 1 We provide pseudocode for the Construct and Encode procedures of our AMM-restricted
CCSS. Decode is given by Algorithm 3.
Algorithm 2 Construct Routine, Scheme 1
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
28:
29:
30:
31:
32:
33:
34:
35:

procedure Construct(C = {c1 , ..., cn })
STAGE 1:
▷ Construct a MM with a directed tree topology
Initialize D as a Moore machine with a single state S0 .
for i = 1...n do
Set s = S0 .
for j = 1...∣ci ∣ do
Set b to be the jth bit of ci .
if s has no 0-, 1-, or unconditional transition edges then
Add a new state s′ to D which outputs b.
Add an unconditional transition edge from s to s′ .
end if
if s has an unconditional edge to a state s′′ with output 1 − b then
Modify the transition from s to s′′ to be a transition on input symbol 1 − b.
end if
if s does not have a transition edge on input symbol b then
Add a new state s′ to D which outputs b.
Add a transition on input symbol b from s to s′ .
end if
Set s = s(b), where s(b) denotes the state reached following a transition on symbol b.
end for
Add a new node s′ with the special ⊥ output symbol.
Add a transition from s to s′ on end-of-input symbol ⊥.
Mark s′ as a final state.
end for
STAGE 2:
▷ Enumerate states in depth order
Initialize Q as an empty queue.
Initialize L as an empty list of length ∣S∣.
Q.enqueue(S0 )
Set i = 0
while ∣Q∣ > 0 do
Set s = Q.dequeue()
Set L[∣S∣ − i] = s
Set i = i + 1.
For all states s′ such that there is a transition from s to s′ , Q.enqueue(s′ ).
end while

Page 6

Advanced Algorithms Project Report, Spring 2017
Aubrey Alston (ada2145@columbia.edu)

Algorithm 2 Construct Routine (Continued)
36:
37:
38:
39:
40:
41:
42:
43:
44:
45:
46:
47:
48:
49:
50:
51:

STAGE 3:
▷ Apply reduction: merge isomorphic subgraphs
Initialize T as an empty associative array (dictionary).
for i = 1...∣S∣ do
Set s = L[i]. Let s.out denote the output symbol of state s.
Set id = s.out ∣∣ s(0) ∣∣ s(1) ∣∣ s(⊥).
if T [id] = null then
Set T [id] = s.
else
Let r be the single node having a transition to s. (Unless s is S0 , in which case break).
Replace the transition from r to s with a transition on the same symbol to T [id].
Delete s from D.
end if
end for
If S0 has only an unconditional transition to some state s′ , delete S0 and make s′ the start state.
return D,A = ∅.
end procedure

The Construct routine of scheme 1 begins in stage 1 by constructing a Moore machine whose states and
transitions take the form of a directed binary tree having n paths such that following each path produces
a unique string in the corpus set. Starting from a non-output initial state, we iterate through all strings
in the corpus set, bit by bit, branching where strings following the same path diverge. In stage 2, the
procedure prepares for iteration through the states of this Moore machine in order of decreasing depth
from the start state. In stage 3, the procedure merges isomorphic components in the machine using a
light dynamic programming approach. We prove the correctness and properties of this procedure later in
this section.
The encoding procedure of scheme 1 is given as
Algorithm 3 Encode Procedure, Scheme 1
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
12:
13:

procedure Encode(D = Construct(C), A, ci )
If S0 .out == 1 − ci [1], return error.
Set x to be the empty string.
Set s = S0 .
for j = 1...∣ci ∣ do
If s has only an unconditional edge to a state which outputs 1 − ci [j], return error.
If s has no transition to a state which outputs ci [j], return error.
If s has at least one non-unconditional transition, choose a symbol b which leads to a state
which outputs ci [j] and set x = x ∣∣ b.
Set s to be the successor state of s which outputs ci [j].
end for
If s has no ⊥-transition, return error.
return x
end procedure

Encode simply begins at the start state of the machine and records the transitions along a path in D
which outputs the input string ci . We now move to prove that this scheme is indeed a (0, log n, 0) − CCSS
as well as prove its runtime properties.
3.2.1.1

Proving (0, log n, 0)-CCSS Validity

We prove in this section that Scheme 1 is indeed a valid (0, log n, 0)-CCSS.
Page 7

Advanced Algorithms Project Report, Spring 2017
Aubrey Alston (ada2145@columbia.edu)

Lemma 3.1. At the end of stage 1 of Construct, D has a tree topology in which the output along every
path from the root (S0 ) is unique.
Proof: That the graph underlying D is a directed tree is immediate: when a new state is added, it is
given a unique parent; likewise, when a new state is added, it is never given a transition to an existing
state. Because D is a directed tree, there is a unique path from the root to every internal state. Assume
that there exist two of these unique paths P1 and P2 each starting with S0 such that the output along
these paths is equal. Because these paths cannot be the same, there must exist a first point of divergence
along them. But at this point of divergence, there must be two transitions to two distinct states having
the same output, which is impossible by lines 6-19.◻
Lemma 3.2. At the end of stage 1 of Construct, there is a path from root to leaf in D for each ci ∈ C
along which the machine will output ci .
Proof: Assume not; assume that there exists a ci such that there does not exist a path from S0 to a leaf
along which 0/1 outputs correspond to ci at tne end of stage 1. There must exist a least index k from 1
to ∣ci ∣ such that there is a unique (by Lemma 3.1) path from S0 which outputs ci [1], ..., c[k − 1] (or the
empty string if k = 1) but not ci [1], ..., c[k]. During iteration i of line 4, we see that the sequence of the
first k − 1 values of s is precisely this path; since transitions are never deleted, this path must exist at the
end of stage 1. But we see by lines 6-19 that a transition to a state with output c[k], meaning that there
does exist a path with output c[1], ..., c[k], a contradiction.◻
Lemma 3.3. At the end of stage 1, every path from root to leaf in D outputs a string in C.
Proof: By construction, every leaf in D has output symbol ⊥. There are exactly n such leaves added to
D. Since paths in D are unique (D forms a tree), there are exactly n paths from root to leaf in D. By
Lemma 3.2, there must be a path from root to leaf in D which outputs each ci ∈ C. Since there are n
paths among n strings, we conclude that there is a one-to-one correspondence between paths in D and
strings in C. Every path must therefore output a string in C.◻
Lemma 3.4. Let D be a Moore machine whose underlying graph is acyclic, rooted at S0 , in which
⊥-output states are either S0 or nodes without any outbound transitions (leaves). For any state a in D,
let gen(a) be the set of strings which are generated by Da , the machine whose underlying graph is the
directed acyclic subgraph rooted at a (i.e., the set of strings output by D when starting at a and following
any path to a leaf).
For any two distinct states a and b, gen(a) = gen(b) if and only if there exist states x ∈ Da , y ∈ Db
such that Dx is isomorphic to Dy but x ≠ y.
Proof: (⇒). We show that Da ≅ Db implies gen(a) = gen(b) by an inductive argument. Consider first
the case where a and b are leaves. By our choice of D, a and b must be ⊥-output leaves. Therefore
gen(a) = gen(b) = {⊥}, the set containing the empty string. Assume now that Da ≅ Db ⇒ gen(a) = gen(b)
holds for the children of some pair of states x and y in D having Dx ≅ Dy . Because Dx ≅ Dy , the output
bits of x and y, dx and dy , must be equal. Similarly, the subgraphs of the 0-,1-,and ⊥-successors of x
must be respectively isomorphic to those of y, therefore having the same generated set of strings by our
inductive assumption; call these s0 , s1 , s⊥ respectively, and let gen(s⋅ ) = ∅ if the given successor does not
exist.
We may explicitly determine gen(x) as gen(x) = ⋃s⋅ ∈s0 ,s1 ,s⊥ {dx ∣∣ z, ∀z ∈ gen(s⋅ )}. Likewise, gen(y) =
⋃s⋅ ∈s0 ,s1 ,s⊥ {dy ∣∣ z, ∀z ∈ gen(s⋅ )}. Because dx = dy , then, gen(x) = gen(y). Since x ≠ y, we conclude the
proof in this direction.
(⇐). Consider now any distinct states a and b with gen(a) = gen(b) = g. If g contains the one-bit
string dx , then both a and b have ⊥-successors sa⊥ and sb⊥ , both leaves with the same set of generated
strings. If g contains strings which are 1 in the second bit, a and b must each have exactly one successor
with output bit 1, sa1 and sb1 , each generating the subset of g which is 1 in the second bit. Likewise, if g
Page 8

Advanced Algorithms Project Report, Spring 2017
Aubrey Alston (ada2145@columbia.edu)

contains strings which are 0 in the second bit, a and b must each have a successor state with output bit
0, sa0 and sb0 , each generating the subset of g which is 0 in the second bit. (By the same argument, if g
does not contain strings which are 0 in the second bit, neither a nor b have 0-successors; the same holds
for strings which are 1 in the second bit. Thus sa⋅ ≠ ∅ ⇐⇒ sb⋅ ≠ ∅).
Now say that we wish to contradict the statement that there exist x ∈ Da , y ∈ Db such that Dx is
isomorphic to Dy but x ≠ y. Then it must be the case that Dsa1 ≅/ Dsb1 ∨ sa1 = sb1 , Dsa0 ≅/ Dsb0 ∨ sa0 = sb0 ,
and Dsa⊥ ≅/ Dsb⊥ ∨ sa⊥ = sb⊥ . Indeed, equality cannot hold between all successors of a and b, else it would
be trivially true that a and b are isomorphic, and our original statement holds. There must then exist
a ∆ ∈ {0, 1, ⊥} such that sa∆ ≠ sb∆ (whose corresponding subgraphs re not isomorphic). But we have
established that gen(sa∆ ) = gen(sb∆ ), and so we may repeat this argument starting from these two states.
Following this pattern, we may continue until (a) all successors are equal, and we obtain an example, or
(b) are are considering two distinct leaves x′ , in Da , and y ′ , in Db [we may not consider a leaf and a
non-leaf, as it cannot be the case that a leaf and non-leaf generate the same string set]. But, by choice of
D, x′ and y ′ have the same output symbol, and so we simultaneously have x′ ∈ Da , y ′ ∈ Db , x′ ≠ y ′ , and
Dx′ ≅ Dy′ .◻.
Lemma 3.5 (0-Minimality Condition). Fix a corpus set C = {c1 , ..., cn }. Let X be a Moore machine
following the description given in Lemma 3.4 such that each has exactly n paths beginning with S0 and
ending at a leaf and where each such path outputs a unique string in Cn . Let Y be another Moore machine meeting the same requirements. Denote by ∣X∣ and ∣Y ∣ respectively the number of states in X and Y .
∣X∣ < ∣Y ∣ implies that there exist states u and v such that Du ≅ Dv or states w and x such that a
path from S0 to w has the same output as one from S0 to x. As a result, Y is minimal if there are no two
distinct states u and v in Y such that Du ≅ Dv and no two distinct states w and x such that the paths
from S0 to each have the same output.
Proof: We provide a proof by contrapositive. Assume (1) that for all pairs of distinct states u and v in Y ,
Du ≅/ Dv . Then by Lemma 3.4, there do not exist any distinct states u and v in Y having gen(u) = gen(v).
Further, (2) assume that there do not exist any distinct states w and y such that any path from S0 to
either has the same output.
For the sake of contradiction, assume that X has ∣X∣ < ∣Y ∣. By the pidgeonhole principle, there
necessarily exist strings ci and cj and indices k and l such that state sk along the path Pi generating ci
in X is state sl along the path Pj generating cj in X. Without loss of generality, say that sk outputs the
kth bit of ci and that sl outputs the lth bit of cj .
1. The prefix t of ci generated by the sub-path of Pi from S0 to sk in X is also a prefix of cj . But uk
and vk , respectively the states outputing bit k of ci and cj in Y , must necessarily have a path from
the root which outputs this prefix. This contradicts our choice of Y .
2. The substring ti of ci generated by the sub-path of Pi from S0 to sk in X is not a prefix of cj .
Let tj be the substring of cj generated by the sub-path of Pj from S0 to sl = sk in X. Since every
path in X must correspond to a string in C, we have that Qi = {ti ∣∣ q, ∀q ∈ gen(sk )} ⊆ C and
Qj = {tj ∣∣ q, ∀q ∈ gen(sk )} ⊆ C.
By condition (2) on Y , there must exist a unique state ui in Y which generates the substring ti
through which all Qi are generated, and there must exist a unique state vj in Y which generates
the substring tj through which all Qj are generated. This implies that gen(sk ) ⊆ gen(ui ) and also
that gen(sk ) ⊆ gen(vj ). Without loss of generality, say that condition (2) holds also for X (given
an X for which this is not true, we may simply construct one by merging identical prefix paths).
If there exists a string r ∈ gen(vj ) not in gen(sk ), then the string ti ∣∣ r is in C but cannot be
generated by X by condition (2); the same argument holds for strings in gen(ui ). Indeed, then, it
is the case that gen(vj ) = gen(ui ), therefore that there exist a and b such that Da ≅ Db by Lemma
3.4, a contradiction.
.◻.
Page 9

Advanced Algorithms Project Report, Spring 2017
Aubrey Alston (ada2145@columbia.edu)

Theorem 3.1 (Validity of Scheme 1). Scheme 1 is a valid (0, log n, 0)-CCSS.
Proof:
0-correctness We demonstrate that scheme 1 is 0-correct. By lemmas 3.1, 3.2, and 3.3, at the end of stage
1 of Construct, D has a directed tree topology and has exactly one path from root to leaf which outputs
one unique string in Ci . In stage 2 of construct , we order this tree in decreasing order of the depth of
states in D. For each state from root to leaf, we then in stage 3 merge isomorphic components (which
therefore generate the same sets of strings). Because only states generating the same sets of strings are
merged, D preserves both the number of paths and the set of strings generated from the root (the corpus
set).
So long as the string ci given to Encode is a string in C, there exists a path in D returned by Encode
which outputs ci . Further, by the construction of D, there is exactly one path through D for every prefix
of any string, and so the procedure given in lines 5-10 of Encode will generate x as the sequence of nonunconditional inputs needed to generate ci . It follows directly, then, that running D on x (and reading ⊥
at the end of x) will yield ci without any reconstruction error. It thus holds that
∀ci ∈ C,

ham(Decode(D, Encode(D, A, ci )), ci )
≤
∣ci ∣

⌈log n⌉-compression By lemmas 3.1, 3.2, and 3.3, and as we have shown in our demonstration of 0correctness, the schematic returned by Construct has exactly n paths. There can therefore be at most
⌈log n⌉ junctions at which there is more than one transition. At any junction, one of the following must
be true:
1. There is an unconditional transition and a ⊥ transition. Then all that is needed is a single unary
signal indicating to continue. (Include an additional 1 in the input to continue; else end the input
where it is.)
2. There is a 0-transition and a 1-transition. Then all that is needed is a single binary signal indicating
which transition to take.
Since in both cases each junction requires only a one-bit indicator, we conclude that
∀ci ∈ C, ∣Encode(D, ci )∣ ≤ log n
0-minimality Note in the specification of Construct that, for every unique prefix among strings in C, D
has a unique path from S0 to some node x which generates that prefix at the end of stage 1. Thus, for
D (at the end of stage 1), there do not exist w and x such that a path from S0 to w has the same output
as one from S0 to x. Because stage 3 does not add new states or cause any state to generate a new set of
strings (by the argument given in our discussion of 0-correctness), we conclude that the final schematic
D returned maintains this property.
We also claim that the final schematic D returned does not contain any distinct states a and b such
that gen(a) = gen(b). We show this by induction on the depth of states. Base case: consider any two
distinct states a and b with depth greater than or equal to m, the maximum depth of any state in D. a and
b are necessarily leaves, thus also necessarily ⊥-output states. They will both thus have id =⊥∣∣ ∅ ∣∣ ∅ ∣∣ ∅
in stage 3, line 39, and would have been merged. As an inductive hypothesis, assume that there are no
distinct pairs of nodes x and y at depth greater than or equal to k such that gen(x) = gen(y). Say that
there exists a pair a and b at or below depth greater than or equal to k − 1 such that gen(a) = gen(b).
Then gen(a(0)) = gen(b(0)), gen(a(1)) = gen(b(1)), and gen(a(⊥)) = gen(b(⊥)). This implies that the
successors of a respectively generate the same set of strings as the successors of b. But since all of these
successors are at depth greater than ≥ k, they cannot be distinct by the inductive hypothesis. Therefore,
where o is the output symbol of a and b, id = o ∣∣ s(0) ∣∣ s(1) ∣∣ s(⊥) will be equal for these nodes, and so
they would therefore be merged in stage 3 of Construct. We note that the procedure given in stage 3
enforces the invariant of this inductive argument by processing states in decreasing depth order.

Page 10

Advanced Algorithms Project Report, Spring 2017
Aubrey Alston (ada2145@columbia.edu)

By Lemma 3.4, then, the schematic D returned by Construct does not contain any pairs of states
a and b such that Da ≅ Db . Since we have already shown that there do not exist w and x such that a
path from S0 to w has the same output as one from S0 to x in D, we conclude by Lemma 3.5 that D is
minimal, and so
∣D∣
≤1
∣D∗∣

◻.
3.2.1.2

Runtime Analysis

In this section, we show the runtime for all procedures (Encode, Decode, Construct) comprising scheme
1.
Theorem 3.2 (Runtime of Scheme 1 Construct). The Construct(C = {c1 , ..., cn }) routine of Scheme 1
completes in time O(∑ni=1 ∣ci ∣).
Proof: This follows rather directly. Stage 1 of Construct iterates through all bits of all strings in the
corpus set. For each string, it begins at the start state of the current Moore machine, and then for
each bit, it (a) adds or removes at most a constant number of states, (b) modifies a constant number of
transitions, and (c) makes a single transition. Stage 1 therefore takes O(∑ni=1 ∣ci ∣) time; likewise, S has at
most O(∑ni=1 ∣ci ∣) states. Stage 2 is a simple state BFS enumeration of the states of S, therefore taking
time O(∑ni=1 ∣ci ∣). Stage 3 is a pass through the nodes in the order of the enumeration determined in stage
2; in each iteration, an O(1) operation is performed. Thus, the entire procedure takes time O(∑ni=1 ∣ci ∣).
◻.
Theorem 3.3 (Runtime of Scheme 1 Encode). The Encode(D, C, A, ci ) operation of Scheme 1 completes
in time O(∣ci ∣).
Proof: This also follows directly. Note that Encode simply iterates through each bit of ci , during each
iteration making a constant number of (constant-time) chehcks, appending at most 1 bit to a single string,
and taking at most a single transition in D. The entire procedure thus takes time O(∣ci ∣).
◻.
Theorem 3.4 (Runtime of Fixed Decoding Procedure). The fixed decoding procedure Decode(D, x)
completes in time O(∣c∗i ∣), where c∗i is the string that x encodes if it encodes a string or x if it encodes
none.
Proof: When x encodes a string, the Decode procedure is simply an execution of D which outputs the
string ci which x encodes. By the structure of Moore machines, this thus takes time O(∣ci ∣). When x
does not encode a string, some prefix of bits of x are read before the procedure aborts.
◻.
3.2.1.3

A Note on Optimality and a Worked Example

We’ve seen thus far that Scheme 1 is a (0, ⌈log n⌉, 0)-CCSS. From Theorem 2.1, we know that the minimum
possible code length for any corpus set and any CCSS is is bounded from below by log(n + 1) − 1. By
giving Scheme 1 with p(n, z) = ∣log n∣, we have therefore provided a CCSS admitting a streaming code
n
length only additive factor of ⌈log n⌉ − (log (n + 1) − 1) ≤ log n+1
+ 2 from optimal. Noting that this factor
tends towards 2 for large n and is strictly less than 2 for all other n, we also see that this scheme is nearly
optimal with respect to streaming code length in a very strong sense.
The remainder of this section provides and illustrates a worked example of Scheme 1 in order to
motivate questions surrounding how to extend the scheme. Consider the corpus set consisting of the
vowels in the English alphabet (excluding y):
C = {a, e, i, o, u}
Page 11

Advanced Algorithms Project Report, Spring 2017
Aubrey Alston (ada2145@columbia.edu)

For the sake of exposition, say that each of these vowels are given using a naive alphabetical encoding
where any letter is represented by its ordinal position in the English alphabet. We may view our corpus
set now as
C = {a = 1 =

0b00001

e=5=

0b00101

i=9=

0b01001

o = 15 =

0b01111

u = 21 =

0b10101}

Let us say now that we run Construct(C) (for the Construct procedure of Scheme 1) according to
the given pseudo-code. We depict below the Moore machine schematic that would be obtained via this
procedure:

Figure 1: Schematic for C, Output of Scheme 1 Construct
As can be seen in Figure 1 above, the schematic for C in Scheme 1 is an acyclic Moore machine in
11 states. As promised by the validity of scheme 1 as a (0, ⌈log n⌉, 0)-CCSS, we have that we may now
convey vowels in less than or equal to ⌈log n⌉ = 3 bits according to the following stream encoding:
a ∶ 000
e ∶ 001
i ∶ 010
o ∶ 011
u∶1
As we see in the case of this example, scheme 1 portrays the properties of a CCSS that we desired in
order to address the Spotify problem: we see a 40% reduction in the bandwidth required to express vowels
under the given naive encoding without needing to explicitly store the encodings for all vowels.
The reader may perhaps have noticed at this point that there are yet states in 1 that may be merged
to obtain a smaller schematic whilst maintaining the acyclicity property of the restriction. We illustrate
such a merge below:

Page 12

Advanced Algorithms Project Report, Spring 2017
Aubrey Alston (ada2145@columbia.edu)

Figure 2: Modified Schematic
Figure 2 shows that we may merge two states to obtain a smaller schematic (9 states). Note, however, that
this reduction in size increases the number of paths through the machine, meaning that stream encodings
must convey more information. In particular, notice that the above schematic contains a path encoding
42 = 0b101001, not a vowel (not even a letter in our naive encoding); indeed, this schematic no longer
satisfies ⌈log n⌉-compression, as the longest encoding required for any vowel increases from 3 to 5:
a ∶ 000
e ∶ 00101
i ∶ 010
o ∶ 011
u ∶ 1101
While it is certainly true that this schematic no longer satisfies the definition of a (0, ⌈log n⌉, 0)-CCSS,
this modification shows the benefit of increasing p(n, z) for AMM-restricted schemes: if we increase the
maximum encoding length, we may reduce the size of the schematic. This phenomenon motivates our
study of the case where p(n, z) > ⌈log n⌉.
3.2.2

On the Hardness of Maintaining Minimality for a p(n, z) > ⌈log n⌉ AMM-restricted
CCSS

The previous section portrays very clearly the advantage of increasing maximum streaming code length
from the near-optimal point of ⌈logn ⌉: by doing so, we may reduce the size of the schematic. Though this
is an attractive prospect, we will show that this is in fact NP-hard to do while maintaining strict schematic
minimality in virtually all interesting cases. As in the remainder of this work, we are considering strictly
0-correct CCSS constructions.
Specifically, we will show that (i) it is NP-hard to give an AMM-restricted CCSS maintaining 0minimality for unbounded maximum code length p(n, z) and the stronger result that (ii) it is NP-hard
to give an AMM-restricted CCSS maintaining 0-minimality for maximum code length p(n, z) = βz for any
fixed β ≥ 1. We will then extend our discussion to consider the maintenance of δ-minimality for general
δ > 0, formulating a manner in which to relax CCSS constraints to allow us to give CCSS constructions
which still perform well in practice.
Theorem 3.5 (AMM-restriction Hardness for Unbounded Streaming Codes). It is NP-hard to give a
0-minimal, 0-correct AMM-restricted CCSS with unbounded streaming code length (p(n, z) = ∞).
Page 13

Advanced Algorithms Project Report, Spring 2017
Aubrey Alston (ada2145@columbia.edu)

Proof: We show the hardness of this problem via reduction from the well-known NP-hard shortest common supersequence (SCS) problem for binary alphabets (shown to be NP-complete in [5]). The SCS
problem is as follows: given a set of n strings composed of letters from a fixed (binary, in our case) alphabet, determine the shortest possible string s such that each string in the input set is a subsequence of s.
The reduction from SCS to AMM-restricted (0, ∞, 0)-CCSS is direct. Say that we have a (0, ∞, 0)CCSS S = (Construct, Encode, Decode). Consider now an instance I of the SCS problem: I = {c1 , ..., cn }.
As this notation implies, take now I as our corpus set C and run Construct(C = I) to obtain an AMM
schematic D.
By the definition of an AMM-restricted CCSS, D is a Moore machine whose underlying directed graph
is acyclic. Since this graph is acyclic, we may enumerate the states of D in topological order O. Take s as
the string formed by taking the output symbols of each 1- or 0- state in the same order as O. We claim
now that s is a shortest common supersequence of the original instance I, and we show this in two parts:
1. s is a supersequence of all strings in I. Take any string ci ∈ I. Since D is an AMM schematic for
C = I, there exists a path of states through which D outputs ci . The jth state along this path
outputs the jth bit of ci , and the edges along the path which outputs ci must obey the topological
ordering, meaning there is a subsequence of states in the topological ordering O which outputs ci .
Taking s as defined, there is therefore a subsequence of bits in s which is equal to ci ; s is therefore
a supersequence of ci .
2. s is as short as any other supersequence of the strings in I. Assume not. Then there exists a string
s′ shorter than s. We will use this string s′ to construct a new Moore machine D′ : for each bit in
s′ , introduce a new state which outputs the same bit. Next, for each string ci ∈ I, create a path
through these states by adding transitions between states Ej and Ej+1 , respectively corresponding
to the jth and the j + 1th bits of ci , for all j = 1, ...∣ci ∣ − 1. By adding start and end states with the
special symbol ⊥ according to the convention we’ve seen thus far, we obtain a valid Moore machine
D′ which is a valid schematic for I. But D′ has as many states as there are bits in s′ , therefore fewer
states than bits in s and thus fewer states than D, contradicting the 0-minimality of our scheme.
◻.
Theorem 3.6 (AMM-restriction Hardness for βz -bounded Streaming Codes). It is NP-hard to give a
0-minimal, 0-correct AMM-restricted CCSS with streaming code length bounded by p(n, z) = βz for any
fixed β ≥ 1.
Proof: Our proof relies on a result by Jiang and Li in [3] which states that it is NP-hard to approximate the SCS problem with a constant approximation ratio. In particular, we show that the existence
of a (0, βz , 0) AMM-restricted CSS yields a polynomial-time (β + 1)-approximation algorithm for the SCS
problem for any β ≥ 1; the truth of this theorem will then follow from Jiang and Li’s result.
Say that we have a (0, βz , 0) AMM-restricted CSS S for some β ≥ 1. Consider an instance I = {c1 , ..., cn }
of the SCS problem (for binary alphabets). We use S to approximate the shortest common supersequence
of I using the following polynomial-time method:
1. Add to I an all-0 string of polynomial length β(z log2 ∑ni=1 ∣ci ∣ + 1), where z is (as before) the length
of the longest string in I, obtaining a new set of strings I ′ .
2. Run Construct(I ′ ) to obtain an AMM schematic B.
3. Obtain a supersequence s of the strings in I by using the topological ordering method from Theorem
3.5, except this time traversing only the states which are along the output path of some string in
the original set I. Return s.

Page 14

Advanced Algorithms Project Report, Spring 2017
Aubrey Alston (ada2145@columbia.edu)

By the proof of Theorem 3.5, we know that s is at least a supersequence of all the strings in I. All
that remains to show is the optimality gap between s and the true shortest common supersequence of I.
Note that the states of the AMM schematic B may be partitioned into a group of states which (a) are
along the output path for some ci ∈ I but not the path for the string added to obtain I ′ or (b) are along
the output path for the long string added to I. Let the former be D̄, and let the latter be Z. Trivially,
we have ∣B∣ = ∣D̄∣ + ∣Z∣.
Note now that the length of s corresponds to the number of states enumerated in the topological
ordering step: this is equal to all states along an output path for some ci ∈ I, including those also along
the output path for the added string, D̂: ∣D̂∣ = ∣D̄∣+∣D̂ ∩Z∣. The optimal SCS s∗ corresponds (by our proof
of Theorem 3.5) to the number of states in the would-be schematic of a AMM-restricted (0, ∞, 0)-CCSS,
D∗ given by Construct(I).
Because our CCSS is 0-minimal, we know that ∣B∣ is minimized; additionally, since ∣Z∣ is fixed, we
know that ∣D̄∣ is minimized. We note now that D∗ may be converted to an AMM schematic for B ′ by
simply adding one state per bit of the added string. This is true because each state in D∗ has at most
∣D∗ ∣ ≤ ∑ni=1 ∣ci ∣ transitions, meaning that the streaming code gives at most log2 ∑ni=1 ∣ci ∣ bits of information
per transition, therefore that, for the minimum (0, ∞, 0) schematic, at most z log2 ∑ni=1 ∣ci ∣ bits are needed
to represent any string: since our effective z in I ′ is β(z log2 ∑ni=1 ∣ci ∣ + 1), z/β (our maximum encoding
length) is strictly larger than this quantity. Moreover, adding 0-states as mentioned creates exactly one
additional choice at the start node (hence the +1 term), and the resulting schematic B ′ for I ′ intersects
with precisely no states along the output path for strings in I in D∗ .
To continue, given that D∗ may be used to obtain an AMM schematic for I ′ in which the states along
the output paths of strings in I intersect with no states along the output path corresponding to the added
string, we know that ∣D̄∣ ≤ ∣∣D∗ ∣ by the 0-minimality of our CCSS, thus that ∣D̄∣ + ∣D̂ ∩ Z∣ ≤ ∣D∗ ∣ + ∣D̂ ∩ Z∣.
Furthermore, because ∣Z∣ = zβ ≤ β∣D∗ ∣, we can state ∣D̄∣ + ∣D̂ ∩ Z∣ ≤ ∣D∗ ∣(β + 1). Applying this, we see then
that the approximation ratio of this algorithm, given by
∣D̄∣ + ∣D̂ ∩ Z∣
∣D∗ ∣
is in fact
≤
◻.
3.2.2.1

∣D∗ ∣(β + 1)
=β+1
∣D∗ ∣

Considering δ > 0-Minimality

We saw in Theorems 3.5 and 3.6 that it is NP-hard to maintain 0-minimality in an AMM-restricted CCSS
when the streaming code length is either unbounded or bounded as a constant fraction of the length of the
longest string in a corpus set. A natural question to ask now is this: does the problem remain hard when
we relax the δ parameter? I.e., is it hard to maintain δ-minimality when varying code length bound?
We give a result in this section which indicates that the answer to this question is yes. We specifically
rely on yet another result from [3] to show that there exists a natural floor to the maximum value of δ
below which unexpected complexity-theoretic results are implied.
Theorem 3.7 (Minimality Floor of AMM-restricted Schemes). For every β ≥ 1, there exists an α such
that the existence of a (logα n, βz , 0)-CCSS implies that N P ⊆ DT IM E(2polylog(n) ).
Proof: Our proof relies on the following result of Jiang and Li [3]: there exists a constant γ > 0
such that, if SCS has a polynomial-time approximation algorithm with ratio O(logγ n), then N P ⊆
DT IM E(2polylog(n) ). We then need only to show that, for generic β, the existence of a (f (n), β, 0)-CCSS
implies the existence of an O(f (n) + β)-ratio SCS approximation algorithm. The theorem then follows
directly from the result of Jiang and Li.

Page 15

Advanced Algorithms Project Report, Spring 2017
Aubrey Alston (ada2145@columbia.edu)

That a (f (n), β, 0)-CCSS yields an O(f (n)+β)-ratio SCS approximation algorithm follows almost exactly
according to the argument given in the proof of Theorem 3.6 with the following exception: where D̄ is
the set of states along the output paths of the strings of I and D∗ is the set of states in the minimal
AMM schematic, we use the fact that ∣D̄∣ ≤ ∣D∗ ∣ to instead obtain that f (n)∣D̄∣ ≤ f (n)∣D∗ ∣. Introducing
D′ as the corresponding set of states for the schematic returned by the f (n)-minimal scheme, we can
(using the same strategy in the proof of Theorem 3.6) show that ∣D̄′ ∣ + ∣D̂′ ∩ Z∣ ≤ f (n)∣D∗ ∣ + β∣D∗ ∣. The
approximation ratio is immediate.
◻.
3.2.2.2

Relaxing the Problem: from f (⋅)-Minimality to E[f (⋅)]-Minimality

This section overall has shown that analysis of AMM-restricted CCSS constructions through a strict
interpretation of minimality reveals very unyielding hardness results. Theorems 3.5 and 3.6 show us that
it is hard to give CCSS constructions bounding code length as a fraction of maximum string length;
indeed, this hardness will present itself once more if we instead consider code-length bounds p(n, z) as a
function of n on instances where n << z, and so the prospect of exploring this possibility seems equally
grim. Theorem ?? shows us that there is a poly-logarithmic minimality floor under which the prospect
of giving efficient schemes seems unlikely; this is especially daunting when we consider that, in practice,
we would like to see δ-minimality for small, constant values of δ, e.g. 1.25 or 1.5.
More positively, however, the structure of the problem of giving AMM-restricted CCSS constructions
and how closely related it seems to the SCS problem does show some promise for relaxations which
still allow resulting constructions to be useful in practice. In particular, [3] notes that simple greedy
algorithms for the SCS problem yield solutions which are bad in the worst case but are nearly optimal
in the expected case. Toward the end of exploiting this similarity, we suggest the exploration of a new
class of AMM-restricted CCSS constructions: constructions in which minimality is viewed in the expected
case. Where we previously were married to the idea of giving an AMM-restricted (f (⋅), ⋅, ⋅)-CCSS which
is strictly f (⋅)-minimal in all cases, we suggest considering AMM-restricted (E[f (⋅)], ⋅, ⋅) schemes which
is f (⋅)-minimal in the expected case. If the structural similarities with SCS hold to this point, it may
be possible that greedy approaches perform well in the expected case.
Due to the scope of this report and in the interest of being able to touch a broader range of issues related
to MM-restricted CCSS constructions in general, we leave both the formulation of E[f (⋅)]-minimality and
the presentation of algorithms fitting its definition open.

3.3

Restricting Schematics to General Moore Machines

The reader may recall from section 3.2.1.3 that we saw a method of reducing AMM schematic size by
merging states and introducing new paths. In the rest of this report, we do away with the acyclicity
requirement. Now that we have the ability to introduce cycles into the graph underlying our schematics,
we may in fact reduce schematic size even further. Anecdotally, we illustrate how the addition of a single
self-loop reduces the size of the schematic depicted in Figure 2 from 9 to 7:

Page 16

Advanced Algorithms Project Report, Spring 2017
Aubrey Alston (ada2145@columbia.edu)

Figure 3: Schematic with Loop
In truth, the ability to include cycles in our schematics does more than give us the ability to reduce
schematic size: not even the same hardness properties no longer hold. For example, Theorem 3.5 showed
that schematic minimization is NP-hard for unbounded code lengths in the AMM-restricted case; the
relaxed MM-restriction contradicts this directly, as invariably something similar to one of the following
schematics will be optimal:

Figure 4: Cyclic Schematic for Degenerate Case, Unbounded Code Length
Above, we see that an NP-hard instance of CCSS construction problem in the AMM restriction becomes
the degenerate case for the general MM restriction. Owing to potentially significant savings in schematic
size and this significant gap in hardness, we in this section begin to explore the prospect of MM-restricted
CCSS constructions. In the interest of adhering to the expected scope of this report, this exploration is
limited to an informal presentation of an equivalent formulation meant to motivate future study of the
problem.

3.4

An Equivalent Formulation of the Construction Problem

We denote by the construction problem the task of designing the Construct algorithm of a CCSS. In this
section, we informally present an equivalent formulation of the MM-restricted construction problem as a
bicriteria partitioning problem in directed graphs. We then use this formulation as a basis of discussing
directions for continued work.
As stated, we equivalently pose the MM-restricted construction problem as a partitioning problem in
directed graphs. The input for such a problem is a directed acyclic graph F = (V, E), an associated
labeling function L(u) which maps each node in V to a color in {0, 1}, a natural number parameter k, a
natural number parameter τ , and a set of trace-paths P1 , ..., Pm through F . The output desired by this
problem is a disjoint monochromatic (as in each partition is monochromatic) k-partitioning G1 , ..., Gk of
F which satisfies τ in the following specific sense:
Page 17

Advanced Algorithms Project Report, Spring 2017
Aubrey Alston (ada2145@columbia.edu)

• For each trace path Pi , define the partition-path of Pi , p(Pi ), to be the sequence of partitions reached
along the path Pi .
• For each partition Gi , define the degree of Gi , deg(Gi ) to be the number of distinct partitions Gj
such that Gj is the successor of Gi along some partition path.
i
⌈log deg(p(Pi )[j])⌉ ≤ τ .
• We say that a partition G1 , ..., Gk satisfies τ if and only if maxPi ∑j=1

∣P ∣

We omit a formal proof of the correspondence between this formulation and the construction problem
for the sake of maintaining the scope of this report, but we summarize it informally. In the above formulation, k corresponds to the number of states in a schematic, and the parameter τ corresponds to the
maximum streaming code length. The quantity which must satisfy τ corresponds precisely to the length
of the longest streaming code. Thus, to give an MM-restricted (0, p(n, z), 0)-CCSS, we would solve the
given problem for the minimum k yielding a partition satisfying p(n, z). Again, we note that we leave the
formal proof of this correspondence open. 2
This formulation is useful because it gives us a natural framework in which to develop schematic minimization algorithms, but it is also useful for the sake of analyzing hardness as we did for the AMM-restricted
schemes. We can see this, for example, even in an ability to view hardness of the AMM-restricted case
through the lens of this formulation: if we impose a partial acyclicity constraint, namely dictating that
there must not exist edges with start- and end-points in the same partition, the above formulation reduces to the problem of determining the chromatic number of an arbitrary undirected graph (when τ is
unbounded).
Focusing once more on the MM-restricted case, our hope is that this formulation makes it possible to
analyze the limits of MM-restricted schemes in a natural way. We leave the problem of this analysis open,
but we note that other similar partitioning problems [2] are both hard to solve exactly and approximately.
We additionally hope that this formulation simplifies the task of developing specific MM-restricted CCSS
constructions, but we leave also this problem open.

4

Future Work

We have in this work explored the surface of corpus-compressed streaming as a solution to the Spotify
problem, substantiating a particular strategy which utilizes regular function automata as schematics.
Even with respect to this strategy, our concrete results are limited to the development of a single AMMrestricted (0, ⌈log n⌉, 0)-CCSS and a few hardness results for this specific restriction. While our discussion
has touched on extensions of this strategy, our work nonetheless leaves open quite a few questions which
seem worthwhile to explore in the future. We outline these areas for future work below.
• Lossy Reconstruction All of our schemes, hardness results, and discussion thus far have been
restricted to consideration of lossless schemes having the  parameter fixed at 0. Future work
could consider developing new lossless CCSS constructions, extending the AMM-restricted scheme
we’ve developed to make strategic use of loss, or even seeking to extend or refine our hardness results
in the lossless case.
• Expected Minimality In our presentation of results for AMM-restricted schemes, we noted the
possible utility of developing a notion of expected-case minimality rather than strict minimality of
a CCSS. Future work could look at giving a precise formulation of this notion and, moreover, using
it to construct practically useful schemes with p(n, z) varied away from ⌈log n⌉.
• Taking Other Parameters in Expectation Related to the previous point, it seems natural to also
consider the benefit of also taking the maximum streaming code length and loss parameters in
expectation.
2 Indeed, the problem which corresponds exactly requires a slight modification in that the input graph must support
having a constant number of unlabeled nodes, but we leave this out for ease of exposition.

Page 18

Advanced Algorithms Project Report, Spring 2017
Aubrey Alston (ada2145@columbia.edu)

• MM-restricted Schemes The last section gave an overview of the benefits of studying MM-restricted
constructions. Future work in this area could look at formally proving properties of these constructions (potentially using the equivalent formulation we have provided) or, perhaps more importantly,
developing MM-restricted schemes.
• Schemes from Other Function Automata This work has focused exclusively on constructing schematics from regular function automata. While the hardness results we found at this level of the hierarchy
may be a deterrent from any attempt at operating at a higher level, studying what happens when
we do could nonetheless be worthwhile.
• Other Restriction Constraints Related to the previous, it would of course be worthwhile to consider
other means of restricting schematics independent of language considerations. One particular area
of interest could be exploring restrictions of schematics to auto-encoders with specific properties.
• Practical Evaluation of Schemes Outside of the realm of theory, one major area of future work
concerns the implementation and evaluation of CCSS constructions on real-world data and in realworld environments.

5

Conclusion

In this work, we have defined the Spotify problem and explored a potential solution in the form of a
new algorithmic goal which we refer to as corpus-compressed streaming schemes. After formally
substantiating the notion of a corpus-compressed streaming scheme, we explored a specific strategy of
constructing them based upon a Kolmogorov-like use of regular function automata as an ‘almost selfextracting’ archive. Following a presentation of results including a concrete, nearly optimal scheme (under
a specific restriction) and hardness properties, we further motivate and outline opportunities for future
work in this area.

References
[1] Bryant, R. E. Graph-based algorithms for boolean function manipulation. IEEE Trans. Comput.
35, 8 (Aug. 1986), 677–691.
[2] Feldmann, A. E. Fast Balanced Partitioning Is Hard Even on Grids and Trees. Springer Berlin
Heidelberg, Berlin, Heidelberg, 2012, pp. 372–382.
[3] Jiang, T., and Li, M. On the approximation of shortest common supersequences and longest common
subsequences. Springer Berlin Heidelberg, Berlin, Heidelberg, 1994, pp. 191–202.
[4] Li, M., and Vitnyi, P. M. An Introduction to Kolmogorov Complexity and Its Applications, 3 ed.
Springer Publishing Company, Incorporated, 2008.
[5] Rih, K.-J., and Ukkonen, E. The shortest common supersequence problem over binary alphabet
is np-complete. Theoretical Computer Science 16, 2 (1981), 187 – 198.

Page 19

