Query complexity and the polynomial Freiman-Ruzsa conjecture

We prove a query complexity variant of the weak polynomial Freiman-Ruzsa conjecture in the following form. For any $ϵ>0$, a set $A \subset $\mathbb{Z}$^d$withdoubling$K$hasasubsetofsizeatleast$K^{-\frac{4}{\epsilon}}|A|$withcoordinatequerycomplexityatmost$\epsilon \log_2 |A|$. We apply this structural result to give a simple proof of the “few products, many sums” phenomenon for integer sets. The resulting bounds are explicit and improve on the seminal result of Bourgain and Chang.