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:69d1ff64b950d
DTSTART;TZID=America/Toronto:20241129T153000
SEQUENCE:0
TRANSP:TRANSPARENT
DTEND;TZID=America/Toronto:20241129T163000
URL:https://uwaterloo.ca/combinatorics-and-optimization/events/tutte-colloq
 uium-vijay-bhattiprolu-0
SUMMARY:Tutte colloquium-Vijay Bhattiprolu
CLASS:PUBLIC
DESCRIPTION:TITLE: Inapproximability of Sparsest Vector in a Real Subspace\
 n\nSPEAKER:\n Vijay Bhattiprolu\n\nAFFILIATION:\n University of Waterloo\n
 \nLOCATION:\n MC 5501\n\nABSTRACT:We establish strong inapproximability fo
 r finding the\nsparsest nonzero vector in a real subspace (where sparsity 
 refers to\nthe number of nonzero entries). Formally we show that it is NP-
 Hard\n(under randomized reductions) to approximate the sparsest vector in 
 a\nsubspace within any constant factor. We recover as a corollary state\no
 f the art inapproximability factors for the shortest vector problem\n(SVP)
 \, a foundational problem in lattice based cryptography. Our proof\nis sur
 prisingly simple\, bypassing even the PCP theorem. \n\nOur main motivation
  in this work is the development of\ninapproximability techniques for prob
 lems over the reals. Analytic\nvariants of sparsest vector have connection
 s to small set expansion\,\nquantum separability and polynomial maximizati
 on over convex sets\, all\nof which cause similar barriers to inapproximab
 ility. 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 
DTSTAMP:20260405T062124Z
END:VEVENT
END:VCALENDAR