BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1795
DTSTAMP:20261104T053650Z
SUMMARY:Local Spectral Expansion: Pseudoindependence\, Chernoff Bounds\, an
 d Constructions
DESCRIPTION:Speaker: Arka Ray (IISc Bengaluru)\n\nAbstract: \nThe notion of
  expansion has been one of the most effective ways to quantify connectivit
 y in graphs\, with applications throughout theoretical computer science. H
 owever\, generalizing this notion to hypergraphs has been extremely challe
 nging\, and the most natural generalization has not proven helpful for app
 lications such as algorithm design\, coding\, hardness of approximation\, 
 and pseudorandomness. Recently\, local spectral expansion (also known as h
 igh-dimensional expansion) has emerged as a promising notion of expansion 
 in hypergraphs.\nIn this talk\, we will first look at the notion of local 
 spectral expansion (and a related notion called approximate product space)
  through the lens of 'pseudoindependence'. To this end\, we will define th
 e notion of simplicial complexes and walks on them and briefly examine the
  relation between their spectra and local spectral expansion. We will end 
 this exposition with a discussion of the celebrated trickle-down theorem.\
 nThen\, to firmly establish local spectral expansion as a useful relaxatio
 n of independence\, we will look at a few versions of the Chernoff bounds 
 for approximate product spaces and local spectral expansion. The proof for
  approximate product spaces will be through a direct bound on the moment g
 enerating function (MGF). The bound for the case of local spectral expansi
 on will be through a bound on the variance\, giving us a bound on the seco
 nd derivative of the log-MGF.\nFinally\, we will look at a few constructio
 ns of sparse local spectral expanders.\n
URL:https://www.tcs.tifr.res.in/web/events/1795
DTSTART;TZID=Asia/Kolkata:20261111T160000
DTEND;TZID=Asia/Kolkata:20261111T170000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR