Search Mailing List Archives
[theory-seminar] Theory Lunch 3/17: Shivam Nadimpalli (Columbia University)
Victor Lecomte
vc.lecomte at gmail.com
Thu Mar 17 15:49:48 PDT 2022
If you liked Shivam's talk, you should consider attending his talk *tomorrow
12-1pm in Gates 287*. It will be a whiteboard talk with no prerequisites,
where he'll tell us about "convex influences" (a deep link between monotone
Boolean functions and convex bodies over Gaussian space).
Hope to see you there!
Victor
Junyao Zhao <junyaoz at stanford.edu> 于 2022年3月17日周四 11:50写道：
> A gentle reminder: This is happening in 10 minutes.
>
> ------------------------------
> *From:* Junyao Zhao <junyaoz at stanford.edu>
> *Sent:* Sunday, March 13, 2022 10:55 PM
> *To:* theory-seminar at lists.stanford.edu <theory-seminar at lists.stanford.edu>;
> thseminar at cs.stanford.edu <thseminar at cs.stanford.edu>
> *Subject:* [theory-seminar] Theory Lunch 3/17: Shivam Nadimpalli
> (Columbia University)
>
> Hello everyone,
>
> This last theory lunch of this quarter will take place this Thursday at
> noon in the Engineering Quad
> <https://www.google.com/maps/place/Science+%26+Engineering+Quad+Courtyard/@37.4284882,-122.1765394,17z/data=!3m1!4b1!4m5!3m4!1s0x808fbb8ce58bcc27:0x677c06a883bb7bb7!8m2!3d37.428484!4d-122.1743507>.
> We'll start with some socializing, followed by a talk at 12:30pm. Shivam will
> tell us about: *Approximating Sumset Size*
>
> *Abstract:* Given a subset [image: A] of the [image: n]-dimensional
> Boolean hypercube [image: \mathbb{F}_2^n], the sumset [image: A+A] is the
> set [image: \{a+a': a, a' \in A\}] where addition is in [image:
> \mathbb{F}_2^n]. Sumsets play an important role in additive
> combinatorics, where they feature in many central results of the field.
>
> The main result I will talk about is an algorithm for the problem of sumset
> size estimation. In more detail, the algorithm is given oracle access to
> (the indicator function of) an arbitrary [image: A \subseteq
> \mathbb{F}_2^n] and an accuracy parameter [image: \epsilon > 0], and with
> high probability it outputs a value [image: 0 \leq v \leq 1] that is [image:
> \pm \varepsilon]-close to [image: \mathrm{Vol}(A' + A')] for some
> perturbation [image: A' \subseteq A] of [image: A] satisfying [image:
> \mathrm{Vol}(A \setminus A') \leq \varepsilon.] It is easy to see that
> without the relaxation of dealing with [image: A'] rather than [image: A],
> any algorithm for estimating [image: \mathrm{Vol}((A+A)] to any
> nontrivial accuracy must make [image: 2^{\Omega(n)}] queries. In
> contrast, we will (at a high-level) describe how to obtain an algorithm
> whose query complexity depends only on [image: \epsilon] and is
> completely independent of the ambient dimension [image: n].
>
> Based on joint work <https://arxiv.org/abs/2107.12367> with Anindya De
> and Rocco Servedio.
>
> Cheers,
> Junyao
>
> _______________________________________________
> theory-seminar mailing list
> theory-seminar at lists.stanford.edu
> https://mailman.stanford.edu/mailman/listinfo/theory-seminar
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20220317/814dcfec/attachment-0001.html>
More information about the theory-seminar
mailing list