Theory Lunch Seminar - Shivam Nadimpalli February 5, 2025 12:00pm — 1:00pm Location: In Person - Gates Hillman 8102 Speaker: SHIVAM NADIMPALLI, Instructor in Applied Mathematics, Department of Mathematics, Massachusetts Institute of Technology https://math.mit.edu/~shivamn/ We study the approximability of high-dimensional convex sets by intersections of halfspaces, where the approximation quality is measured with respect to the standard Gaussian distribution and the complexity of an approximation is the number of halfspaces used. We establish a range of upper and lower bounds both for general convex sets and for specific natural convex sets that are of particular interest. We rely on techniques from many different areas, including classical results from convex geometry, Cramér-type bounds from probability theory, and—perhaps surprisingly—a range of topics from computational complexity theory, including computational learning theory, unconditional pseudorandomness, and the study of influences and noise sensitivity in the analysis of Boolean functions. Based on joint work with Anindya De and Rocco Servedio. Event Website: https://www.cs.cmu.edu/~theorylunch/abstractsHTML/20250205.html Add event to Google Add event to iCal
