Interlacing families: a new technique for controlling eigenvalues
| Speaker: | Adam Marcus |
|---|---|
| Affiliation: | Yale and Crisply Inc. |
| Room: |
Institute
for
Quantum
Computing
(IQC)
0101
|
Abstract:
Matrices
are
one
of
the
most
fundamental
structures
in
mathematics,
and
it
is
well
known
that
the
behavior
of
a
matrix
is
dictated
by
its
eigenvalues.
Eigenvalues,
however,
are
notoriously
hard
to
control,
due
in
part
to
the
lack
of
techniques
available.
In
this
talk,
I
will
present
a
new
technique
that
we
call
the
"method
of
interlacing
polynomials"
which
has
been
used
recently
to
give
unprecedented
bounds
on
eigenvalues,
and
as
a
result,
new
insight
into
a
number
of
old
problems.
I
will
discuss
some
of
these
recent
breakthroughs,
which
include
the
existence
of
Ramanujan
graphs
of
all
degrees,
a
resolution
to
the
famous
Kadison-Singer
problem,
and
most
recently
an
incredible
result
of
Anari
and
Gharan
on
the
traveling
salesman
problem
that
has
produced
an
interesting
anomaly
in
computer
science.
This
talk
will
be
directed
at
a
general
mathematics
audience
and
represents
joint
work
with
Dan
Spielman
and
Nikhil
Srivastava.