Teoretyczne informatyka

1

Jakie są wyniki algorytmów szacujących wielomiany dla danego zestawu punktów?

Wydaje się, że istnieje wiele randomizowanych algorytmów do testowania tożsamości wielomianowej, sprawdzających, czy dany wielomian ma wartość zero. Czy są jakieś wyniki algorytmów, które dokonują pewnego rodzaju oszacowania wielomianów w określonym zestawie punktów? Może to być na przykład przybliżenie, dla jakiej części tych punktów wielomian ocenia się na zero, lub …

10 ds.algorithms approximation-algorithms randomized-algorithms derandomization polynomials

2

Numeracja podzbiorów

Napraw . Dla każdego wystarczająco dużego chcielibyśmy oznaczyć wszystkie podzbiory wielkości dokładnie dodatnimi liczbami całkowitymi z . Chcielibyśmy, aby to etykietowanie spełniało następującą właściwość: istnieje zestaw liczb całkowitych , uln { 1 .. n } n / k { 1 ... T } S.k ≥ 5k≥5k\ge5nnn{ 1 .. n }{1 …

10 ds.algorithms graph-algorithms it.information-theory nt.number-theory exp-time-algorithms

2

Zasoby wprowadzające dotyczące obliczeniowej teorii uczenia się

Ostatnio czytałem sporo artykułów CoLT. Chociaż nie walczę z poszczególnymi artykułami (przynajmniej nie bardziej niż zwykle walczę z innymi artykułami teoretycznymi), nie czuję, że dobrze rozumiem tę dziedzinę jako całość. Czy istnieje standardowy tekst, ankiety lub notatki z wykładów dotyczące wprowadzania CoLT na poziomie absolwenta? Mam podstawową wiedzę z teorii …

10 reference-request machine-learning lg.learning survey books

4

Wyniki Oracle dla P vs BPP

Niech będzie dowolnym EXP kompletnym problemem. Następnie .P A = N P AZAAAP.ZA= NP.ZAPA=NPAP^A = NP^A Niech będzie jakiś wyrocznią, która bierze pod rachunkach zapytań (a TM w P) uczynią, a my możemy dostać .M P B ≠ N P BbBBM.MMP.b≠ N.P.bPB≠NPBP^B \neq NP^B Pytanie: Czy mamy podobne wyniki wyroczni …

10 cc.complexity-theory oracles relativization

1

Generowanie wykresów obwodu

Niech . Muszę wygenerować proste wykresy obwodu tak aby zestaw wszystkich motocykli tworzy podwójną osłonę (to znaczy, każda krawędź jest dzielona przez dokładnie dwa motocykle) i takie, że przecięcie dowolnych dwóch motocykle to albo wierzchołek, krawędź, albo pusty. Wygenerowane wykresy powinny być dowolnie duże.G g g G g gsol≥ 3g≥3g\geq …

10 ds.algorithms reference-request graph-theory co.combinatorics pseudorandom-generators

1

Algorytmy na wykresach reprezentowane za pomocą BDD

Najprostsze reprezentacje wykresów wykorzystują macierze / listy przyległości, co oznacza, że każdy węzeł i krawędź są wyraźnie reprezentowane. Znaczenie ukrytych reprezentacji dla wykresów wykazujących silne prawidłowości od dawna zostało uznane. Na przykład Galperin i Wigderson (1983), Papadimitriou i Yannakakis ( Nota o zwięzłych reprezentacjach grafów , 1986) badali kwestię wykresów, …

10 ds.algorithms reference-request graph-theory survey binary-decision-diagrams

1

Błąd logiczny korygujący kod w

Czy istnieje znana konstrukcja kodu korygującego błędy liniowe (z rozsądnymi parametrami), na przykład gdy podano logiczny wektor zwraca również wartość logiczną wektora logicznego? (chociaż to koniec \ mathbb {F} _q )ECC:Fnq→FmqECC:Fqn→Fqm\mathsf{ECC}:\mathbb{F}_q^n \to \mathbb{F}_q^mv∈{0,1}nv∈{0,1}nv\in \{0,1\}^nFqFq\mathbb{F}_q (to znaczy Pr[ECC(v)∈{0,1}m]>1−ϵPr[ECC(v)∈{0,1}m]>1−ϵ\Pr[\mathsf{ECC}(v) \in \{0,1\}^m]>1-\epsilon , gdzie prawdopodobieństwo jest przejmowane równomiernie wybierając v∈{0,1}nv∈{0,1}nv\in \{0,1\}^n , a …

10 co.combinatorics linear-algebra coding-theory

1

Reguła eliminacji równości oparta na ujednoliceniu

Kilka lat temu natknąłem się na następującą lewą zasadę równości w rachunku różniczkowym: s ≐ t ⇝ θθ ( Γ ) ⊢ θ ( C)Γ , s ≐ t ⊢ C.s≐t⇝θθ(Γ)⊢θ(C)Γ,s≐t⊢C \frac{s \doteq t \leadsto \theta \qquad \theta(\Gamma) \vdash \theta(C)} {\Gamma, s \doteq t \vdash C} Tutaj, Oblicza najogólniejszym unifikatorem …

10 reference-request lo.logic pl.programming-languages proof-theory sequent-calculus

2

Decydujący homomorfizm grafowy

Graf decydujący Homomorfizm jest ogólnie NP-Complete. Czy istnieją wyniki, które badają ten problem, gdy leżące u podstaw wykresy mają strukturę algebraiczną (takie jak decydowanie o homomorfizmach z wykresów Coseleya lub Cayleya do innych wykresów o określonej strukturze również)? Oprócz wyników złożoności interesują mnie również pomocne techniki algebraiczne i / lub …

10 cc.complexity-theory graph-theory co.combinatorics

1

Jaka jest motywacja definicji ciągliwości parametrów stałych?

Wikipedia pisze: FPT zawiera ustalone, możliwe do rozwiązania problemy, które można rozwiązać w czasie dla niektórych funkcji obliczalnych f . Zwykle funkcja ta jest traktowana jako pojedynczy wykładniczy, taki jak 2 O ( k ), ale definicja dopuszcza funkcje, które rosną jeszcze szybciej. Jest to niezbędne dla dużej części wczesnej …

10 cc.complexity-theory fixed-parameter-tractable

3

Jakim automatem jest Google Turing Doodle?

Z okazji urodzin Alana Turinga Google opublikował doodle przedstawiające maszynę. Jaką maszyną jest doodle? Czy może wyrażać język Turing Complete? Istnieją oczywiste różnice w stosunku do klasycznej maszyny Turinga: skończona taśma, ograniczenia w sposobie łączenia stanu, ... Doodle jest nadal dostępne tutaj (Wyświetlacz w prawym górnym rogu pokazuje oczekiwane wyjście.) …

10 cc.complexity-theory turing-machines

2

Relacja między Babbage a von Neumann

Powszechnie wiadomo, że maszyna analityczna Charlesa Babbage'a miała architekturę silnie przypominającą nowoczesną architekturę von Neumanna. Warto również zauważyć, że tabele reprezentujące program maszyny analitycznej Babbage'a ( http://www.fourmilab.ch/babbage/figures/menat3.png ) oraz prace von Neumanna (takie jak http://library.ias.edu /files/pdfs/ecp/planningcodingof0103inst.pdf ) są dość analogiczne. Teraz zastanawiam się, czy są jakieś wskazówki, w jakim stopniu …

10 ho.history-overview

1

Czym jest algorytm znajdujący minimalną osłonę wierzchołków na dwustronnym grafie z ważonymi wierzchołkami?

Wiem, że dla nieważonego grafu dwustronnego mogę znaleźć minimalną osłonę wierzchołków, najpierw znajdując maksymalne dopasowanie i przekształcając ją w osłonę wierzchołków za pomocą Twierdzenia Königa. Czy istnieje modyfikacja, której można by użyć, gdyby węzły były ważone?

10 ds.algorithms graph-theory

1

Jednolity sposób kwantyfikacji „rozgałęzień” w obliczeniach niedeterministycznych, probabilistycznych i kwantowych?

Obliczenia niedeterministycznej maszyny Turinga (NTM) są dobrze znane jako drzewa konfiguracji, zakorzenione w konfiguracji początkowej. Każde przejście w programie jest reprezentowane przez łącze ojciec-dziecko w tym drzewie. Podobne drzewa można również skonstruować do wizualizacji obliczeń maszyn probabilistycznych i kwantowych. (Należy zauważyć, że dla niektórych celów lepiej jest nie wyświetlać powiązanego …

10 cc.complexity-theory quantum-computing randomness derandomization nondeterminism

1

Czy

Czy oznacza ?E = N EE X P = N E X PmiXP.=N.miXP.\mathsf{EXP}=\mathsf{NEXP}E = N Emi=N.mi\mathsf{E}=\mathsf{NE}

10 cc.complexity-theory conditional-results nexp structural-complexity