12
$\begingroup$

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.

Improve this question
$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – user32373
    Commented Mar 12, 2015 at 1:18

5 Answers 5

Reset to default
17
$\begingroup$

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.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Is $3SAT$ implication potential possibility? $\endgroup$
    – Turbo
    Commented Mar 13, 2015 at 8:34
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ryan Williams
    Commented May 23, 2015 at 21:09
8
$\begingroup$

The DC3 algorithm 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. 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. Journal of the ACM, 2006.

Improve this answer
$\endgroup$
8
$\begingroup$

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).

Improve this answer
$\endgroup$
5
$\begingroup$

If you include testing in algorithm design, Samorodnitsky uses additive combinatorics to show that linear transformations are efficiently testable [here].

Improve this answer
$\endgroup$
3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.