<p>A recent example from STACS 2015 last week is a randomized algorithm for SUBSET SUM instances where no value can arise as a sum of more than $B$ different subsets of $n$ integers running in $O(2^{0.3399n}B^4)$ time.</p>

<p>See <a href="http://drops.dagstuhl.de/opus/volltexte/2015/4903/pdf/3.pdf">Austrin, P., Kaski, P., Koivisto, M., &amp; Nederlof, J. (2015, February). Subset Sum in the Absence of Concentration. In E. W. Mayr, &amp; N. Ollinger (Eds.), 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) (Vol. 30, pp. 48-61).</a></p>

CC BY-SA 3.0
2015-03-12T09:37:38.490Z
2015-03-12T09:37:38.490Z
Juho
<p>The <a href="http://algo2.iti.kit.edu/documents/jacm05-revised.pdf">DC3 algorithm</a> for computing a suffix array takes advantage of additive combinatorics.  It uses difference covers in a key part of the algorithm.  The ideas are very cool and accessible.  The algorithm also has excellent performance in practice, and is widely taught.</p>

<p>A difference cover for a group $G$ is a set $S$ of group elements such that for every $g \in G$, there exists $s,t \in S$ such that $g=s-t$; this notion is related to <a href="http://www.encyclopediaofmath.org/index.php/Difference_set">a difference set</a>.  In this case, the group $G$ is an additive group of integers modulo $n$, hence the connection to additive combinatorics.</p>

<p>Here's the citation:</p>

<p>Juha Kärkkäinen, Peter Sanders, Stefan Burkhardt.  <a href="http://algo2.iti.kit.edu/documents/jacm05-revised.pdf">Linear Work Suffix Array Construction</a>.  Journal of the ACM, 2006.</p>

CC BY-SA 3.0
2015-03-11T22:41:32.410Z
2015-03-12T09:33:16.943Z
2015-03-12T09:33:16.943Z
D.W.
<p>If you include testing in algorithm design, Samorodnitsky uses additive combinatorics to show that linear transformations are efficiently testable <a href="http://www.ccs.neu.edu/home/viola/papers/add.pdf">[here]</a>.</p>

CC BY-SA 3.0
2015-03-14T17:47:45.077Z
2015-03-14T17:47:45.077Z
Manu
<p>Another example is the classical work of Coppersmith and Winorgrad from 1990 on matrix multiplication, which is based on additive combinatorics </p>

<p><a href="http://www.sciencedirect.com/science/article/pii/S0747717108800132" rel="nofollow">http://www.sciencedirect.com/science/article/pii/S0747717108800132</a></p>

CC BY-SA 3.0
2015-05-15T11:33:39.663Z
2015-05-15T11:33:39.663Z
Shachar Lovett
<p>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.</p>

<p>See <a href="https://cs.uwaterloo.ca/~tmchan/pub.html">this link to Chan's papers</a>.</p>

CC BY-SA 3.0
2015-03-13T08:34:07.503Z
Is $3SAT$ implication potential possibility?
Turbo
CC BY-SA 3.0
2015-05-23T21:09:14.287Z
I don't think we could use this to solve $3SAT$ faster than known algorithms -- $3SAT$ can already be solved in $1.308^n$ time.
Ryan Williams
CC BY-SA 3.0
2015-03-12T00:33:49.393Z
2015-03-12T00:33:49.393Z
Ryan Williams
<p>I'm reading surveys by <a href="http://theory.stanford.edu/~trevisan/pubs/addcomb-sigact.pdf">Trevisan</a> and <a href="http://cseweb.ucsd.edu/~slovett/files/addcomb-survey.pdf">Lovett</a> on applications of additive combinatoric in TCS. The majority of these applications fall under <em>computational complexity</em>, e.g., lower bounds. I wonder if additive combinatorics has found applications in <em>algorithm design</em> too.</p>

<p>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.</p>

CC BY-SA 3.0
2015-03-12T01:18:19.017Z
I think 'acceptance' for this type of questions is pointless, since the goal is compiling a list of relevant pointers. But, I accepted Ryan's since the referenced result is definitely the type of connections I was looking for: the use of additive combinatorics is explicit in the algorithm design, and the resolution is intriguing in that why BSG fell short of cracking the infamous 3SUM.
user32373
<ds.algorithms><reference-request><co.combinatorics>
Additive combinatorics applications in algorithm design
user32373
# Additive combinatorics applications in algorithm design

(Asked by: username_0 on 2015-03-11)

I'm reading surveys by [Trevisan](http://theory.stanford.edu/~trevisan/pubs/addcomb-sigact.pdf) and [Lovett](http://cseweb.ucsd.edu/~slovett/files/addcomb-survey.pdf) 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.

**Tags:** ds.algorithms, reference-request, co.combinatorics

> **Comments:**
> **username_0**: I think 'acceptance' for this type of questions is pointless, since the goal is compiling a list of relevant pointers. But, I accepted Ryan's since the referenced result is definitely the type of connections I was looking for: the use of additive combinatorics is explicit in the algorithm design, and the resolution is intriguing in that why BSG fell short of cracking the infamous 3SUM.  

---

## 5 answers

### Answer by username_5 on 2015-03-12. Score: 17 | Accepted answer

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](https://cs.uwaterloo.ca/~tmchan/pub.html).

> **Comments:**
> **username_6**: Is $3SAT$ implication potential possibility?  
> **username_5**: I don't think we could use this to solve $3SAT$ faster than known algorithms -- $3SAT$ can already be solved in $1.308^n$ time.  

---

### Answer by username_1 on 2015-03-12. Score: 8

A recent example from STACS 2015 last week is a randomized algorithm for SUBSET SUM instances where no value can arise as a sum of more than $B$ different subsets of $n$ integers running in $O(2^{0.3399n}B^4)$ time.

See [Austrin, P., Kaski, P., Koivisto, M., & Nederlof, J. (2015, February). Subset Sum in the Absence of Concentration. In E. W. Mayr, & N. Ollinger (Eds.), 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015) (Vol. 30, pp. 48-61).](http://drops.dagstuhl.de/opus/volltexte/2015/4903/pdf/3.pdf)


---

### Answer by username_2 on 2015-03-11. Score: 8

The [DC3 algorithm](http://algo2.iti.kit.edu/documents/jacm05-revised.pdf) for computing a suffix array takes advantage of additive combinatorics. It uses difference covers in a key part of the algorithm. The ideas are very cool and accessible. The algorithm also has excellent performance in practice, and is widely taught.

A difference cover for a group $G$ is a set $S$ of group elements such that for every $g \in G$, there exists $s,t \in S$ such that $g=s-t$; this notion is related to [a difference set](http://www.encyclopediaofmath.org/index.php/Difference_set). In this case, the group $G$ is an additive group of integers modulo $n$, hence the connection to additive combinatorics.

Here's the citation:

Juha Kärkkäinen, Peter Sanders, Stefan Burkhardt. [Linear Work Suffix Array Construction](http://algo2.iti.kit.edu/documents/jacm05-revised.pdf). Journal of the ACM, 2006.


---

### Answer by username_3 on 2015-03-14. Score: 5

If you include testing in algorithm design, Samorodnitsky uses additive combinatorics to show that linear transformations are efficiently testable [[here]](http://www.ccs.neu.edu/home/viola/papers/add.pdf).


---

### Answer by username_4 on 2015-05-15. Score: 3

Another example is the classical work of Coppersmith and Winorgrad from 1990 on matrix multiplication, which is based on additive combinatorics

<http://www.sciencedirect.com/science/article/pii/S0747717108800132>


---

