{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T06:04:17Z","timestamp":1775282657467,"version":"3.50.1"},"reference-count":80,"publisher":"Association for Computing Machinery (ACM)","issue":"2","license":[{"start":{"date-parts":[[2009,6,20]],"date-time":"2009-06-20T00:00:00Z","timestamp":1245456000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2009,6,20]]},"abstract":"<jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>\n          <jats:p>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.<\/jats:p>","DOI":"10.1145\/1556154.1556170","type":"journal-article","created":{"date-parts":[[2009,6,24]],"date-time":"2009-06-24T16:47:07Z","timestamp":1245862027000},"page":"50-66","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Guest column"],"prefix":"10.1145","volume":"40","author":[{"given":"Luca","family":"Trevisan","sequence":"first","affiliation":[{"name":"U.C. Berkeley"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2009,6,20]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1994.1005"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930070001"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-45198-3_17"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.10056"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1137\/050633445"},{"key":"e_1_2_1_6_1","unstructured":"Tim Austin and Terence Tao. On the testability and repair of hereditary hypergraph properties. arXiv:0801.2179 2008.  Tim Austin and Terence Tao. On the testability and repair of hereditary hypergraph properties. arXiv:0801.2179 2008."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132556"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1073\/pnas.32.12.331"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89520"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2004.29"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-004-0451-1"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(92)90047-M"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000390050105"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1142\/S1793042105000108"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132611"},{"key":"e_1_2_1_17_1","unstructured":"Vitaly Bergelson Terence Tao and Tamar Ziegler. An inverse theorem for the uniformity semi-norms associated with the action of Fw. arXiv:0901.2602 2009.  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."},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.56"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/800061.808737"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/0217015"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0406009"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.56"},{"key":"e_1_2_1_23_1","doi-asserted-by":"crossref","unstructured":"Zeev Dvir. On the size of Kakeya sets in finite fields. Journal of the AMS to appear 2008.  Zeev Dvir. On the size of Kakeya sets in finite fields. Journal of the AMS to appear 2008.","DOI":"10.1090\/S0894-0347-08-00607-3"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.23"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.5555\/874062.875528"},{"key":"e_1_2_1_26_1","first-page":"6","article-title":"A simple algorithm for constructing Szemer\u00e9di's regularity partition","author":"Frieze Alan","year":"1999","journal-title":"Electronic Journal of Combinatorics"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930050052"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02813304"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579457"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/285055.285060"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/103418.103429"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001621"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000390050065"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-001-0332-9"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2007.166.897"},{"key":"e_1_2_1_36_1","unstructured":"Timothy Gowers. Decompositions approximate structure transference and the Hahn-Banach theorem. arXiv:0811.3103 2008.  Timothy Gowers. Decompositions approximate structure transference and the Hahn-Banach theorem. arXiv:0811.3103 2008."},{"key":"e_1_2_1_37_1","unstructured":"Ben Green. Finite field models in additive combinatorics. arXiv:math.NT\/0409420 2004.  Ben Green. Finite field models in additive combinatorics. arXiv:math.NT\/0409420 2004."},{"key":"e_1_2_1_38_1","unstructured":"Ben Green. Montreal lecture notes on quadratic Fourier analysis. arXiv:math\/0604089 2006.  Ben Green. Montreal lecture notes on quadratic Fourier analysis. arXiv:math\/0604089 2006."},{"key":"e_1_2_1_39_1","unstructured":"Ben Green and Terence Tao. An inverse theorem for the Gowers U* norm. math.NT\/0503014 2005.  Ben Green and Terence Tao. An inverse theorem for the Gowers U* norm. math.NT\/0503014 2005."},{"key":"e_1_2_1_40_1","unstructured":"Ben Green and Terence Tao. Linear equations in primes. math.NT\/0606088 2006.  Ben Green and Terence Tao. Linear equations in primes. math.NT\/0606088 2006."},{"key":"e_1_2_1_41_1","unstructured":"Ben Green and Terence Tao. The distribution of polynomials over finite fields with applications to the Gowers norms. arXiv:0711.3191 2007.  Ben Green and Terence Tao. The distribution of polynomials over finite fields with applications to the Gowers norms. arXiv:0711.3191 2007."},{"key":"e_1_2_1_42_1","unstructured":"Ben Green and Terence Tao. A note on the Freiman and Balog-Szemer\u00e9di-Gowers theorems in finite fields. arXiv:math\/0701585 2007.  Ben Green and Terence Tao. A note on the Freiman and Balog-Szemer\u00e9di-Gowers theorems in finite fields. arXiv:math\/0701585 2007."},{"key":"e_1_2_1_43_1","unstructured":"Ben Green and Terence Tao. The M\u00f6bius function is asymptotically orthogonal to nilsequences. arXiv:0807.1736 2008.  Ben Green and Terence Tao. The M\u00f6bius function is asymptotically orthogonal to nilsequences. arXiv:0807.1736 2008."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2008.167.481"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.5802\/aif.2401"},{"key":"e_1_2_1_46_1","unstructured":"Timothy Gowers and Julia Wolf. The true complexity of a system of linear equations. arXiv:0711.0185 2007.  Timothy Gowers and Julia Wolf. The true complexity of a system of linear equations. arXiv:0711.0185 2007."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s2-35.3.385"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060689"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.5555\/795662.796290"},{"key":"e_1_2_1_50_1","unstructured":"Russell Impagliazzo. Personal Communication 2008.  Russell Impagliazzo. Personal Communication 2008."},{"key":"e_1_2_1_51_1","unstructured":"Sergei Konyagin. A sum-product estimate in fields of prime order. math.NT\/0304217 2003.  Sergei Konyagin. A sum-product estimate in fields of prime order. math.NT\/0304217 2003."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374454"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374455"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2006.05.002"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(95)90024-1"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.v28:2"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001602"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1112\/jlms\/s1-28.1.104"},{"key":"e_1_2_1_59_1","first-page":"939","volume-title":"Proceedings of the Fifth Hungarian Colloquium on Combinatorics","author":"Ruzsa Imre","year":"1976"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.20017"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.38"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250864"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.2307\/2274681"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/1132516.1132519"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01894569"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.4064\/aa-27-1-199-245"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01903717"},{"issue":"3","key":"e_1_2_1_68_1","first-page":"294","article-title":"From rotating needles to stability of waves: Emerging connections between combinatorics, analysis, and PDE","volume":"48","author":"Tao Terence","year":"2001","journal-title":"Notices of the AMS"},{"key":"e_1_2_1_69_1","volume-title":"Proceedings of the International Congress of Mathematicians","author":"Tao Terence","year":"2006"},{"key":"e_1_2_1_70_1","unstructured":"Terence Tao. Szemer\u00e9di's regularity lemma revisited. Contributions to Discrete Mathematics 1:8--28 2006.  Terence Tao. Szemer\u00e9di's regularity lemma revisited. Contributions to Discrete Mathematics 1:8--28 2006."},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2005.11.006"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.5555\/1333875.1334177"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.41"},{"key":"e_1_2_1_74_1","unstructured":"Terence Tao and Van Vu. Additive Combinatorics. Cambridge University Press 2006.  Terence Tao and Van Vu. Additive Combinatorics. Cambridge University Press 2006."},{"key":"e_1_2_1_75_1","unstructured":"Terence Tao and Tamar Ziegler. The inverse conjecture for the Gowers norm over finite fields via the correspondence principle. arXiv:0810.5527 2008.  Terence Tao and Tamar Ziegler. The inverse conjecture for the Gowers norm over finite fields via the correspondence principle. arXiv:0810.5527 2008."},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11511-008-0032-5"},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.16"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2007.15"},{"key":"e_1_2_1_80_1","first-page":"129","volume-title":"NJ, 1996)","author":"Wolff Thomas","year":"1999"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89574"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1556154.1556170","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1556154.1556170","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:38:45Z","timestamp":1750253925000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1556154.1556170"}},"subtitle":["additive combinatorics and theoretical computer science"],"short-title":[],"issued":{"date-parts":[[2009,6,20]]},"references-count":80,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2009,6,20]]}},"alternative-id":["10.1145\/1556154.1556170"],"URL":"https:\/\/doi.org\/10.1145\/1556154.1556170","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2009,6,20]]},"assertion":[{"value":"2009-06-20","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}