Approximate Modularity

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).