<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=utf-8">
</head>
<body>
<div class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Dear All, </div>
<div dir="ltr" class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div dir="ltr" class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
There will be a student lunch with our Tuesday Theory and CS Colloquium spearker Stefan Tiegel on Tuesday, and all PhD students are welcome! </div>
<div dir="ltr" class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div dir="ltr" class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Time 12-2pm, location TBA.</div>
<div dir="ltr" class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div dir="ltr" class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
If you are interested in coming please reply to this email. This will help to plan in advance!</div>
<div dir="ltr" class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div dir="ltr" class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Best,</div>
<div dir="ltr" class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
Olga</div>
<div dir="ltr" class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div dir="ltr" class="elementToProof" style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; color: rgb(0, 0, 0);">
<br>
</div>
<div id="appendonsend" dir="ltr"></div>
<hr style="display: inline-block; width: 98%;">
<div id="divRplyFwdMsg" dir="ltr"><span style="font-family: Calibri, sans-serif; font-size: 11pt; color: rgb(0, 0, 0);"><b>From:</b> Theory <theory-bounces@mailman.cs.uchicago.edu> on behalf of Alec Sun via Theory <theory@mailman.cs.uchicago.edu><br>
<b>Sent:</b> Sunday, October 12, 2025 12:20 PM<br>
<b>To:</b> theory@mailman.cs.uchicago.edu <theory@mailman.cs.uchicago.edu><br>
<b>Subject:</b> [Theory] Re: UC Theory Seminar</span>
<div> </div>
</div>
<div dir="auto">Hi all,</div>
<div dir="ltr"><br>
</div>
<div dir="auto">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.</div>
<div dir="ltr"><br>
</div>
<div dir="auto">Best,</div>
<div dir="auto">Alec</div>
<div dir="ltr"><br>
<br>
</div>
<div dir="ltr" class="x_gmail_attr">On Tue, Oct 7, 2025, 4:14 PM Alexander Razborov via Theory <<a href="mailto:theory@mailman.cs.uchicago.edu" target="_blank" rel="noreferrer">theory@mailman.cs.uchicago.edu</a>> wrote:</div>
<blockquote style="margin: 0px 0px 0px 0.8ex; padding-left: 1ex; border-left-width: 1px; border-left-style: solid; border-left-color: rgb(204, 204, 204);">
<div dir="auto" class="x_gmail_quote">The first meeting this academic year will take place next week.</div>
<p dir="auto" class="x_MsoNormal" style="margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;">
<span style="font-size: 11pt;"> </span></p>
<p dir="auto" class="x_MsoNormal" style="margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;">
</p>
<p dir="auto" class="x_MsoNormal" style="margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;">
<span style="font-size: 11pt;"> </span><span style="font-family: Helvetica; font-size: 14pt;"><b>Shivam Nadimpalli</b></span></p>
<p dir="auto" class="x_MsoNormal" style="margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;">
<span style="font-family: Helvetica; font-size: 14pt;"><b>Massachusetts Institute of Technology</b></span></p>
<p dir="auto" class="x_MsoNormal" style="margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;">
</p>
<div dir="ltr" class="x_gmail_quote"><img src="cid:ii_199d96d534325db3d0a1" alt="NadimpalliPhoto.png" id="x_m_-7926189068108924649m_612089718785611055id-C89CF669-CF1C-481F-9251-CFE537E54F97" width="351" height="351" style="width: 351px; height: 351px;"></div>
<p dir="auto" class="x_MsoNormal" style="margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;">
<span style="font-size: 11pt;"> </span> </p>
<p dir="auto" class="x_MsoNormal" style="margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;">
<span style="font-size: 11pt;"><b>Tuesday, October 14, 2025, at 3:30pm</b></span></p>
<p dir="auto" class="x_MsoNormal" style="margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;">
<span style="font-size: 11pt; background-color: yellow;"><b>Kent Chemical Laboratory, Room 102</b></span></p>
<p dir="auto" class="x_MsoNormal" style="margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;">
<span style="font-size: 11pt;"> </span></p>
<p dir="auto" class="x_MsoNormal" style="margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;">
<span style="font-size: 11pt;"> </span></p>
<p dir="auto" class="x_MsoNormal" style="margin: 0in; font-family: Calibri, sans-serif; font-size: 10pt;">
<span style="font-size: 12pt;"> </span></p>
<div dir="auto" class="x_gmail_quote" style="font-family: Aptos, Arial, Helvetica, sans-serif; font-size: 12pt;">
<span style="background-color: rgb(255, 255, 255);"><b><i>Title: </i></b>Polyhedral Approximation and Sparsification</span></div>
<ul dir="auto" style="margin-top: 0px; margin-bottom: 0px;">
<li style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif; font-size: 12pt; display: block;">
<div dir="ltr" class="x_gmail_quote" role="presentation" style="background-color: rgb(255, 255, 255); margin: 0px; font-family: Aptos, Arial, Helvetica, sans-serif;">
<b><i><br>
</i></b></div>
</li></ul>
<div dir="ltr" class="x_gmail_quote" style="background-color: rgb(255, 255, 255); margin: 0px; font-size: 12pt;">
<span style="font-family: Aptos, Arial, Helvetica, sans-serif;"><b><i>Abstract: </i>
</b></span><span style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif;">Given an intersection of (possibly infinitely many) halfspaces at bounded distance from the origin, we show that it can be
<i>sparsified, </i>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.<br>
<br>
The talk will be self-contained and will require no prior background on Gaussian processes.<br>
<br>
(Based on joint works with Anindya De, Ryan O'Donnell, and Rocco Servedio: </span>
<span style="font-family: Aptos, Arial, Helvetica, sans-serif; color: rgb(31, 167, 116);"><a href="https://urldefense.com/v3/__https://arxiv.org/abs/2311.08575__;!!BpyFHLRN4TMTrA!7H-FX0Klfc_UA5K8hDM3Xn7teXBkEoUpWEUhR195h_DeL1ljEzqpOydCyUhOJ2WzFTzUKaWzboc2bhKSU46u$" target="_blank" id="x_m_-7926189068108924649m_612089718785611055OWA0f0d6b62-5e36-2964-f205-ba1d01eda1db" title="https://urldefense.com/v3/__https://arxiv.org/abs/2311.08575__;!!BpyFHLRN4TMTrA!7H-FX0Klfc_UA5K8hDM3Xn7teXBkEoUpWEUhR195h_DeL1ljEzqpOydCyUhOJ2WzFTzUKaWzboc2bhKSU46u$" rel="noreferrer noreferrer" style="color: rgb(31, 167, 116);">https://arxiv.org/abs/2311.08575</a></span><span style="font-family: Aptos, Arial, Helvetica, sans-serif;">,
</span><span style="font-family: Aptos, Arial, Helvetica, sans-serif; color: rgb(31, 167, 116);"><a href="https://urldefense.com/v3/__https://arxiv.org/abs/2411.14664__;!!BpyFHLRN4TMTrA!7H-FX0Klfc_UA5K8hDM3Xn7teXBkEoUpWEUhR195h_DeL1ljEzqpOydCyUhOJ2WzFTzUKaWzboc2bs5_UjHQ$" target="_blank" id="x_m_-7926189068108924649m_612089718785611055OWA0b352f00-ca84-edfa-6e38-b4f6bb297c48" title="https://urldefense.com/v3/__https://arxiv.org/abs/2411.14664__;!!BpyFHLRN4TMTrA!7H-FX0Klfc_UA5K8hDM3Xn7teXBkEoUpWEUhR195h_DeL1ljEzqpOydCyUhOJ2WzFTzUKaWzboc2bs5_UjHQ$" rel="noreferrer noreferrer" style="color: rgb(31, 167, 116);">https://arxiv.org/abs/2411.14664</a></span><span style="font-family: Aptos, Aptos_EmbeddedFont, Aptos_MSFontService, Calibri, Helvetica, sans-serif;">.)</span></div>
<div dir="auto" class="x_gmail_quote">_______________________________________________<br>
Theory mailing list<br>
<a href="mailto:Theory@mailman.cs.uchicago.edu" target="_blank" rel="noreferrer noreferrer">Theory@mailman.cs.uchicago.edu</a><br>
<a href="https://mailman.cs.uchicago.edu/mailman/listinfo/theory" target="_blank" rel="noreferrer noreferrer noreferrer">https://mailman.cs.uchicago.edu/mailman/listinfo/theory</a></div>
</blockquote>
</body>
</html>