[Theory] Re: UC Theory Seminar

[Alec Sun via Theory]

Hi all,

There will be a student lunch with Shivam on Tuesday from 12pm to 2pm, all
PhD students are welcome! To sign up please react to my message on Slack in
the theory channel or reply to me by email.

Best,
Alec


On Tue, Oct 7, 2025, 4:14 PM Alexander Razborov via Theory <
theory at mailman.cs.uchicago.edu> wrote:

> The first meeting this academic year will take place next week.
>
>
>
>
>
>  *Shivam Nadimpalli*
>
> *Massachusetts Institute of Technology*
>
>
> [image: NadimpalliPhoto.png]
>
>
>
> *Tuesday, October 14, 202**5,** 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$>
> .)
> _______________________________________________
> Theory mailing list
> Theory at mailman.cs.uchicago.edu
> https://mailman.cs.uchicago.edu/mailman/listinfo/theory
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20251012/b69da9ed/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: NadimpalliPhoto.png
Type: image/png
Size: 1394997 bytes
Desc: not available
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20251012/b69da9ed/attachment-0001.png>