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

[Junyao Zhao]

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>