BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Drupal iCal API//EN
X-WR-CALNAME:Events items teaser
X-WR-TIMEZONE:America/Toronto
BEGIN:VTIMEZONE
TZID:America/Toronto
X-LIC-LOCATION:America/Toronto
BEGIN:DAYLIGHT
TZNAME:EDT
TZOFFSETFROM:-0500
TZOFFSETTO:-0400
DTSTART:20240310T070000
END:DAYLIGHT
BEGIN:STANDARD
TZNAME:EST
TZOFFSETFROM:-0400
TZOFFSETTO:-0500
DTSTART:20241103T060000
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
UID:68701cc157d1f
DTSTART;TZID=America/Toronto:20241129T153000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20241129T163000
URL:/combinatorics-and-optimization/events/tutte-colloq
 uium-vijay-bhattiprolu-0
SUMMARY:Tutte colloquium-Vijay Bhattiprolu
CLASS:PUBLIC
DESCRIPTION:Summary \n\nTITLE: Inapproximability of Sparsest Vector in a Re
 al Subspace\n\nSPEAKER:\n Vijay Bhattiprolu\n\nAFFILIATION:\n University o
 f À¶Ý®ÊÓƵ\n\nLOCATION:\n MC 5501\n\nABSTRACT:We establish strong inapprox
 imability for finding the\nsparsest nonzero vector in a real subspace (whe
 re sparsity refers to\nthe number of nonzero entries). Formally we show th
 at it is NP-Hard\n(under randomized reductions) to approximate the sparses
 t vector in a\nsubspace within any constant factor. We recover as a coroll
 ary state\nof the art inapproximability factors for the shortest vector pr
 oblem\n(SVP)\, a foundational problem in lattice based cryptography. Our p
 roof\nis surprisingly simple\, bypassing even the PCP theorem. \n\nOur mai
 n motivation in this work is the development of\ninapproximability techniq
 ues for problems over the reals. Analytic\nvariants of sparsest vector hav
 e connections to small set expansion\,\nquantum separability and polynomia
 l maximization over convex sets\, all\nof which cause similar barriers to 
 inapproximability. The approach we\ndevelop could lead to progress on the 
 hardness of some of these\nproblems.\n\nJoint work with Euiwoong Lee. \n\
 n \n\n \n 
DTSTAMP:20250710T200417Z
END:VEVENT
END:VCALENDAR