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 64th IEEE Symposium on Foundations of Computer Science, one of the two top international conferences in theoretical computer science.
Left
to
right:
Janani
Sundaresan
and
Sepehr
Assadi
Janani
Sundaresan
is
a
PhD
student
in
the
computer
science
theory
group
at
the
Cheriton
School
of
Computer
Science.
She
is
interested
in
sublinear
and
streaming
algorithms,
online
algorithms
and
more
broadly
optimization
problems.
Recently,
she
has
focused
on
proving
lower
bounds
for
streaming
algorithms.
Sepehr
Assadi
is
an
Associate
Professor
and
a
Faculty
of
Mathematics
Research
Chair
at
the
Cheriton
School
of
Computer
Science.
His
research
interest
is
in
theoretical
computer
science
and
primarily
algorithm
design
and
complexity
theory
for
modern
models
of
computation.
This
includes
sublinear
algorithms
and
lower
bounds
in
various
models
for
processing
massive
datasets
such
as
streaming,
distributed,
massively
parallel,
and
sublinear
time
algorithms.
He
is
also
interested
in
graph
theory,
communication
complexity,
online
algorithms,
and
algorithmic
game
theory.
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 64th Annual Symposium on Foundations of Computer Science (FOCS), Santa Cruz, CA, USA, 2023, pp. 909–932.