The Index function and the space complexity of Dyck languages
| Speaker: | Ashwin Nayak |
|---|---|
| Affiliation: | University of Waterloo |
| Room: | Mathematics & Computer Building (MC) 5158 |
Abstract:
Streaming algorithms access the input sequentially, one symbol at a time, a small number of times, while attempting to solve some information processing task. The goal is to process massive data using as little space and time as possible. Streaming algorithms that use constant space and time per input symbol recognize precisely the class of regular languages.
Following
Magniez,
Mathieu,
and
Nayak,
we
study
the
streaming
complexity
of
Dyck
languages,
prototypical
languages
in
the
next
level
of
the
Chomsky
hierarchy.
We
show
an
Omega(sqrt(n)/T)
lower
bound
for
the
space
required
by
any
constant-error
randomized
streaming
algorithm
for
Dyck(2)
that
make
T
passes
over
the
input,
all
in
the
same
direction.
This
proves
a
conjecture
due
to
Magniez
et
al.
and
rigorously
establishes
the
peculiar
power
of
bi-directional
streams
over
unidirectional
ones
reflected
in
their
algorithms.
The
space
lower
bound
is
obtained
by
reducing
the
problem
to
one
in
communication
complexity,
involving
the
so-called
Index
function.
It
rests
on
the
information
necessarily
revealed
by
each
party
about
her
input
in
a
two-party
communication
protocol
for
a
variant
of
the
Index
function.
We
show
that
either
one
party
reveals
Omega(n)
information
about
her
n-bit
input,
or
the
other
party
reveals
Omega(1)
information
about
a
(log
n)-bit
input.
We
show
similar
results
in
the
quantum
analogues
of
the
streaming
and
communication
models.
Joint
work
with
Rahul
Jain
(CQT
and
NUS,
Singapore).