BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//128.220.13.64//NONSGML kigkonsult.se iCalcreator 2.20//
CALSCALE:GREGORIAN
METHOD:PUBLISH
X-WR-CALNAME:Johns Hopkins Algorithms and Complexity
X-WR-CALDESC:
X-FROM-URL:https://www.cs.jhu.edu/~mdinitz/theory
X-WR-TIMEZONE:America/New_York
BEGIN:VTIMEZONE
TZID:America/New_York
X-LIC-LOCATION:America/New_York
BEGIN:STANDARD
DTSTART:20221106T020000
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
TZNAME:EST
END:STANDARD
BEGIN:DAYLIGHT
DTSTART:20220313T020000
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
RDATE:20230312T020000
TZNAME:EDT
END:DAYLIGHT
END:VTIMEZONE
BEGIN:VEVENT
UID:ai1ec-332@www.cs.jhu.edu/~mdinitz/theory
DTSTAMP:20221001T204002Z
CATEGORIES:
CONTACT:
DESCRIPTION:Speaker: Aditya Krishnan\nAffiliation: Johns Hopkins University
\nTitle: Schatten Norms in Matrix Streams: The Role of Sparsity. \nAbstra
ct: Spectral functions of large matrices contain important structural inf
ormation about the underlying data\, and are thus becoming increasingly im
portant to efficiently compute. Many times\, large matrices representing r
eal-world data are \\emph{sparse} or \\emph{doubly sparse} (i.e.\, sparse
in both rows and columns)\, and are accessed as a \\emph{stream} of update
s\, typically organized in \\emph{row-order}. In this setting\, where spac
e (memory) is the limiting resource\, all known algorithms require space t
hat is polynomial in the dimension of the matrix\, even for sparse matrice
s. We address this challenge by providing the first algorithms whose space
requirement is \\emph{independent of the matrix dimension}\, assuming the
matrix is doubly-sparse and presented in row-order. \nIn addition\, we pr
ove that multiple passes are unavoidable in this setting and show extensio
ns of our primary technique\, including a trade-off between space requirem
ents and number of passes. Our algorithms approximate the Schatten p-norms
\, which we use in turn to approximate other spectral functions\, such as
logarithm of the determinant\, trace of matrix inverse\, and Estrada index
. \nJoint work with Vladimir Braverman\, Robert Krauthgamer and Roi Sinoff
.
DTSTART;TZID=America/New_York:20201007T120000
DTEND;TZID=America/New_York:20201007T130000
LOCATION:https://wse.zoom.us/j/91450299380
SEQUENCE:0
SUMMARY:[Theory Seminar] Aditya Krishnan
URL:https://www.cs.jhu.edu/~mdinitz/theory/event/theory-seminar-aditya-kris
hnan-2/
X-COST-TYPE:free
X-ALT-DESC;FMTTYPE=text/html:\\n\\n\\n\\n\\nSpeaker: Adit
ya Krishnan

\nAffiliation: Johns Hopkins University

\nTitle: Sc
hatten Norms in Matrix Streams: The Role of Sparsity.

\nAbstract:
Spectral functions of large matrices contain important structural informa
tion about the underlying data\, and are thus becoming increasingly import
ant to efficiently compute. Many times\, large matrices representing real-
world data are \\emph{sparse} or \\emph{doubly sparse} (i.e.\, sparse in b
oth rows and columns)\, and are accessed as a \\emph{stream} of updates\,
typically organized in \\emph{row-order}. In this setting\, where space (m
emory) is the limiting resource\, all known algorithms require space that
is polynomial in the dimension of the matrix\, even for sparse matrices. W
e address this challenge by providing the first algorithms whose space req
uirement is \\emph{independent of the matrix dimension}\, assuming the mat
rix is doubly-sparse and presented in row-order.

\nIn addition\, we
prove that multiple passes are unavoidable in this setting and show exten
sions of our primary technique\, including a trade-off between space requi
rements and number of passes. Our algorithms approximate the Schatten p-no
rms\, which we use in turn to approximate other spectral functions\, such
as logarithm of the determinant\, trace of matrix inverse\, and Estrada in
dex.

\nJoint work with Vladimir Braverman\, Robert Krauthgamer and
Roi Sinoff.

\n
END:VEVENT
END:VCALENDAR