Speaker: |
Gunjan Kumar |

Organiser: |
Sayantan Chakraborty |

Date: |
Friday, 8 Sep 2017, 17:15 to 18:15 |

Venue: |
A-201 (STCS Seminar Room) |

(Scan to add to calendar)

Consider a function $f:\{0,1\}^n \rightarrow \mathbb{R}$. The distance to submodularity is the minimum fraction of values of $f$ that need to be modified to make $f$ submodular. If this distance is more than $\epsilon > 0$, then we say that $f$ is $\epsilon$-far from being submodular. The aim is to have an efficient procedure that, given input $f$ that is $\epsilon$-far from being submodular, certifies that $f$ is not submodular. We analyze a very natural tester for this problem, and prove that it runs in subexponential time. This gives the first non-trivial tester for submodularity. On the other hand, we prove an interesting lower bound (that is, unfortunately, quite far from the upper bound) suggesting that this tester cannot be very efficient in terms of $\epsilon$.This involves non-trivial examples of functions which are far from submodular and yet do not exhibit too many local violations.

This result appears in Algorithmica 2014 titled `Is Submodularity Testable?' by C.Seshadhri and Jan Vondrak.