Search Mailing List Archives

Limit search to: Subject & Body Subject Author
Sort by: Reverse Sort
Limit to: All This Week Last Week This Month Last Month
Select Date Range     through    

[theory-seminar] Theory Lunch 3/17: Shivam Nadimpalli (Columbia University)

Victor Lecomte vc.lecomte at
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!

Junyao Zhao <junyaoz at> 于 2022年3月17日周四 11:50写道:

> A gentle reminder: This is happening in 10 minutes.
> ------------------------------
> *From:* Junyao Zhao <junyaoz at>
> *Sent:* Sunday, March 13, 2022 10:55 PM
> *To:* theory-seminar at <theory-seminar at>;
> thseminar at <thseminar at>
> *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
> <,-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 <> with Anindya De
> and Rocco Servedio.
> Cheers,
> Junyao
> _______________________________________________
> theory-seminar mailing list
> theory-seminar at
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list