Znajdź współautora ;)

Umieszczajcie tu swoje "anonse" :) Jeśli zabrakło Twojej ulubionej dziedziny informatyki — nie wahaj się dodać odpowiedniego działu. Słowo zachęty: większość młodych naukowców, z którymi rozmawiałam na ten temat, uważa, że współpraca jest kluczowym elementem rozwoju naukowego. Wydaje mi się też, że w innych krajach jest to bardziej promowane przez uczelnie, zwłaszcza wśród studentów zainteresowanych nauką; my musimy sami się o to zatroszczyć :)

Algorytmika

Kryptografia

Logika

Chętnie zajmę się badaniem złożoności topologicznej języków słów, lub drzew definiowanych przez logiki w stylu MSO, lub adekwatne modele automatowe. Chodzi o to, by łącząc metody teorii automatów, logiki i deskryptywnej teorii mnogości dostawać szacowania górne, lub ciekawe przykłady szacujące z dołu odpowiednią złożoność.

mskrzypczakmskrzypczak

Matematyka dyskretna

Teoria grafów

Raz na jakiś czas powracam do hipotezy Cerny'ego ([http://en.wikipedia.org/wiki/Synchronizing_word]). Chętnie z kimś o tym porozmawiam i popracuję.
mskrzypczakmskrzypczak

Sztuczna inteligencja

Teoria obliczeń

Teoria złożoności

Chętnie rozważę przyłączenie się do dowolnego projektu z teorii złożoności, teorii obliczeń lub algorytmów aproksymacyjnych. Ze swojej strony mogę zaproponować następujące tematy:

nieaproksymowalność w czasie podwykładniczym — zajmowałam się tym przez jakiś czas z dr. Łukaszem Kowalikiem i paroma innymi osobami, ale niestety reszta grupy zawiesiła projekt.
Chcę pokazać, że paru problemów (np. kliki lub kolorowania) nie da się aproksymować w czasie podwykładniczym ($2^{o(n)}$) z jakimkolwiek stałym współczynnikiem, przy założeniu ETH (hipoteza, że SAT-a nie daje się rozwiązywać w czasie podwykładniczym ze względu na liczbę zmiennych). Wiemy dwie rzeczy:

  • aproksymacja tych problemów ze stałym współczynnikiem jest NP-trudna
  • jeśli dokonamy redukcji SAT-a do jakiegoś problemu, i ta redukcja będzie liniowa (czyli instancje SAT-a o $n$ zmiennych i $m$ klauzulach będzie przerabiać na instancje nowego problemu o rozmiarze $O(n+m)$), to przy założeniu ETH pokażemy, że tego problemu nie da się rozwiązywać w czasie podwykładniczym. Możemy nawet korzystać ze słabszych redukcji (niekoniecznie działających w czasie wielomianowym; mogą też być redukcjami Turinga), byleby były liniowe (wynik stwierdzający, że rozwiązywalność SAT-a w czasie podwykładniczym ze względu na liczbę zmiennych oraz ze względu na liczbę klauzul są równoważne, jest nietrywialny i całkiem ciekawy [1])

Widać więc, że jeśli zmienimy redukcje używane w dowodach NP-trudności aproksymacji tych problemów tak, aby były liniowe, to dostaniemy to, o co nam chodzi. W paru przypadkach udało nam się po prostu zauważyć: "o, ta redukcja już jest liniowa", reszta problemów stawia większy opór. Co ciekawe — wydaje się, że aby ten opór pokonać, trzeba używać różnych pięknych twierdzeń i koncepcji z "twardej" teorii złożoności! — teraz na przykład bawię się generatorami pseudolosowymi i twierdzeniem PCP. Wydaje mi się, że jakieś przynajmniej częściowe wyniki wyniki są w miarę blisko, więc naprawdę zachęcam do współpracy :)

PSPACE-zupełność gry w Kropki-2 — ostrzegam, to nie jest "poważna praca badawcza" ;) Zajmowałam się przez chwilę dowodzeniem, że gra w kropki jest PSPACE-zupełna; aby to pokazać, wystarczyło zastosować naprawdę ładny nowy wynik dotyczący złożoności pewnego podproblemu występującego w grze w go (tzw. drabinki) [2], i dodać jeden mały gadżet łatający główną różnicę między go a kropkami (w go "żywa grupa" to taka, która ma dwoje oczu; w kropkach — taka, która łączy się z brzegiem kartki). Zastanowiło mnie czy daje się to przystosować do wersji gry w kropki, w której można skakać o 2 kratki — ta drobna zmiana zasad daje tak naprawdę zupełnie inną grę. Idea dowodu pokazującego, że ta gra jest PSPACE-zupełna teoretycznie powinna być podobna, tylko że tutaj na razie nie umiem "wymusić" drabinki! Jakby ktoś chciał ze mną w wolnej chwili poimplementować kombinatoryczne gadżety na kartce w kratkę - zapraszam!

Wkrótce dopiszę tu więcej pomysłów.

bibliografia
1. R. Impagliazzo, R. Paturi, F. Zane Which problems have strongly exponential complexity? pdf
2. M. Crasmaru , J. Tromp Ladders are PSPACE-complete pdf

ksoltysksoltys

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License