BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/829
DTSTAMP:20230914T125940Z
SUMMARY:Agreement Tests on Graphs and Hypergraphs
DESCRIPTION:Speaker: Prahladh  Harsha\n\nAbstract: \nAgreement tests are a 
 generalization of low degree tests that capture a local-to-global phenomen
 on\, which forms the combinatorial backbone of most PCP constructions. In 
 an agreement test\, a function is given by an ensemble of local restrictio
 ns. The agreement test checks that the restrictions agree when they overla
 p\, and the main question is whether average agreement of the local pieces
  implies that there exists a global function that agrees with most local r
 estrictions.\n\nThere are very few structures that support agreement tests
 \, essentially either coming from algebraic low degree tests or from direc
 t product tests (and recently also from high dimensional expanders). In th
 is talk\, we will discuss a new agreement theorem which extends direct pro
 duct tests to higher dimensions\, analogous to how low degree tests extend
  linearity testing. An immediate corollary of this agreement theorem we ob
 tain the following: an ensemble of small graphs on overlapping sets of ver
 tices can be glued together to one global graph assuming they agree with e
 ach other on average.\n\nA key technical step in our proof is a new hyperg
 raph pruning lemma which allows us to treat dependent events as if they ar
 e disjoint\, and may be of independent interest (joint work with Irit Dinu
 r and Yuval Filmus).\n
URL:https://www.tcs.tifr.res.in/web/events/829
DTSTART;TZID=Asia/Kolkata:20171130T113000
DTEND;TZID=Asia/Kolkata:20171130T123000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR