Aplicações combinatórias aditivas no projeto de algoritmos

12

Estou lendo pesquisas de Trevisan e Lovett sobre aplicações de aditivos combinatórios no TCS. A maioria desses aplicativos se enquadra na complexidade computacional , por exemplo, limites mais baixos. Gostaria de saber se a combinatória aditiva também encontrou aplicações no design de algoritmos .

A motivação para minha pergunta é a seguinte: embora a conexão entre combinatória aditiva e complexidade pareça um tanto natural, estou curioso para ver como a estrutura algébrica descoberta pela combinatória aditiva pode ser explorada no design de algoritmos eficientes, se houver. Ponteiros para a literatura seriam apreciados.

ds.algorithms reference-request co.combinatorics user32373
fonte

Eu acho que 'aceitação' para esse tipo de perguntas é inútil, pois o objetivo é compilar uma lista de indicadores relevantes. Mas aceitei o de Ryan, já que o resultado referenciado é definitivamente o tipo de conexão que eu estava procurando: o uso de combinatória aditiva é explícito no design do algoritmo, e a resolução é intrigante porque o BSG não conseguiu quebrar o infame 3SUM.

user32373

17

Timothy Chan e Moshe Lewenstein têm um artigo sobre 3SUM e problemas relacionados no próximo STOC, que aplica uma versão eficaz do teorema BSG da combinatória aditiva para resolver variantes do 3SUM mais rapidamente que n ^ 2.

Veja este link para os documentos de Chan .

Ryan Williams
fonte

A possibilidade de implicação do é possível?

3 S A T

$3SAT$

T ....

1

Acho que não poderíamos usar isso para resolver o mais rápido que os algoritmos conhecidos - o já pode ser resolvido em tempo.

3 S A T

$3SAT$

3 S A T

$3SAT$

{1.308}^{n}

$1.308^n$

Ryan Williams

8

O algoritmo DC3 para calcular uma matriz de sufixos aproveita as combinações aditivas. Ele usa capas de diferença em uma parte essencial do algoritmo. As idéias são muito legais e acessíveis. O algoritmo também possui excelente desempenho na prática e é amplamente ensinado.

$G$ $S$ $g \in G$ $s,t \in S$ $g=s-t$ $G$ $n$

Aqui está a citação:

Juha Kärkkäinen, Peter Sanders e Stefan Burkhardt. Construção de matriz de sufixo de trabalho linear . Revista da ACM, 2006.

DW
fonte

8

$B$ $n$ $O(2^{0.3399n}B^4)$

Ver Austrin, P., Kaski, P., Koivisto, M. e Nederlof, J. (2015, fevereiro). Soma do subconjunto na ausência de concentração. Em EW Mayr, & N. Ollinger (Eds.), 32º Simpósio Internacional sobre Aspectos Teóricos da Ciência da Computação (STACS 2015) (Vol. 30, pp. 48-61).

Juho
fonte

5

Se você incluir testes no design de algoritmos, Samorodnitsky usa combinatória aditiva para mostrar que transformações lineares são eficientemente testáveis [aqui] .

Manu
fonte

3

Outro exemplo é o trabalho clássico de Coppersmith e Winorgrad, de 1990, sobre multiplicação de matrizes, baseado em combinações aditivas

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

Shachar Lovett
fonte

Aplicações combinatórias aditivas no projeto de algoritmos

Respostas: