Search Mailing List Archives
[theory-seminar] Theory Lunch 3/17: Shivam Nadimpalli (Columbia University)
Junyao Zhao
junyaoz at stanford.edu
Wed Mar 16 21:54:24 PDT 2022
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 [A] of the -dimensional Boolean hypercube [\mathbb{F}_2^n] , the sumset [A+A] is the set [\{a+a': a, a' \in A\}] where addition is in [\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 [A \subseteq \mathbb{F}_2^n] and an accuracy parameter [\epsilon > 0] , and with high probability it outputs a value [0 \leq v \leq 1] that is [\pm \varepsilon] -close to [\mathrm{Vol}(A' + A')] for some perturbation [A' \subseteq A] of [A] satisfying [\mathrm{Vol}(A \setminus A') \leq \varepsilon.] It is easy to see that without the relaxation of dealing with [A'] rather than [A] , any algorithm for estimating [\mathrm{Vol}((A+A)] to any nontrivial accuracy must make [2^{\Omega(n)}] queries. In contrast, we will (at a high-level) describe how to obtain an algorithm whose query complexity depends only on and is completely independent of the ambient dimension .
Based on joint work<https://arxiv.org/abs/2107.12367> with Anindya De and Rocco Servedio.
Cheers,
Junyao
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mailman.stanford.edu/pipermail/theory-seminar/attachments/20220317/fca30c2d/attachment-0003.html>
More information about the theory-seminar
mailing list