Aplikacje kombinatoryki addytywnej w projektowaniu algorytmów

12

Czytam ankiety Trevisana i Lovetta dotyczące zastosowań dodatku kombinatorycznego w TCS. Większość tych aplikacji ma złożoność obliczeniową , np. Niższe granice. Zastanawiam się, czy kombinatoryka addytywna znalazła również zastosowania w projektowaniu algorytmów .

Motywacja mojego pytania jest następująca: chociaż związek między kombinatoryką addytywną a złożonością wydaje się dość naturalny, jestem ciekawy, jak struktura algebraiczna odkryta przez kombinatorykę addytywną może być wykorzystana do projektowania wydajnych algorytmów, jeśli takie istnieją. Docenione zostaną wskaźniki do literatury.

ds.algorithms reference-request co.combinatorics użytkownik32373
źródło

Myślę, że „akceptacja” tego rodzaju pytań jest bezcelowa, ponieważ celem jest skompletowanie listy odpowiednich wskazówek. Zaakceptowałem jednak Ryana, ponieważ przywoływany wynik jest zdecydowanie rodzajem połączeń, których szukałem: użycie kombinatoryki addytywnej jest wyraźne w projekcie algorytmu, a rozdzielczość jest intrygująca, dlatego BSG nie złamał niesławnego 3SUM.

user32373,

17

Timothy Chan i Moshe Lewenstein mają artykuł na temat 3SUM i powiązanych problemów w nadchodzącym STOC, który stosuje skuteczną wersję twierdzenia BSG od kombinatoryki addycyjnej do rozwiązywania wariantów 3SUM szybciej niż n ^ 2.

Zobacz ten link do dokumentów Chana .

Ryan Williams
źródło

3 S A T

$3SAT$

1

3 S A T

$3SAT$

3 S A T

$3SAT$

{1.308}^{n}

$1.308^n$

8

Algorytm DC3 obliczania macierzy sufiks wykorzystuje dodatków kombinatoryki. Wykorzystuje osłony różnic w kluczowej części algorytmu. Pomysły są bardzo fajne i dostępne. Algorytm ma również doskonałą wydajność w praktyce i jest powszechnie nauczany.

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

Oto cytat:

Juha Kärkkäinen, Peter Sanders, Stefan Burkhardt. Konstrukcja tablicy sufiksów pracy liniowej . Journal of the ACM, 2006.

DW
źródło

8

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

Patrz Austrin, P., Kaski, P., Koivisto, M., i Nederlof, J. (2015, luty). Podzbiór Suma przy braku koncentracji. W EW Mayr i N. Ollinger (Red.), 32. Międzynarodowe Sympozjum na temat teoretycznych aspektów informatyki (STACS 2015) (t. 30, s. 48–61).

Juho
źródło

5

Jeśli włączysz testowanie do algorytmu, Samorodnitsky zastosuje kombinatorykę addytywną, aby pokazać, że transformacje liniowe można skutecznie przetestować [tutaj] .

Manu
źródło

3

Innym przykładem jest klasyczna praca Coppersmitha i Winorgrada z 1990 roku na temat mnożenia macierzy, która oparta jest na kombinatorykach addytywnych

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

Shachar Lovett
źródło

Aplikacje kombinatoryki addytywnej w projektowaniu algorytmów

Odpowiedzi: