Selected Results in Additive Combinatorics: An Exposition

by Emanuele Viola

Theory of Computing, Graduate Surveys 3, pp. 1-15, 2011

Bibliography with links to cited articles

[1]   Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron: Testing low-degree polynomials over GF(2). In Proc. 7th Intern. Workshop Randomization Approx. Tech. in Comput. Sci. (RANDOM), volume 2764 of Lecture Notes in Comput. Sci., pp. 188–199. Springer, 2003. [doi:10.1007/978-3-540-45198-3_17]

[2]   Antal Balog and Endre Szemerédi: A statistical theorem of set addition. Combinatorica, 14(3):263–268, 1994. [doi:10.1007/BF01212974]

[3]   Alexander Barvinok: Measure Concentration, 2005. Lecture notes. Available at

[4]   Mihir Bellare, Don Coppersmith, Johan Håstad, Marcos A. Kiwi, and Madhu Sudan: Linearity testing in characteristic two. IEEE Trans. Inform. Theory, 42(6):1781–1795, 1996. [doi:10.1109/18.556674]

[5]   Manuel Blum, Michael Luby, and Ronitt Rubinfeld: Self-testing/correcting with applications to numerical problems. J. Comput. System Sci., 47(3):549–595, 1993. [doi:10.1016/0022-0000(93)90044-W]

[6]   Thomas M. Cover and Joy A. Thomas: Elements of Information Theory. Wiley Series in Telecommunications and Signal Processing. Wiley-Interscience, 2006.

[7]   Devdatt P. Dubhashi and Alessandro Panconesi: Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, 2009.

[8]   Gregory A. Freĭman: Foundations of a Structural Theory of Set Addition. American Mathematical Society, 1973. Translated from the Russian, Translations of Mathematical Monographs, Vol 37.

[9]   Timothy Gowers: A new proof of Szemerédi’s theorem for arithmetic progressions of length four. Geom. Funct. Anal., 8(3):529–551, 1998. [doi:10.1007/s000390050065]

[10]   Ben Green: Finite field models in additive combinatorics. In Surveys in Combinatorics, number 327 in London Math. Soc. Lecture Note Ser., pp. 1–28. Cambridge University Press, 2005. [doi:10.1017/CBO9780511734885.002]

[11]   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]

[12]   Ben Green and Terence Tao: A note on the Freiman and Balog-Szemerédi-Gowers theorems in finite fields. J. Aust. Math. Soc., 86(1):61–74, 2009. [doi:10.1017/S1446788708000359]

[13]   L. H. Harper: Optimal assignments of numbers to vertices. SIAM Journal on Applied Mathematics, 12(1):131–135, 1964.

[14]   Alexandr Kostochka and Benny Sudakov: On Ramsey numbers of sparse graphs. Combin. Probab. Comput., 12(5-6):627–641, 2003. [doi:10.1017/S0963548303005728]

[15]   Jiří Matoušek: Lectures on Discrete Geometry. Springer-Verlag, 2002.

[16]   Imre Z. Ruzsa: An analog of Freiman’s theorem in groups. Astérisque, 258:xv, 323–326, 1999.

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

[18]   Benny Sudakov, Endre Szemerédi, and Van Vu: On a question of Erd˝o     s and Moser. Duke Math. J., 129(1):129–155, 2005. [doi:10.1215/S0012-7094-04-12915-X]

[19]   Endre Szemerédi: On sets of integers containing no k elements in arithmetic progression. Acta Arith., 27:199–245, 1975. [doi:10.1007/BF01894569]

[20]   Terence Tao and Van H. Vu: Additive Combinatorics. Volume 105 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, 2006.

[21]   Luca Trevisan: Additive combinatorics and theoretical computer science. SIGACT News, 40(2):50–66, 2009. [doi:10.1145/1556154.1556170]

[22]    Emanuele Viola: Selected results in additive combinatorics: An exposition. Technical Report 103, Electron. Colloq. on Comput. Complexity (ECCC), 2007.