BEGIN:VCALENDAR VERSION:2.0 PRODID:researchseminars.org CALSCALE:GREGORIAN X-WR-CALNAME:researchseminars.org BEGIN:VEVENT SUMMARY:Santhoshini Velusamy (Harvard University) DTSTART:20210512T170000Z DTEND:20210512T180000Z DTSTAMP:20260423T021008Z UID:TCSPlus/24 DESCRIPTION:Title: Classification of the approximability of all finite Max-CSPs in the dynam ic streaming setting\nby Santhoshini Velusamy (Harvard University) as part of TCS+\n\n\nAbstract\nA maximum constraint satisfaction problem\, Ma x-CSP(F)\, is specified by a finite family of constraints F\, where each c onstraint is of arity k. An instance of the problem on n variables is give n by m applications of constraints from F to length-k subsequences of the n variables\, and the goal is to find an assignment to the n variables tha t satisfies the maximum number of constraints. The class of Max-CSP(F) inc ludes optimization problems such as Max-CUT\, Max-DICUT\, Max-3SAT\, Max-q -Coloring\, Unique Games\, etc.\n\nIn this talk\, I will present our recen t dichotomy theorem on the approximability of Max-CSP(F) for every finite family F\, in the single-pass dynamic streaming setting. In this setting\, at each time step\, a constraint is either added to or deleted from the s tream. In the end\, the streaming algorithm must estimate the maximum numb er of constraints that can be satisfied using space that is only polylogar ithmic in n. No background in streaming algorithms or constraint satisfact ion problems will be needed to enjoy this talk!\n\nThe talk will be based on this paper (https://eccc.weizmann.ac.il/report/2021/011/)\, and this pa per (https://eccc.weizmann.ac.il/report/2021/063/) with Chi-Ning Chou\, Al exander Golovnev\, and Madhu Sudan.\n LOCATION:https://researchseminars.org/talk/TCSPlus/24/ END:VEVENT END:VCALENDAR