BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/786
DTSTAMP:20230914T125938Z
SUMMARY:Streaming Complexity of Approximating Max 2CSP and Max Acyclic Subg
raph
DESCRIPTION:Speaker: Santhoshini Velusamy (VSRP Student\nIndian Institute o
f Technology\nChennai 600036)\n\nAbstract: \nThis paper is joint work with
Venkatesan Guruswami and Ameya Vellingker\, to appear in APPROX 17.\n\nW
e studied the complexity of estimating the optimum value of a Boolean 2CSP
(arity two constraint satisfaction problem) in the single-pass streaming
setting\, where the algorithm is presented the constraints in an arbitrary
order. We give a streaming algorithm to estimate the optimum within a fac
tor approaching 2/5 using logarithmic space\, with high probability. This
beats the trivial factor 1/4 estimate obtained by simply outputting 1/4 th
of the total number of constraints.\n\nThe inspiration for our work is a
lower bound of Kapralov\, Khanna\, and Sudan (SODA '15) who showed that a
similar trivial estimate (of factor 1/2) is the best one can do for Max CU
T. This lower bound implies that beating a factor 1/2 for Max 2CSP\, in pa
rticular\, to distinguish between the case when the optimum is m/2 versus
when it is at most (1/4+ \\eps) m\, where m is the total number of constra
ints\, requires polynomial space. We complement this hardness result by sh
owing that one can distinguish between the case in which the optimum excee
ds (1/2 + \\eps)m and the case in which it is close to m/4.\n\nWe also pro
ve that estimating the size of the maximum acyclic subgraph of a graph\, w
hen its edges are presented in a single-pass stream\, within a factor bett
er than 7/8 requires polynomial space.\n\nIn this talk\, I'll present the
main results of the paper. The proofs are quite simple and would not requi
re any previous knowledge\n \n
URL:https://www.tcs.tifr.res.in/web/events/786
DTSTART;TZID=Asia/Kolkata:20170616T171500
DTEND;TZID=Asia/Kolkata:20170616T181500
LOCATION:A-201 (STCS Seminar Room)
END:VEVENT
END:VCALENDAR