[Theory] Re: UC Theory Seminar

[Olga Medrano Martin del Campo via Theory]

Good morning.

Update: Lunch with Theory speaker is at Nella ( 1125 E55th St ), and we are planning to meet at 12:20-12:30, ( until 2:00- 2:30 approximately ).

Please reply to this email if interested before 10pm today if possible, since reservation is needed for Nella.

 Thank you!
Olga


Obtener Outlook para iOS<https://aka.ms/o0ukef>
________________________________
De: Theory <theory-bounces at mailman.cs.uchicago.edu> en nombre de Olga Medrano Martin del Campo via Theory <theory at mailman.cs.uchicago.edu>
Enviado: Monday, October 20, 2025 10:38:16 AM
Para: theory at mailman.cs.uchicago.edu <theory at mailman.cs.uchicago.edu>; Alec Sun <alecsun at uchicago.edu>
Asunto: [Theory] Re: UC Theory Seminar

Dear All,

There will be a student lunch with our Tuesday Theory and CS Colloquium spearker Stefan Tiegel on Tuesday, and all PhD students are welcome!

Time 12-2pm, location TBA.

If you are interested in coming please reply to this email. This will help to plan in advance!

Best,
Olga


________________________________
From: Theory <theory-bounces at mailman.cs.uchicago.edu> on behalf of Alec Sun via Theory <theory at mailman.cs.uchicago.edu>
Sent: Sunday, October 12, 2025 12:20 PM
To: theory at mailman.cs.uchicago.edu <theory at mailman.cs.uchicago.edu>
Subject: [Theory] Re: UC Theory Seminar

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<mailto:theory at mailman.cs.uchicago.edu>> wrote:
The first meeting this academic year will take place next week.





 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$>.)
_______________________________________________
Theory mailing list
Theory at mailman.cs.uchicago.edu<mailto: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/20251020/504a1d61/attachment-0001.html>
-------------- next part --------------
A non-text attachment was scrubbed...
Name: NadimpalliPhoto.png
Type: image/png
Size: 1394997 bytes
Desc: NadimpalliPhoto.png
URL: <http://mailman.cs.uchicago.edu/pipermail/theory/attachments/20251020/504a1d61/attachment-0001.png>