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