An Exposition of Sanders' Quasi-Polynomial Freiman-Ruzsa Theorem

by Shachar Lovett

Theory of Computing, Graduate Surveys 6, pp. 1-14, 2015

Bibliography with links to cited articles

[1]   Divesh Aggarwal, Yevgeniy Dodis, and Shachar Lovett: Non-malleable codes from additive combinatorics. In Proc. 46th STOC, pp. 774 – 783. ACM Press, 2014. Available at ACM DL. Preliminary version in ECCC. [doi:10.1145/2591796.2591804]

[2]   Boaz Barak, Luca Trevisan, and Avi Wigderson: A mini-course on additive combinatorics, 2007. Available at Alan Frieze’s webpage.

[3]   Eli Ben-Sasson, Shachar Lovett, and Noga Ron-Zewi: An additive combinatorics approach relating rank to communication complexity. J. ACM, 61(4):22, 2014. Preliminary version in FOCS’12. [doi:10.1145/2629598]

[4]   Abhishek Bhowmick, Zeev Dvir, and Shachar Lovett: New bounds for matching vector families. In Proc. 45th STOC, pp. 823–832. ACM Press, 2013. [doi:10.1145/2488608.2488713]

[5]   Khodakhast Bibak: Additive combinatorics: With a view towards computer science and cryptography: An exposition. In Number Theory and Related Fields, volume 43, pp. 99–128. Springer, 2013. Preliminary version in arXiv. [doi:10.1007/978-1-4614-6642-0_4]

[6]   Mei-Chu Chang: A polynomial bound in Freiman’s theorem. Duke Math. J., 113(3):399–419, 2002. Available at Project Euclid.

[7]   Ernie Croot and Olof Sisask: A probabilistic technique for finding almost-periods of convolutions. Geom. Funct. Anal., 20(6):1367–1396, 2010. [doi:10.1007/s00039-010-0101-8]

[8]   Chaim Even-Zohar: On sums of generating sets in Z2n. Combin. Probab. Comput., 21(6):916–941, 2012. Preliminary version in CoRR. [doi:10.1017/S0963548312000351]

[9]   Gregory A. Freiman: Foundations of a structural theory of set addition. Volume 37 of Translations of Mathematical Monographs. Amer. Math. Soc., 1973.

[10]   Ben Green: The polynomial Freiman-Ruzsa conjecture, 2005. Available at Open Problems in Mathematics.

[11]   Ben Green and Imre Z. Ruzsa: Sets with small sumset and rectification. Bull. Lond. Math. Soc., 38(1):43–52, 2006. Preliminary version in arXiv.

[12]   Ben Green and Terence Tao: Freiman’s theorem in finite fields via extremal set theory. Combin. Probab. Comput., 18(3):335–355, 2009. [doi:10.1017/S0963548309009821]

[13]   Sergey V. Konyagin: On the Freiman theorem in finite fields. Math. Notes, 84(3-4):435–438, 2008. [doi:10.1134/S0001434608090137]

[14]   Shachar Lovett: Equivalence of polynomial conjectures in additive combinatorics. Combinatorica, 32(5):607–618, 2012. Preliminary version in ECCC. [doi:10.1007/s00493-012-2714-z]

[15]   Shachar Lovett: Additive combinatorics and its applications in theoretical computer science (draft). Available at author’s website, 2013.

[16]   Józef Marcinkiewicz and Antoni Zygmund: Sur les fonctions indépendantes. Func. Math., 29, 1937. Available from the Polish Virtual Library of Science.

[17]   Helmut Plünnecke: Eigenschaften und Abschätzungen von Wirkungsfunktionen. Gesellschaft für Mathematik und Datenverarbeitung, 1969.

[18]   Noga Ron-Zewi and Eli Ben-Sasson: From affine to two-source extractors via approximate duality. In Proc. 43rd STOC, pp. 177–186. ACM Press, 2011. Preliminary version in ECCC. [doi:10.1145/1993636.1993661]

[19]   Imre Z. Ruzsa: An analog of Freiman’s theorem in groups. Structure Theory of Set-Addition. Astérisque, 258:323–326, 1999.

[20]   Alex Samorodnitsky: Low-degree tests at large distances. In Proc. 39th STOC, pp. 506–515. ACM Press, 2007. Preliminary version in ECCC. [doi:10.1145/1250790.1250864]

[21]   Tom Sanders: A note on Freĭman’s theorem in vector spaces. Combin. Probab. Comput., 17(2):297–305, 2008. [doi:10.1017/S0963548307008644]

[22]   Tom Sanders: On the Bogolyubov-Ruzsa lemma. Analysis & PDE, 5(3):627–655, 2012. [doi:10.2140/apde.2012.5.627]

[23]   Terence Tao and Van H. Vu: Additive Combinatorics. Cambridge Univ. Press, 2006.

[24]   Luca Trevisan: Guest column: additive combinatorics and theoretical computer science. ACM SIGACT News, 40(2):50–66, 2009. [doi:10.1145/1556154.1556170]

[25]   Emanuele Viola: Selected results in additive combinatorics: An exposition. Theory of Computing Library, Graduate Surveys, 3:1–15, 2011. [doi:10.4086/]