An Exposition of Sanders' Quasi-Polynomial Freiman-Ruzsa Theorem
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/toc.gs.2011.003]