[Colloquium] CS Theory Seminar - Tuesday, October 14

[Jose J Fragoso via Colloquium]

UNIVERSITY OF CHICAGO
COMPUTER SCIENCE DEPARTMENT
PRESENTS




Shivam Nadimpalli
Massachusetts Institute of Technology

[NadimpalliPhoto.png]

Tuesday, October 14, 2025, at 3:30pm
Kent Chemical Laboratory, Room 102



Title: Polyhedral Approximation and Sparsification

  *


Abstract: Given an intersection of (possibly infinitely many) halfspaces at bounded distance from the origin, we show that it can be sparsified, i.e. approximated (under the Gaussian distribution) by an intersection of a halfspaces where the number of halfspaces depends only on the desired accuracy.  This yields efficient algorithms for learning, tolerant testing, and volume estimation of convex sets of bounded width.  Our result follows from a more general sparsification lemma for Gaussian processes, which relies on Talagrand's majorizing measures theorem. As another consequence, we obtain a "junta theorem" for norms over Gaussian space: Every norm over R^n can be multiplicatively approximated (under the Gaussian measure) by a norm that depends on only a constant number of coordinates.

The talk will be self-contained and will require no prior background on Gaussian processes.

(Based on joint works with Anindya De, Ryan O'Donnell, and Rocco Servedio: https://arxiv.org/abs/2311.08575<https://urldefense.com/v3/__https://arxiv.org/abs/2311.08575__;!!BpyFHLRN4TMTrA!7H-FX0Klfc_UA5K8hDM3Xn7teXBkEoUpWEUhR195h_DeL1ljEzqpOydCyUhOJ2WzFTzUKaWzboc2bhKSU46u$>, https://arxiv.org/abs/2411.14664<https://urldefense.com/v3/__https://arxiv.org/abs/2411.14664__;!!BpyFHLRN4TMTrA!7H-FX0Klfc_UA5K8hDM3Xn7teXBkEoUpWEUhR195h_DeL1ljEzqpOydCyUhOJ2WzFTzUKaWzboc2bs5_UjHQ$>.)

Bio: Shivam Nadimpalli is a CLE Moore Instructor of Mathematics at MIT. He earned his PhD from Columbia University under the supervision of Rocco Servedio and Mihalis Yannakakis. His primary research interests lie in high-dimensional geometry and sublinear algorithms.




  Host: Alexander Razborov
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20251006/0c8dd60d/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: NadimpalliPhoto.png
Type: image/png
Size: 2608527 bytes
Desc: NadimpalliPhoto.png
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20251006/0c8dd60d/attachment-0001.png>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ATT00001.txt
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20251006/0c8dd60d/attachment-0002.txt>
-------------- next part --------------
An embedded and charset-unspecified text was scrubbed...
Name: ATT00002.txt
URL: <http://mailman.cs.uchicago.edu/pipermail/colloquium/attachments/20251006/0c8dd60d/attachment-0003.txt>