Teoretyczne informatyka

3

Liczba osiągalnych wierzchołków w DAG dla każdego wierzchołka

Niech będzie grafem ukierunkowanym acyklicznie, tak że out-out dowolnego wierzchołka to O ( log | V | ) . Dla każdego wierzchołka G możemy policzyć liczbę osiągalnych wierzchołków, po prostu uruchamiając dfs z każdego wierzchołka, a to zajmie czas O ( | V | | E | ) . Czy …

11 ds.algorithms graph-theory graph-algorithms directed-acyclic-graph

1

Lemma i derandomizacja Borela-Cantellego

Czytałem artykuł zatytułowany Losowe wyrocznie z (poza) programowalnością . Ostatni akapit sekcji 2.3 brzmi: [Stosując nasze nowatorskie podejście] nie ma potrzeby stosowania dobrze znanych klasycznych asymptotycznych (i jednolitych) technik derandomizacji opartych na lemacie Borela-Cantellego . Zgodnie z naszą najlepszą wiedzą, podejście to jest nowością w tym dokumencie. Rzuciłem okiem na …

11 cc.complexity-theory derandomization pr.probability measure-theory

1

Twierdzenie PCP - etap redukcji alfabetu

To, co następuje, może wydawać się głupie (i to prawdopodobnie odzwierciedla moje słabe zrozumienie - więc proszę o wyrozumiałość) Miałem zapytanie dotyczące twierdzenia PCP. Wiemy, że po pierwszych trzech krokach mianowicie. Redukcja stopnia, ekspansja i amplifikacja odstępów , mamy wykres ograniczeń z ulepszoną przerwą i dużym rozmiarem alfabetu (jak Σ …

11 cc.complexity-theory pcp

5

Wystąpienie redukcji FPT, która nie jest redukcją czasu wielomianowego

W sparametryzowanej złożoności ludzie używają redukcji stałych parametrów (FPT), aby udowodnić twardość W [t]. Teoretycznie redukcja FPT nie jest redukcją czasu wielomianowego, ponieważ może działać wykładniczo w parametrze k. Ale w praktyce wszystkie redukcje FPT, które widziałem, są redukcjami czasu p, co oznacza, że dowody twardości W [t] prawie zawsze …

11 cc.complexity-theory np-hardness reductions parameterized-complexity

1

„Przepełnienie” w rozszerzonym algorytmie euklidesowym

Przepraszam, jeśli mylę się z miejscem zadawania pytania (może powinienem przejść do stackoverflow.com/mathoverflow.net?). Ciekawe, jeśli istnieje dowód, że podczas oceny rozszerzony algorytm euklidesową współczynnikom Bézout użytkownika (to jest y i T w tożsamość jako + Bt = GCD ( , b )) nie przekracza około rozsądne wartości (w zależności od …

11 ds.algorithms nt.number-theory

1

NP vs co-NP i logika drugiego rzędu

Załóżmy, że NP = co-NP i wielomian ogranicza długość dowodu niezadowolenia dla instancji 3-CNF . Czy są więc jakieś wyniki w jakiej formie może przyjąć jakiś dowód niezadowolenia dla długości ? Tzn. Ogólnie, czy taki dowód musiałby na przykład wykorzystać pełną moc logiki drugiego rzędu nad nieskończonymi strukturami (zdaję sobie …

11 cc.complexity-theory lo.logic np proof-complexity

2

Które gry 2P1R są potencjalnie ostre?

Dwukomorowe gry na jedną rundę (2P1R) są niezbędnym narzędziem do uzyskania stopnia zbliżenia. Konkretnie, równoległe powtarzanie dwóch rundowych gier z dwiema proverami pozwala zwiększyć rozmiar luki w decyzyjnej wersji problemu aproksymacji. Zobacz wywiad ankiety Ran Raz na CCC 2010, aby uzyskać przegląd tego tematu. Równoległe powtarzanie gry ma zadziwiającą właściwość …

11 cc.complexity-theory approximation-hardness

1

Dolne granice niedeterministycznej komunikacji wielostronnej

Jest to kontynuacja mojego poprzedniego pytania dotyczącego dolnych granic komunikacji dla częściowych funkcji boolowskich . Czy ktoś może zasugerować jakieś odniesienie do dolnych granic niedeterministycznej komunikacji wielopartyjnej? Przeglądam dokumenty w terenie, ale wydaje się, że wszyscy wykazują separacje następującego typu: dolna granica dla protokołu losowego i (mniejsza) górna granica dla …

11 cc.complexity-theory reference-request lower-bounds communication-complexity norms

2

Formalizacje grupowania inne niż K-średnie dla oddzielnych danych

Dane ze świata rzeczywistego czasami mają naturalną liczbę klastrów (próba klastrowania ich w liczbę klastrów mniejszą niż jakaś magiczna k spowoduje drastyczny wzrost kosztu klastrowania). Dzisiaj uczestniczyłem w wykładzie dr Adama Meyersona, który nazwał tego typu danymi „danymi możliwymi do oddzielenia”. Jakie są inne formalizacje klastrowania, inne niż K-średnie, które …

11 lg.learning clustering

4

Ludzka inteligencja i algorytmy

Czy były jakieś badania mające na celu ustalenie, czy ludzka inteligencja może przewyższyć algorytmy (tj. Sprawdzenie, czy twierdzenie o braku wolnego obiadu ma zastosowanie do ludzkiej inteligencji)? W tym samym sensie, czy ktoś opracował metodę techniczną, aby wykorzystać dowolne unikalne, ponadkomputerowe właściwości ludzkiej inteligencji?

11 ds.algorithms big-picture ai.artificial-intel

3

Nauka z „małomównymi” wyroczniami

Moje pytanie jest trochę ogólne, więc wymyślam fajną historię, aby to uzasadnić. Zrób ze mną, jeśli to nie jest realistyczne ;-) Fabuła Pan X, szef działu bezpieczeństwa komputerowego w dużej firmie, jest nieco paranoiczny: wymaga od wszystkich pracowników zmiany hasła raz w miesiącu, aby zminimalizować ryzyko kradzieży tożsamości lub informacji. …

11 lg.learning

2

symulacja w linii prostej

Czy jakieś ciało zna jakieś dobre odniesienie do znaczenia symulacji liniowej? Obecnie jestem głęboko w strukturze Universal Composability (UC) Canetti, ale nie mogę znaleźć żadnego dobrego odniesienia do znaczenia symulacji w linii prostej. Każda pomoc jest mile widziana.

11 cr.crypto-security

2

Układ „równań stochastycznych”

Rozważmy wykres z wierzchołkami i krawędziami m . Wierzchołki są oznaczone zmiennymi rzeczywistymi x i , gdzie x 1 = 0 jest ustalone. Każda krawędź reprezentuje „pomiar”: dla krawędzi ( u , v ) otrzymuję pomiar z ≈ x u - x v . Dokładniej, z jest naprawdę losową wielkością …

11 ds.algorithms graph-algorithms

2

Skutecznie uzyskuje bity N! ?

Biorąc pod uwagę i , czy możliwe jest uzyskanie M -tego bitu (lub cyfry dowolnej małej podstawy) N! w czasie / przestrzeni O (P (ln (N), LN (M))) , gdzie p (x, y) jest kilka funkcji wielomianowej w X i Y ?M M N !N.N.NM.M.MM.M.MN.!N.!N!p ( x , y ) …

11 ds.algorithms nt.number-theory

1

Uczenie się agnostyczne nad dowolnymi rozkładami

Niech będzie rozkładem na pary łańcuchów bitów / etykiet { 0 , 1 } d × { 0 , 1 } i niech C będzie zbiorem funkcji o wartościach logicznych f : { 0 , 1 } d → { 0 , 1 } . Dla każdej funkcji f ∈ …

11 reference-request machine-learning lg.learning