Pytania otagowane jako property-testing

1
Naturalne, niestabilne właściwości wykresu
Podczas testowania właściwości wykresu algorytm wysyła zapytanie do wykresu docelowego o obecność lub brak krawędzi i musi ustalić, czy cel ma określoną właściwość, czy też jest -far od posiadania tej właściwości. (Algorytm może zostać poproszony o powodzenie z błędem 1-stronnym lub 2-stronnym.) Wykres ma -far od posiadania właściwości, jeśli nie …
3
Testowanie właściwości w innych metrykach?
Istnieje duża literatura na temat „testowania właściwości” - problemu polegającego na utworzeniu niewielkiej liczby zapytań do czarnej skrzynki do funkcji celu rozróżnienia dwóch przypadków:f:{0,1}n→Rf:{0,1}n→Rf\colon\{0,1\}^n \to R fff jest członkiem pewnej klasy funkcjiCC\mathcal{C} fff jest -far z każdej funkcji w klasie .εε\varepsilonCC\mathcal{C} Zakres funkcji jest czasem wartością logiczną: , ale nie …
1
Wykorzystanie dodatkowej mocy metody negatywnego przeciwnika
Negatywna metoda przeciwnika ( A D V±ZAreV.±ADV^\pm ) to SDP, który charakteryzuje złożoność kwantowych zapytań. Jest to uogólnienie powszechnie stosowanej metody przeciwnika ( ) i pokonuje dwie bariery, które utrudniały metodę przeciwnika:A D VZAreV.ADV Bariera testowania właściwości: jeśli wszystkie wystąpienia 0 są daleko od wszystkich 1 wystąpień, wówczas metoda przeciwnika …
1
Czułość właściwości wykresu
W [1] Turan pokazuje, że czułość (zwana w dokumencie „złożonością krytyczną”) właściwości wykresu jest ściśle większa niż ⌊ 14m ⌋⌊14m⌋\lfloor {1\over 4} m \rfloorgdziemmmjest liczbą wierzchołków na wykresie. Dalej zakłada, że ​​każda nietrywialna właściwość graficzna ma czułość≥m−1≥m-1\geq m-1. Wspomina, że ​​zostało to zweryfikowane dla. Czy poczyniono jakieś postępy w tej …
2
Testowanie pozytywności zamiast równości
Alice i Bob mają n-bitowe ciągi i chcą dowiedzieć się, czy są równe, podczas niewielkiej komunikacji. Standardowe rozwiązanie randomizowane polega na traktowaniu ciągów n-bitowych jako wielomianów stopnia a następnie ocenie wielomianów na kilku losowo wybranych elementach z pola o wielkości większej niż n . Wymaga to komunikacji O ( log …
2
Dolna granica szacowania dla
Chciałbym wiedzieć (związany z tym drugim pytaniem ), czy dolne granice były znane z następującego problemu testowego: jeden ma dostęp do zapytania do sekwencji liczb nieujemnych i , z obietnicą, że albo lub .an≥⋯≥a1an≥⋯≥a1a_n \geq \dots\geq a_1ε∈(0,1)ε∈(0,1)\varepsilon \in (0,1)∑nk=1ak=1∑k=1nak=1\sum_{k=1}^n a_k = 1∑nk=1ak≤1−ε∑k=1nak≤1−ε\sum_{k=1}^n a_k \leq 1-\varepsilon Ile zapytań (wyszukiwań) jest wystarczających …
4
Dolna granica dla testowania bliskości w normie ?
Zastanawiałem się, czy istnieje jakakolwiek dolna granica (pod względem złożoności próby) znana z następującego problemu: Biorąc pod uwagę przykładowy dostęp do wyroczni do dwóch nieznanych dystrybucji , D_2 w \ {1, \ dots, n \} , test (whp) czyD1D1D_1D2D2D_2{1,…,n}{1,…,n}\{1,\dots,n\} D1=D2D1=D2D_1=D_2 lub d2(D1,D2)=∥D1−D2∥2=∑ni=1(D1(i)−D2(i))2−−−−−−−−−−−−−−−−−−√≥ϵd2⁡(D1,D2)=‖D1−D2‖2=∑i=1n(D1(i)−D2(i))2≥ϵ\operatorname{d_2}(D_1,D_2)=\lVert D_1-D_2\rVert_2 = \sqrt{\sum_{i=1}^n\left(D_1(i)-D_2(i)\right)^2} \geq \epsilon Batu i in. …
2
Jak długo trwa znalezienie krótkiego cyklu na losowym wykresie?
Pozwolić G∼G(n,n−1/2)G∼G(n,n−1/2)G \sim G(n, n^{-1/2}) być losowym wykresem na ≈n3/2≈n3/2\approx n^{3/2}krawędzie Z bardzo dużym prawdopodobieństwemGGG ma wiele 444motocykle. Naszym celem jest wyprodukowanie dowolnego z nich444- motocykle tak szybko, jak to możliwe. Załóżmy, że mamy dostęp do GGG w formie listy sąsiedztwa możemy odnieść sukces ze stałym prawdopodobieństwem w O(n−−√)O(n)O(\sqrt{n}) czas …
2
Testowanie właściwości dla niezależnych zestawów
Załóżmy, że otrzymaliśmy wykres GGG i parametry k,ϵk,ϵk,\epsilon. Czy istnieją zakresy wartości dlakkk (czy jest to wykonalne dla wszystkich kkk), dla których można sprawdzić, czy GGG jest ϵϵ\epsilon-dużo posiadania niezależnego zestawu przynajmniej wielkości kkk w samą porę O(n+poly(1/ϵ))O(n+poly(1/ϵ))O(n + \text{poly}(1/\epsilon)) ? Jeśli użyjemy zwykłego pojęcia ϵϵ\epsilon-dale (tj. co najwyżej ϵn2ϵn2\epsilon …
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.