Janani Sundaresan, a PhD candidate at the Cheriton School of Computer Science, has been awarded a Faculty of Mathematics Graduate Research Excellence Award. Conferred annually to two graduate students who have authored or coauthored an outstanding research paper, the prestigious recognition comes with a prize of $5,000.

Janani’s
paper
titled
“Hidden
Permutations
to
the
Rescue:
Multi-Pass
Semi-Streaming
Lower
Bounds
for
Approximate
Matchings”
was
co-authored
with
her
doctoral
advisor
Professor
Sepehr
Assadi.
It
was
presented
at
FOCS
2023,
the
64^{th}
IEEE
Symposium
on
Foundations
of
Computer
Science,
one
of
the
two
top
international
conferences
in
theoretical
computer
science.

Janani’s paper makes substantial progress on a longstanding open question regarding the maximum matching problem in the semi-streaming model. The maximum matching problem is the problem of finding the largest number of edges in a given graph that do not share any vertices. As an application, consider finding a pairing of a set of items to a set of interested buyers in a way that each buyer receives at most one item and each item is allocated to at most one buyer. This application can be modelled as an instance of the maximum matching problem on a graph between items and buyers, with edges showing which buyer is interested in which item. The maximum matching problem has been a cornerstone of algorithmic research for almost a century, including pioneering work by Jack Edmonds and William Tutte, mathematicians both formerly affiliated with the University of Waterloo.

The
semi-streaming
model
is
a
model
of
computation
tailored
toward
processing
massive
graphs.

In
the
classical
view
of
algorithms,
often
referred
to
as
the
von
Neumann
model,
we
assume
that
our
algorithms
have
random-access
to
every
part
of
the
input
at
a
unit
cost.
This
model,
however,
can
be
unrealistic
when
working
with
inputs
that
are
too
large
to
be
stored
in
the
main
memory
of
the
computer.
Instead,
in
such
scenarios,
one
typically
only
has
sequential
access
to
the
input
—
say,
stored
in
the
hard-drive
of
the
computer
which
allows
a
fast
sequential
access
but
a
slow
random
access
—
and
needs
to
process
it
with
a
memory
much
smaller
than
the
input
size
—
say,
corresponding
to
the
main
memory
of
the
computer,
which
is
typically
much
smaller
than
its
hard-drive.
The
semi-streaming
model
precisely
captures
this
scenario.
Specifically,
a
semi-streaming
algorithm
needs
to
process
its
input
by
making
one
or
a
few
passes
over
the
edges
of
the
input
graph
and
use
a
limited
memory,
proportional
only
to
the
number
of
vertices
in
the
graph
as
opposed
to
the
potentially
much
larger
number
of
edges.

Janani’s paper now considers the following question: does finding even a near-optimal maximum matching in the semi-streaming model require making a substantial number of passes over the input? Stated more formally, the paper asks how many passes are needed to find a (1 + ϵ)-approximation of maximum matching as a function of ϵ.

Given the central role of the maximum matching problem in algorithm design and its wide range of applications, this problem has received significant attention since the introduction of the semi-streaming model almost two decades ago. Yet, almost no progress has been made on the open question except for one- or two-pass algorithms. Janani’s paper, on the other hand, proves the following result:

*
Any
semi-streaming
algorithm
for
finding
a
(1+ϵ)-approximation
of
maximum
matching
requires
Ω
(log
(1/ϵ))
passes,
even
for
ϵ
=
θ(1).
The
lower
bound
holds
assuming
a
natural
combinatorial
hypothesis
regarding
the
density
of
the
so-called
Ruzsa-Szemeredi
graphs
in
extremal
graph
theory. *

Consequently,
while
we
might
still
not
know
the
*
optimal*
pass-dependence
on
the
parameter
ϵ,
this
is
the
first
time
that
we
have
any
evidence
toward
necessity
of
any
dependence
at
all
on
this
parameter,
Professor
Assadi
explained.

“To put this result in perspective, before Janani’s work, we only knew that maximum matching cannot be solved in one or two passes over the input,” Professor Assadi said. “Thus, it was entirely conceivable that this problem could have been solved by making, say, just three passes over the input, regardless of how accurate an approximate solution we aimed for. On the other hand, Janani’s result now proves that, under a natural combinatorial hypothesis, no constant number of passes, say, even a hundred or a thousand, suffices for solving this problem, as long as we require a sufficiently accurate solution.”

To
learn
more
about
this
award-winning
research,
please
see
Sepehr
Assadi
and
Janani
Sundaresan,
“Hidden
Permutations
to
the
Rescue:
Multi-Pass
Streaming
Lower
Bounds
for
Approximate
Matchings,”
*
2023
IEEE
64 ^{th}
Annual
Symposium
on
Foundations
of
Computer
Science
(FOCS)*,
Santa
Cruz,
CA,
USA,
2023,
pp.
909–932.