Events and news relevant to the Laboratory for Foundations of Computer Science

[Heng Guo <hguo@inf.ed.ac.uk>]

Hi,

A reminder that we'll have an LFCS seminar today at 2pm:

  Friday, 07 Aug, 2pm

  Anindya De, University of Pennsylvania

  This seminar is in-person.

  

  Venue: IF G.03

Note the unusual time.

In detail:

----------------------------------------------------------------------

Anindya De, University of Pennsylvania

https://www.engineering.upenn.edu/~anindyad/

  Friday, 07 Aug, 2pm

  Venue: IF G.03

Title: Sparsifying intersections of halfspaces.

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 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 work with Ryan O'Donnell,
Shivam Nadimpalli and Rocco Servedio: https://arxiv.org/abs/2411.14664
(appears in the proceedings of STOC 2026).

----------------------------------------------------------------------

best,

-Heng

The University of Edinburgh is a charitable body, registered in Scotland, with registration number SC005336. Is e buidheann carthannais a th’ ann an Oilthigh Dhùn Èideann, clàraichte an Alba, àireamh clàraidh SC005336.