BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/765
DTSTAMP:20230914T125937Z
SUMMARY:Universal Lossless Compression of Graph-indexed Data
DESCRIPTION:Speaker: Venkat Anantharam (University of California at Berkele
y\nDepartment of Electrical Engineering\nand Computer Science\n271 Cory Ha
ll\nBerkeley\, California 94720-1770\nUnited States of America)\n\nAbstrac
t: \nMany modern data sources arising from social networks\, biological da
ta\, etc. are best viewed as indexed by combinatorial structures such as g
raphs\, rather than as time series. The local weak limit theory for sparse
graphs\, also known as the objective method\, provides a framework in whi
ch to make sense of what one might mean by a stationary stochastic process
indexed by graphs. The theory of time series is the engine driving an eno
rmous range of applications in areas such as control theory\, communicatio
ns\, information theory and signal processing\, to name just a few elds. I
t is to be expected that a theory of stationary stochastic processes index
ed by combinatorial structures\, in particular graphs\, would eventually h
ave a similarly wide ranging impact.\n\nConsider a graph whose vertices an
d edges carry marks\, viewed as data samples associated to the vertex or t
he edge respectively. For example the vertices might be individuals\, the
vertex mark might describe the musical taste of the individual and the edg
e mark might describe the degree of anity between the corresponding pair o
f individuals. We pose the problem of representing the information content
of such a marked graph in the most ecient way possible. Further\, we woul
d like to do this in a universal sense\, i.e.\, in eect\, without making a
ny statistical assumptions about the data sample being compressed. It turn
s out that one can make precise sense of this question in the language of
the local weak limit theory\, the only assumption being that the graph is
sparse\, i.e. that the number of edges is on the same scale as the number
of vertices. What is more\, the compression can be done in the most ecient
way possible. Namely one can make sense of a notion of entropy associated
to the local weak limit\, which is on a linear scale in the number of nod
es\, and one can compress down to this entropy in a universal sense. The e
ntropy notion we work with is a generalized version of the one introduced
by Bordenave and Caputo (2014).\n\nAll the necessary background from the t
heory of local weak limits that is needed will be developed during the tal
k (joint work with Payam Delgosha).\n
URL:https://www.tcs.tifr.res.in/web/events/765
DTSTART;TZID=Asia/Kolkata:20170330T160000
DTEND;TZID=Asia/Kolkata:20170330T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR