BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/807
DTSTAMP:20230914T125939Z
SUMMARY:Is Submodularity Testable?
DESCRIPTION:Speaker: Gunjan Kumar\n\nAbstract: \nWe initiate the study of p
roperty testing of submodularity on the boolean hypercube. Submodular func
tions come up in a variety of applications in combinatorial optimization.
For a vast range of algorithms\, the existence of an oracle to a submodula
r function is assumed. But how does one check if this oracle indeed repres
ents a submodular function?\n\nConsider a function $f:\\{0\,1\\}^n \\right
arrow \\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 tha
t\, given input $f$ that is $\\epsilon$-far from being submodular\, certif
ies 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 fi
rst non-trivial tester for submodularity. On the other hand\, we prove an
interesting lower bound (that is\, unfortunately\, quite far from the uppe
r 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.\n\nThis
result appears in Algorithmica 2014 titled `Is Submodularity Testable?' by
C.Seshadhri and Jan Vondrak.\n
URL:https://www.tcs.tifr.res.in/web/events/807
DTSTART;TZID=Asia/Kolkata:20170908T171500
DTEND;TZID=Asia/Kolkata:20170908T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR