Teoretyczne informatyka

Pytania i odpowiedzi dotyczące teoretycznych informatyków i badaczy w pokrewnych dziedzinach

3
Złożoność decydowania, czy macierz jest całkowicie regularna
Matryca jest nazywana całkowicie regularną, jeśli wszystkie jej kwadratowe submatrice mają pełną rangę. Takie matryce zastosowano do budowy superkoncentratorów. Jaka jest złożoność decyzji, czy dana matryca jest całkowicie regularna w stosunku do racjonalności? Ponad skończonymi polami? Mówiąc bardziej ogólnie, nazwij matrycę całkowicie nieregularną, jeśli wszystkie kwadratowe podmacie wielkości co najwyżej …
1
Znalezienie dobrze wywołanego podgrupy
Otrzymujesz wykres z n wierzchołkami. Jeśli chcesz, może być dwustronny. Istnieje m zestawów krawędzi E 1 , … , E m ⊆ E (powiedz rozłączny). Interesuje mnie problem znalezienia podzbioru S ⊆ V , tak małego, jak to możliwe (lub nawet mniejszego), takiego, że indukowany wykres G S ma co …
2
Liniowo niezależne współczynniki Fouriera
Podstawową właściwością przestrzeni wektorowych jest to, że przestrzeń wektorowa V⊆Fn2V⊆F2nV \subseteq \mathbb{F}_2^n o wymiarze n−dn−dn-d można scharakteryzować ddd liniowo niezależnymi wiązaniami liniowymi - to znaczy istnieją ddd liniowo niezależne wektory w1,…,wd∈Fn2w1,…,wd∈F2nw_1, \ldots, w_d \in \mathbb{F}_2^n , które są prostopadłe do VVV . Z punktu widzenia Fouriera jest to równoważne ze …
4
Dlaczego problem konsensusu jest tak ważny w obliczeniach rozproszonych?
W obliczeniach rozproszonych problem konsensusu wydaje się być jednym z głównych tematów, który przyciągnął intensywne badania. W szczególności artykuł „Niemożność rozproszonego konsensusu z jednym wadliwym procesem” otrzymał nagrodę PODC Influential Paper Award 2001 . Dlaczego więc problem konsensusu jest tak ważny? Co możemy osiągnąć dzięki konsensusowi zarówno w teorii, jak …
2
Aksjomaty dla najkrótszych ścieżek
Załóżmy, że mamy niekierowany wykres ważony G=(V,E,w)G=(V,E,w)G = (V, E, w) (z wagami nieujemnymi). Załóżmy, że wszystkie najkrótsze ścieżki w GGG są unikalne. Załóżmy, że mamy (sekwencje nieważonych krawędzi), ale nie znam samegoCzy możemy wytworzyć dowolny który dałby te ścieżki jako najkrótsze w czasie wielomianowym? Wersja słabsza: czy możemy zdecydować …
3
Czy koncepcja maszyny Turinga pochodzi od automatów?
Niedawno miałem dyskusję na temat maszyn Turinga, kiedy zapytano mnie: „Czy maszyna Turinga pochodzi od automatów, czy jest na odwrót”? Oczywiście nie znałem odpowiedzi, ale jestem ciekawy, aby się dowiedzieć. Maszyna Turinga jest w zasadzie nieco bardziej wyrafinowaną wersją automatów Push-Down. Zakładam, że Maszyna Turinga pochodzi od automatów, jednak nie …
2
Obliczanie stałej Cheegera: możliwe dla jakich klas?
Obliczanie stałej Cheegera na wykresie , znanej również jako stała izoperymetryczna (ponieważ jest to zasadniczo minimalny stosunek powierzchni do objętości), jest znana jako NP-zupełna. Ogólnie jest to przybliżone. Chciałbym się dowiedzieć, czy dokładne algorytmy wielomianowe są znane dla specjalnych klas grafów. Na przykład, czy nadal jest kompletny NP dla zwykłych …
1
Scalanie list delikatnych obiektów
Tło: Chao Xu opublikował kiedyś pytanie: „ Czy są znane algorytmy sortowania porównawczego, które nie ograniczają się do sieci sortujących, tak że każdy element jest porównywany razy?O ( logn )O(log⁡n)O(\log n) ”. Wygląda na to, że trochę utknęliśmy w tym problemie; Omówiłem ten sam problem z Valentinem Polczukiem w 2009 …
1
Czy rozwiązywanie układów równań modulo w dla złożone?
Interesuje mnie złożoność rozwiązywania równań liniowych modulo k , dla dowolnego k (i ze szczególnym zainteresowaniem mocami pierwotnymi), w szczególności: Problem. Czy dla danego układu równań liniowych w nieznanych modulo istnieją jakieś rozwiązania?n kmmmnnnkkk W streszczeniu swojego artykułu Struktura i znaczenie klas logspace-MOD w klasach Mod k L , Buntrock, …
2
Struktura danych dla najkrótszych ścieżek
Niech będzie nieważonym niekierowanym wykresem z wierzchołkami i krawędziami . Czy jest możliwe przetworzenie i utworzenie struktury danych o rozmiarze aby mógł odpowiadać na zapytania o formie „odległość między a ” w czasie O (n)?GGGnnnmmmGGGm⋅polylog(n)m⋅polylog(n)m \cdot \mathrm{polylog}(n)uuuvvv Problem wydaje się zbyt podstawowy, aby go rozwiązać.
2
Minimalna niezadowalająca formuła 3-CNF
Obecnie jestem zainteresowany pozyskiwaniem (lub konstruowaniem) i badaniem formuł 3-CNF, które są niezadowalające i mają minimalny rozmiar. Oznacza to, że muszą składać się z jak najmniejszej liczby klauzul (najlepiej m = 8) i możliwie jak najmniejszej liczby odrębnych zmiennych (n = 4 lub więcej), tak że usunięcie co najmniej jednej …
5
Gdzie można znaleźć oferty pracy na stanowiska wykładowców w teorii CS?
Jakie są najlepsze zasoby do znalezienia ofert pracy na stanowiska wykładowców w teorii CS? Czy jest w szczególności jedna strona internetowa lub lista mailingowa, która jest dość wyczerpująca? Obecnie mam wrażenie, że trzeba użyć różnych zasobów, aby uzyskać kompleksową, ogólnoświatową listę ofert pracy. Czy tak jest w przypadku? To pytanie …
Korzystając z naszej strony potwierdzasz, że przeczytałeś(-aś) i rozumiesz nasze zasady używania plików cookie i zasady ochrony prywatności.
Licensed under cc by-sa 3.0 with attribution required.