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)

Junyao Zhao junyaoz at
Wed Mar 16 21:54:24 PDT 2022

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 [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<> with Anindya De and Rocco Servedio.


-------------- next part --------------
An HTML attachment was scrubbed...
URL: <>

More information about the theory-seminar mailing list