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