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ść.
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ę.
— mskrzypczak
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.
— ksoltys