Tata Institute of Fundamental Research
Approximate Modularity
STCS Colloquium
Speaker:
Anirban Dasgupta (Indian Institute of Technology, Gandhinagar
Computer Science Department
Palaj
Gujarat 382355)
Organiser:
Prahladh Harsha
Date:
Tuesday, 24 May 2016, 11:00 to 12:00
Venue:
A-201 (STCS Seminar Room)
(Scan to add to calendar)
Abstract:
A set function on a ground set of size n is approximately modular if it satisfies every modularity requirement to within an additive error;approximate modularity is the set analog of approximate linearity. In this work we study how close, in additive error, can approximately modular functions be to truly modular functions. While approximately linear functions have been extensively studied in the literature, there has been no study on approximate modularity to the best of our knowledge.
We first obtain polynomial 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-tight computational reconstruction bounds, we then show that for any approximately 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).
| Speaker: | Anirban Dasgupta (Indian Institute of Technology, Gandhinagar Computer Science Department Palaj Gujarat 382355) |
| Organiser: | Prahladh Harsha |
| Date: | Tuesday, 24 May 2016, 11:00 to 12:00 |
| Venue: | A-201 (STCS Seminar Room) |
(Scan to add to calendar)
Abstract:
A set function on a ground set of size n is approximately modular if it satisfies every modularity requirement to within an additive error;approximate modularity is the set analog of approximate linearity. In this work we study how close, in additive error, can approximately modular functions be to truly modular functions. While approximately linear functions have been extensively studied in the literature, there has been no study on approximate modularity to the best of our knowledge.
We first obtain polynomial 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-tight computational reconstruction bounds, we then show that for any approximately 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).
We first obtain polynomial 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-tight computational reconstruction bounds, we then show that for any approximately 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).