Talk information

Date: Sunday, July 14, 2024
Time: 10:10–11:00
Place: Schreiber 309
Speaker: Or Zamir (Tel Aviv University)
Title: Sumsets in the Hypercube

Abstract:

A subset $S$ of the Boolean hypercube $F_2^n$ is called a sumset if $S=A+A=\{a+b | a,b \in A\}$ for some subset $A$ of $F_2^n$. How many sumsets are there in $F_2^n$? In this talk, we will provide an asymptotic answer to this question, along with a structural characterization of almost all such sumsets. Additionally, we will explore related questions: Given an abelian group $G$ and a typical subset $S$ of $G$, how many sumsets in $G$ are needed to express $S$ as their union? (or intersection?) Furthermore, what is the query complexity of testing whether a subset of the hypercube is a sumset?

This talk is based on joint works with Alon and with Chen–Nadimpall–iRandolph–Servedio.