Guest column

Subscribe (Full Service)


	Search: The ACM Digital Library The Guide

	Feedback

Guest column: additive combinatorics and theoretical computer science

Full text

Pdf (671 KB)

Source

ACM SIGACT News archive
Volume 40 , Issue 2 (June 2009) table of contents

COLUMN: Technical columns table of contents

Pages 50-66

Year of Publication: 2009

ISSN:0163-5700

Author

Luca Trevisan

U.C. Berkeley

Publisher

ACM New York, NY, USA

Bibliometrics

Downloads (6 Weeks): 13, Downloads (12 Months): 68, Citation Count: 0

Additional Information:

abstract references index terms collaborative colleagues

Tools and Actions:	Review this Article Save this Article to a Binder Display Formats: BibTeX EndNote ACM Ref

DOI Bookmark:	Use this link to bookmark this Article: http://doi.acm.org/10.1145/1556154.1556170 What is a DOI?

ABSTRACT

Additive combinatorics is the branch of combinatorics where the objects of study are subsets of the integers or of other abelian groups, and one is interested in properties and patterns that can be expressed in terms of linear equations. More generally, arithmetic combinatorics deals with properties and patterns that can be expressed via additions and multiplications.

In the past ten years, additive and arithmetic combinatorics have been extremely successful areas of mathematics, featuring a convergence of techniques from graph theory, analysis and ergodic theory. They have helped prove long-standing open questions in additive number theory, and they offer much promise of future progress.

Techniques from additive and arithmetic combinatorics have found several applications in computer science too, to property testing, pseudorandomness, PCP constructions, lower bounds, and extractor constructions. Typically, whenever a technique from additive or arithmetic combinatorics becomes understood by computer scientists, it finds some application.

Considering that there is still a lot of additive and arithmetic combinatorics that computer scientists do not understand (and, the field being very active, even more will be developed in the near future), there seems to be much potential for future connections and applications.

REFERENCES

Note: OCR errors may be found in this Reference List extracted from the full text article. ACM has opted to expose the complete List rather than only correct and linked references.

	1	N. Alon , R. A. Duke , H. Lefmann , V. Rödl , R. Yuster, The algorithmic aspects of the regularity lemma, Journal of Algorithms, v.16 n.1, p.80-109, Jan. 1994 [doi>10.1006/jagm.1994.1005]
	2	Noga Alon, Eldar Fischer, Michael Krivelevich, and Mario Szegedy. Efficient testing of large graphs. Combinatorica, 20(4):451--476, 2000.
	3	Noga Alon, Tali Kaufman, Michael Krivelevich, Simon Litsyn, and Dana Ron. Testing low-degree polynomials over GF (2). In Proceedings of RANDOM-APPROX, pages 188--199, 2003.
	4	Noga Alon, Testing subgraphs in large graphs, Random Structures & Algorithms, v.21 n.3-4, p.359-370, October 2002 [doi>10.1002/rsa.10056]
	5	Noga Alon , Asaf Shapira, Every Monotone Graph Property Is Testable, SIAM Journal on Computing, v.38 n.2, p.505-522, May 2008 [doi>10.1137/050633445]
	6	Tim Austin and Terence Tao. On the testability and repair of hereditary hypergraph properties. arXiv:0801.2179, 2008.
	7	Christian Borgs , Jennifer Chayes , László Lovász , Vera T. Sós , Balázs Szegedy , Katalin Vesztergombi, Graph limits and parameter testing, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132556]
	8	Felix A. Behrend. On the sets of integers which contain no three in arithmetic progression. Proc. Nat. Acad. Sci., 23:331--332, 1946.
	9	L. Babai , L. Fortnow , C. Lund, Nondeterministic exponential time has two-prover interactive protocols, Proceedings of the 31st Annual Symposium on Foundations of Computer Science, p.16-25 vol.1, October 22-24, 1990 [doi>10.1109/FSCS.1990.89520]
	10	Boaz Barak , Russell Impagliazzo , Avi Wigderson, Extracting Randomness Using Few Independent Sources, Proceedings of the 45th Annual IEEE Symposium on Foundations of Computer Science, p.384-393, October 17-19, 2004 [doi>10.1109/FOCS.2004.29]
	11	Jean Bourgain, Nets Katz, and Terence Tao. A sum-product estimate for finite fields, and applications. Geometric and Functional Analysis, 14:27--57, 2004.
	12	Manuel Blum , Michael Luby , Ronitt Rubinfeld, Self-testing/correcting with applications to numerical problems, Journal of Computer and System Sciences, v.47 n.3, p.549-595, Dec. 1993 [doi>10.1016/0022-0000(93)90044-W]
	13	László Babai , Noam Nisan , Márió Szegedy, Multiparty protocols, pseudorandom generators for logspace, and time-space trade-offs, Journal of Computer and System Sciences, v.45 n.2, p.204-232, Oct. 1992 [doi>10.1016/0022-0000(92)90047-M]
	14	Jean Bourgain. On triples in arithmetic progression. Geometric and Functional Analysis, 9:968--984, 1999.
	15	Jean Bourgain. More on the sum-product phenomenon in prime fields and its applications. International Journal of Number Theory, 1(1):1--32, 2005.
	16	Boaz Barak , Anup Rao , Ronen Shaltiel , Avi Wigderson, 2-source dispersers for sub-polynomial entropy and Ramsey graphs beating the Frankl-Wilson construction, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132611]
	17	Vitaly Bergelson, Terence Tao, and Tamar Ziegler. An inverse theorem for the uniformity semi-norms associated with the action of F^w. arXiv:0901.2602, 2009.
	18	Andrej Bogdanov , Emanuele Viola, Pseudorandom Bits for Polynomials, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.41-51, October 21-23, 2007 [doi>10.1109/FOCS.2007.56]
	19	Ashok K. Chandra , Merrick L. Furst , Richard J. Lipton, Multi-party protocols, Proceedings of the fifteenth annual ACM symposium on Theory of computing, p.94-99, December 1983 [doi>10.1145/800061.808737]
	20	Benny Chor , Oded Goldreich, Unbiased bits from sources of weak randomness and probabilistic communication complexity, SIAM Journal on Computing, v.17 n.2, p.230-261, April 1988 [doi>10.1137/0217015]
	21	Fan R. K. Chung , Prasad Tetali, Communication complexity and quasi randomness, SIAM Journal on Discrete Mathematics, v.6 n.1, p.110-125, Feb. 1993 [doi>10.1137/0406009]
	22	Stefan Dziembowski , Krzysztof Pietrzak, Leakage-Resilient Cryptography, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.293-302, October 25-28, 2008 [doi>10.1109/FOCS.2008.56]
	23	Zeev Dvir. On the size of Kakeya sets in finite fields. Journal of the AMS, to appear, 2008.
	24	Zeev Dvir , Avi Wigderson, Kakeya Sets, New Mergers and Old Extractors, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.625-633, October 25-28, 2008 [doi>10.1109/FOCS.2008.23]
	25	A. Frieze, The regularity lemma and approximation schemes for dense problems, Proceedings of the 37th Annual Symposium on Foundations of Computer Science, p.12, October 14-16, 1996
	26	Alan Frieze and Ravi Kannan. A simple algorithm for constructing Szemerédi's regularity partition. Electronic Journal of Combinatorics, 6, 1999.
	27	Alan M. Frieze and Ravi Kannan. Quick approximation to matrices and applications. Combinatorica, 19(2):175--220, 1999.
	28	Hillel Furstenberg. Ergodic behaviour of diagonal measures and a theorem of Szemerédi on arithmetic progressions. J. d'Analyse Math., 31:204--256, 1977.
	29	Peter Frankl and Richard M. Wilson. Intersection theorems with geometric consequences. Combinatorica, 1(4):357--368, 1981.
	30	Oded Goldreich , Shari Goldwasser , Dana Ron, Property testing and its connection to learning and approximation, Journal of the ACM (JACM), v.45 n.4, p.653-750, July 1998 [doi>10.1145/285055.285060]
	31	Peter Gemmell , Richard Lipton , Ronitt Rubinfeld , Madhu Sudan , Avi Wigderson, Self-testing/correcting for polynomials and for approximate functions, Proceedings of the twenty-third annual ACM symposium on Theory of computing, p.33-42, May 05-08, 1991, New Orleans, Louisiana, United States [doi>10.1145/103418.103429]
	32	Timothy Gowers. Lower bounds of tower type for Szemerédi's uniformity lemma. Geometric and Functional Analysis, 7(2):322--337, 1997.
	33	Timothy Gowers. A new proof of Szeméredi's theorem for progressions of length four. Geometric and Functional Analysis, 8(3):529--551, 1998.
	34	Timothy Gowers. A new proof of Szeméredi's theorem. Geometric and Functional Analysis, 11(3):465--588, 2001.
	35	Timothy Gowers. Hypergraph regularity and the multidimensional Szemerédi theorem. Annals of Mathematics, 166:897--946, 2007.
	36	Timothy Gowers. Decompositions, approximate structure, transference, and the Hahn-Banach theorem. arXiv:0811.3103, 2008.
	37	Ben Green. Finite field models in additive combinatorics. arXiv:math.NT/0409420, 2004.
	38	Ben Green. Montreal lecture notes on quadratic Fourier analysis. arXiv:math/0604089, 2006.
	39	Ben Green and Terence Tao. An inverse theorem for the Gowers U* norm. math.NT/0503014, 2005.
	40	Ben Green and Terence Tao. Linear equations in primes. math.NT/0606088, 2006.
	41	Ben Green and Terence Tao. The distribution of polynomials over finite fields, with applications to the Gowers norms. arXiv:0711.3191, 2007.
	42	Ben Green and Terence Tao. A note on the Freiman and Balog-Szemerédi-Gowers theorems in finite fields. arXiv:math/0701585, 2007.
	43	Ben Green and Terence Tao. The Möbius function is asymptotically orthogonal to nilsequences. arXiv:0807.1736, 2008.
	44	Ben Green and Terence Tao. The primes contain arbitrarily long arithmetic progressions. Annals of Mathematics, 167:481--547, 2008.
	45	Ben Green and Terence Tao. Quadratic uniformity of the Mobius function. Annales de l'Institut Fourier, 58:1863--1935, 2009.
	46	Timothy Gowers and Julia Wolf. The true complexity of a system of linear equations. arXiv:0711.0185, 2007.
	47	David R. Heath-Brown. Integer sets containing no arithmetic progressions. Journal of the London Mathematical Society, 35:385--394, 1987.
	48	Thomas Holenstein, Key agreement from weak bit agreement, Proceedings of the thirty-seventh annual ACM symposium on Theory of computing, May 22-24, 2005, Baltimore, MD, USA [doi>10.1145/1060590.1060689]
	49	R. Impagliazzo, Hard-core distributions for somewhat hard problems, Proceedings of the 36th Annual Symposium on Foundations of Computer Science, p.538, October 23-25, 1995
	50	Russell Impagliazzo. Personal Communication, 2008.
	51	Sergei Konyagin. A sum-product estimate in fields of prime order. math.NT/0304217, 2003.
	52	Shachar Lovett , Roy Meshulam , Alex Samorodnitsky, Inverse conjecture for the gowers norm is false, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374454]
	53	Shachar Lovett, Unconditional pseudorandom generators for low degree polynomials, Proceedings of the 40th annual ACM symposium on Theory of computing, May 17-20, 2008, Victoria, British Columbia, Canada [doi>10.1145/1374376.1374455]
	54	László Lovász , Balázs Szegedy, Limits of dense graph sequences, Journal of Combinatorial Theory Series B, v.96 n.6, p.933-957, November, 2006 [doi>10.1016/j.jctb.2006.05.002]
	55	Roy Meshulam, On subsets of finite Abelian groups with no 3-term arithmetic progressions, Journal of Combinatorial Theory Series A, v.71 n.1, p.168-172, July 1995 [doi>10.1016/0097-3165(95)90024-1]
	56	Brendan Nagle, Vojtech Rödl, and Mathias Schacht. The counting lemma for regular k -uniform hypergraphs. Random Structures and Algorithms, 26:1--67, 2006.
	57	Ran Raz, The BNS-chung criterion for multi-party communication complexity, Computational Complexity, v.9 n.2, p.113-122, April 01, 2000 [doi>10.1007/PL00001602]
	58	Klaus Roth. On certain sets of integers. J. London Math. Soc., 28:104--109, 1953.
	59	Imre Ruzsa and Endre Szemerédi. Triple systems with no six points carrying three triangles. In Proceedings of the Fifth Hungarian Colloquium on Combinatorics, pages 939--945, 1976. Volume II.
	60	Vojtěch Rödl , Jozef Skokan, Regularity lemma for k-uniform hypergraphs, Random Structures & Algorithms, v.25 n.1, p.1-42, August 2004 [doi>10.1002/rsa.20017]
	61	Omer Reingold , Luca Trevisan , Madhur Tulsiani , Salil Vadhan, Dense Subsets of Pseudorandom Sets, Proceedings of the 2008 49th Annual IEEE Symposium on Foundations of Computer Science, p.76-85, October 25-28, 2008 [doi>10.1109/FOCS.2008.38]
	62	Alex Samorodnitsky, Low-degree tests at large distances, Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, June 11-13, 2007, San Diego, California, USA [doi>10.1145/1250790.1250864]
	63	Saharon Shelah. Primitive recursive bounds for Van der Waerden numbers. Journal of Symbolic Logic, 55:887--888, 1990.
	64	Alex Samorodnitsky , Luca Trevisan, Gowers uniformity, influence of variables, and PCPs, Proceedings of the thirty-eighth annual ACM symposium on Theory of computing, May 21-23, 2006, Seattle, WA, USA [doi>10.1145/1132516.1132519]
	65	Endre Szemerédi. On sets of integers containing no four elements in arithmetic progression. Acta Math. Acad. Sci. Hung., 20:89--104, 1969.
	66	Endre Szemerédi. On sets of integers containing no k elements in arithmetic progression. Acta Arithmetica, 27:199--245, 1975.
	67	Endre Szemerédi. Integer sets containing no arithmetic progressions. Acta Math. Hungar., 56(1-2):155--158, 1990.
	68	Terence Tao. From rotating needles to stability of waves: Emerging connections between combinatorics, analysis, and PDE. Notices of the AMS, 48(3):294--303, 2001.
	69	Terence Tao. The dichotomy between structure and randomness, arithmetic progressions, and the primes. In Proceedings of the International Congress of Mathematicians, 2006.
	70	Terence Tao. Szemerédi's regularity lemma revisited. Contributions to Discrete Mathematics, 1:8--28, 2006.
	71	Terence Tao, A variant of the hypergraph removal lemma, Journal of Combinatorial Theory Series A, v.113 n.7, p.1257-1280, October 2006 [doi>10.1016/j.jcta.2005.11.006]
	72	Terence Tao, Structure and Randomness in Combinatorics, Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science, p.3-15, October 21-23, 2007 [doi>10.1109/FOCS.2007.68]
	73	Luca Trevisan, Madhur Tulsiani, and Salil Vadhan. Regularity, boosting, and efficiently simulating every high-entropy distribution. In Proceedings of the 24th IEEE Conference on Computational Complexity, 2009.
	74	Terence Tao and Van Vu. Additive Combinatorics. Cambridge University Press, 2006.
	75	Terence Tao and Tamar Ziegler. The inverse conjecture for the Gowers norm over finite fields via the correspondence principle. arXiv:0810.5527, 2008.
	76	Terence Tao and Tamar Ziegler. The primes contain arbitrarily long polynomial progressions. Acta Mathematica, 201:213--305, 2008.
	77	Emanuele Viola. Selected results in additive combinatorics: an exposition. Technical Report TR07-103, Electronic Colloquium on Computational Complexity, 2007.
	78	Emanuele Viola, The Sum of d Small-Bias Generators Fools Polynomials of Degree d, Proceedings of the 2008 IEEE 23rd Annual Conference on Computational Complexity, p.124-127, June 22-26, 2008 [doi>10.1109/CCC.2008.16]
	79	Emanuele Viola , Avi Wigderson, Norms, XOR Lemmas, and Lower Bounds for GF(2) Polynomials and Multiparty Protocols, Proceedings of the Twenty-Second Annual IEEE Conference on Computational Complexity, p.141-154, June 13-March 16, 2007 [doi>10.1109/CCC.2007.15]
	80	Thomas Wolff. Recent work connected with the Kakeya problem. In Prospects in mathematics (Princeton, NJ, 1996), pages 129--162. AMS, 1999.
	81	D. Zuckerman, General weak random sources, Proceedings of the 31st Annual Symposium on Foundations of Computer Science, p.534-543 vol.2, October 22-24, 1990 [doi>10.1109/FSCS.1990.89574]