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