I'm reading surveys by Trevisan and Lovett on applications of additive combinatoric in TCS. The majority of these applications fall under computational complexity, e.g., lower bounds. I wonder if additive combinatorics has found applications in algorithm design too.The motivation for my question is the following: while the connection between additive combinatorics and complexity seems somewhat natural, I'm curious to see how algebraic structure uncovered by additive combinatorics might be exploited in designing efficient algorithms, if any. Pointers to literature would be appreciated.
Additive combinatorics applications in algorithm design
ds.algorithms;reference request;co.combinatorics
Timothy Chan and Moshe Lewenstein have a paper on 3SUM and related problems in the upcoming STOC, which applies an effective version of the BSG theorem from additive combinatorics to solve variants of 3SUM faster than n^2 time.See this link to Chan's papers.