The goal of this project is to provide an introduction to some chapter of additive combinatorics (AC) and applications in theoretical computer science. As Ben Green (a leading researcher on the subject) defined: "Well one might say that additive combinatorics is a marriage of number theory, harmonic analysis, combinatorics, and ideas from ergodic theory, which aims to understand very simple systems: the operations of addition and multiplication and how they interact."
We will show some nice application of AC e.g. in Communication complexity and in the theory of Boolean functions.
One can join a project started with my students (see [3] and [4])
Hivatkozások
[1] N. Hegyvári: Introduction to Additive Combinatorics Problems and Exercises (e-manuscript)
[2] Anup Rao, Amir Yehudaoff: Communication complexity (book)
[3] Bence, Bakos ; Norbert, Hegyvari ; Mate, Palfy: A communication complexity problem; subset sums of Cartesian product of certain sets
In Proceedings of Conference on Developments in Computer 2021, pp. 23-26. , 4 p.
[4] Bakos, B. ; Hegyvári, Norbert , Pálfy, M., On a communication complexity problem in combinatorial number theory
MOSCOW JOURNAL OF COMBINATORICS AND NUMBER THEORY 10 : 4 pp. 297-302. , 6 p. (2022)
[5] T. Tao and Van H. Vu: Additive Combinatorics. Volume 13. Cambridge Univ. Press, 2006.