BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1705
DTSTAMP:20260408T084515Z
SUMMARY:On Approximability of Satisfiable CSPs & Applications (extended ver
 sion)
DESCRIPTION:Speaker: Amey Bhangale (UNIVERSITY OF CALIFORNIA)\n\nAbstract: 
 \nThe satisfiability problem for Constraint Satisfaction Problems (CSPs) a
 sks whether a CSP instance admits an assignment that satisfies all constra
 ints. For a k-ary predicate P:[q]^k -> {0\,1}\, where P(x)=1 iff x satisfi
 es the constraint\, the problem CSP(P) consists of constraints obtained by
  applying P to ordered k-tuples of variables. By the Dichotomy Theorem of 
 Bulatov and Zhuk\, this problem is either in P or NP-complete. A natural q
 uestion is to determine the threshold \\alpha(P) < 1 for each NP-complete 
 CSP(P) such that (i) there is a polynomial-time algorithm that finds an as
 signment satisfying an \\alpha(P) fraction of constraints on satisfiable i
 nstances\, and (ii) for every \\epsilon>0\, finding an assignment satisfyi
 ng an (\\alpha(P)+\\epsilon) fraction is NP-hard. While such thresholds ar
 e known for some predicates (e.g.\, 7/8 for 3SAT by Hastad)\, determining 
 \\alpha(P) in general remains widely open.This talk presents recent work i
 nitiating a systematic study of this question\, including new analytical t
 heorems and a proposed approximation algorithm. I will also discuss applic
 ations to additive combinatorics\, including improved bounds for sets avoi
 ding restricted 3-term arithmetic progressions and results related to the 
 density Hales--Jewett theorem in [3]^n.The talk will be based on joint wor
 ks with Subhash Khot\, Yang P. Liu\, and Dor Minzer.\n \nShort Bio : Amey
  Bhangale is currently an Assistant Professor in the CSE Department at the
  University of California\, Riverside. He completed his PhD at the Rutgers
  University in 2017 under the supervision of Swastik Kopparty. He subseque
 ntly held postdoctoral positions at the Weizmann Institute of Science (hos
 ted by Irit Dinur) and was a research fellow at the Simons Institute for t
 he Theory of Computing. His research interests include approximation algor
 ithms\, probabilistically checkable proofs\, hardness of approximation\, a
 nd analysis of Boolean functions.\n
URL:https://www.tcs.tifr.res.in/web/events/1705
DTSTART;TZID=Asia/Kolkata:20260410T160000
DTEND;TZID=Asia/Kolkata:20260410T170000
LOCATION:A201
END:VEVENT
END:VCALENDAR