BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/687
DTSTAMP:20230914T125934Z
SUMMARY:Approximate Modularity
DESCRIPTION:Speaker: Anirban Dasgupta (Indian Institute of Technology\, Gan
 dhinagar\nComputer Science Department\nPalaj\nGujarat 382355)\n\nAbstract:
  \nA set function on a ground set of size n is approximately modular if it
  satisfies every modularity requirement to within an additive error\;appro
 ximate modularity is the set analog of approximate linearity. In this work
  we study how close\, in additive error\, can approximately modular functi
 ons be to truly modular functions. While approximately linear functions ha
 ve been extensively studied in the literature\, there has been no study on
  approximate modularity to the best of our knowledge.\n\nWe first obtain p
 olynomial time algorithms that\, given any approximately modular function\
 , reconstructs a modular function that is $O(n^{1/2})$ close. We also show
  an almost matching lower bound. In a striking contrast to these near-tigh
 t computational reconstruction bounds\, we then show that for any approxim
 ately modular function\, there exists a modular function that is $O(\\log 
 n)$-close (joint work with Flavio Chiericetti\, Abhimanyu Das\, Ravi Kumar
  in Proceedings of FOCS 2015).\n
URL:https://www.tcs.tifr.res.in/web/events/687
DTSTART;TZID=Asia/Kolkata:20160524T110000
DTEND;TZID=Asia/Kolkata:20160524T120000
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR