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.

$\endgroup$
  • $\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 Mar 12 '15 at 1:18
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.

$\endgroup$
  • $\begingroup$ Is $3SAT$ implication potential possibility? $\endgroup$ – T.... Mar 13 '15 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 May 23 '15 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.

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

$\endgroup$
5
$\begingroup$

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

$\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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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