Teoretyczne informatyka

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

7
Czy w TCS są pozycje wstępne?
Czy są stanowiska dla absolwentów studiów licencjackich lub magisterskich z historią badań naukowych do pracy jako naukowiec przed podjęciem pracy doktorskiej? TCS ma kulturę stanowisk podoktoranckich dla ostatnich absolwentów studiów doktoranckich w celu przeprowadzenia badań przed próbą ubiegania się o stanowisko na wydziale. Czy istnieje podobny mechanizm dla studentów studiów …
1
Rozumowanie na temat niedeterministycznie kończących się pętli
Oto pytanie „ścieżka B”, czy kiedykolwiek było. Podsumowanie: pierwsza rzecz, o której myślę, kiedy próbuję nadać semantykę programom niedeterministycznym, skutkuje semantyką, w której nie mogę udowodnić rzeczy o pętlach, które kończą tylko niedeterministyczność. Z pewnością ktoś wymyślił, co zrobić w tej sytuacji, lub przynajmniej wskazał, że jest to trudne, ale …
4
Nierówności typu kwantowego dzwonu
Jestem ciekawy, czy ktoś mógłby polecić jakiś materiał uzupełniający do głębszego zrozumienia artykułu: „ Niektóre wyniki i problemy dotyczące nierówności typu kwantowego dzwonu - Tsirelson ”. W szczególności coś, co może nieco bardziej rozwinąć geometryczną interpretację nierówności typu Bell. Być może papier podkładowy lub odpowiedni podręcznik, który bardziej szczegółowo omawia …
2
Problemy z kratą
Dużo pracy poświęcono problemom obliczeniowym dla zamówień częściowych (np. Rozpoznawanie, numer skoku, rozpoznawanie wykresu porównywalności itp.). Jestem ciekawy, jaką pracę wykonano dla sieci. Szukałem wokoło i nie znalazłem podobnej pracy dla krat. W szczególności jestem zainteresowany tym, czy zbadano następujące problemy z siecią: Rozpoznawanie krat: czy przy danym DAG czy …
1
Próbkowanie Agnostic PAC w dolnej granicy
Dobrze wiadomo, że do klasycznego uczenia się PAC, przykłady są konieczne, aby osiągnąć granicę błędu whp, gdzie jest wymiarem VC klasy koncepcyjnej.Ω ( d/ ε)Ω(re/ε)\Omega(d/\varepsilon)εε\varepsilonrered Czy wiadomo, że w przypadku agnostyki potrzebne są przykłady ?Ω ( d/ ε2))Ω(re/ε2))\Omega(d/\varepsilon^2)
1
Praktyczna operacja porównywania i zamiany wielu słów
W artykule o tym samym tytule co tytuł tego pytania, autorzy opisują, jak zbudować nieblokowalną, liniową, wielowątkową operację CAS , używając tylko jednego słowa CAS. Najpierw wprowadzają operację podwójnego porównania-pojedynczej wymiany - RDCSS, jak następuje: word_t RDCSS(RDCSSDescriptor_t *d) { do { r = CAS1(d->a2, d->o2, d); if (IsDescriptor(r)) Complete(r); } …
2
Ograniczanie wpisów operatorów jednolitych do liczb rzeczywistych i uniwersalnych zestawów bramek
W Bernsteina i Vazirani w przełomowej pracy „Quantum Theory Complexity”, pokazują, że redd wymiarowa przekształcenie unitarne można skutecznie przybliżony przez iloczyn co nazywają „w pobliżu trywialna obroty” i „przesunięcia fazowe niemal trywialne”. „Near-trywialne obrotów” oznaczają wymiarową jednolity macierzy, które działają jako identyczności na wszystkich jednak 2 wymiarach, lecz działają jako …
4
Koszty wykonania ok. szukaj najbliższego sąsiada w pomijanym quadtree
UWAGA : Pytanie zostało ponownie sformułowane w moich odpowiedziach: Zakładając, że możemy znaleźć najniższych przodków rodzeństwa w czasie , czy ANN można naprawdę wykonać w ?O ( 1 )O(1)O(1)O ( logn )O(log⁡n)O(\log n) Czworoboki są wydajnymi wskaźnikami przestrzennymi. Mam łamigłówkę z implementacją wyszukiwania najbliższego sąsiada w skompresowanej strukturze quadtree, jak …
4
Ograniczanie luki między kwantową a deterministyczną złożonością zapytań
Chociaż znane są wykładnicze separacje między złożonością kwantowych zapytań o ograniczonym ograniczeniu ( Q ( f)Q(f)Q(f) ) a złożonością deterministycznych zapytań ( D ( f)D(f)D(f) ) lub złożonością losowych zapytań o ograniczonym ograniczeniu ( R ( f)R(f)R(f) ), dotyczą one tylko niektórych funkcji częściowych. Jeśli funkcje cząstkowe mają jakieś specjalne …
1
Jaka jest największa różnica między rangą a przybliżoną rangą?
Wiemy, że log stopnia macierzy 0-1 jest dolną granicą deterministycznej złożoności komunikacji, a log przybliżonej rangi jest dolną granicą losowości złożoności komunikacji. Największa różnica między deterministyczną złożonością komunikacji a losową złożonością komunikacji ma charakter wykładniczy. A co z różnicą między rangą a przybliżoną rangą macierzy boolowskiej?
5
Rozproszona maszyna Turinga?
Jestem studentem specjalizującym się w systemach rozproszonych, ale interesuję się również informatyką teoretyczną. Zastanawiałem się, czy istnieje formalna reprezentacja systemu rozproszonego na maszynie Turinga? To znaczy, czy można rozszerzyć (stworzyć wariant) koncepcję maszyny Turinga, aby skorzystać z przetwarzania rozproszonego? Jednym z pomysłów jest utworzenie wspólnej taśmy (coś podobnego do Tuple …
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.