Zerowa przypadkowa złożoność komunikacji a deterministyczna złożoność komunikacji

Wiadomo, że dla błędu definicja najgorszego przypadku złożoności losowej komunikacji i definicja średniego przypadku są równoważne. Ale gdy błąd wynosi , najgorszy przypadek złożoności komunikacji losowej jest taki sam, jak deterministyczna złożoność komunikacji. $\Theta(1)$ $0$

Czy jakaś funkcja ma super-stałą deterministyczną złożoność komunikacji, ale stałą losową złożoność komunikacji przy zerowym błędzie?

Mówiąc bardziej ogólnie, czym jest funkcja świadka, która oddziela deterministyczną złożoność komunikacji od losowej złożoności komunikacji o zerowym błędzie?

Każda pomoc jest mile widziana.

communication-complexity sagnik
źródło

Masz na myśli coś przeciwnego (mały randomizowany, ale duży deterministyczny)?

Noam

Tak, bardzo przepraszam za ten bałagan. Chcę stałej losowej złożoności komunikacji z zerowym błędem, ale bardzo stałej deterministycznej złożoności komunikacji. Patrzyłem na problem rozłączności set. Ponieważ i protokół Hastad-Wigderson już dają jednostronny protokół rozłączenia set dla koszt problem sprowadza się do udowodnienia stałego kosztu jednostronnego górnego limitu z randomizacją o stałym koszcie dla braku rozłączenia k-set. Czy jest już wynik?

k

$k$

R_{0} (f) = O (m a x {R^{1} (f), R^{1} (not f)})

$R_0(f)=O(max\{R^1(f), R^1(\text{not }f)\})$

k

$k$

O (k)

$O(k)$

sagnik

Odpowiedzi:

Rzeczywiście, dla rozróżnienia zestawów wielkości spośród elementów, wiadomo, że złożona z losowych wartości komunikacja jest , podczas gdy złożoność deterministyczna to . $\log(n)$ $n$ $0$ $\Theta(\log n)$ $\Theta(\log^2 n)$

Przypomnijmy, że może istnieć co najwyżej kwadratowego szczeliny od -error losowo złożoność jest ograniczony od dołu przez nie deterministyczne i CO-niedeterministycznego złożoności. $0$

Zobacz: http://mirror.theoryofcomputing.org/articles/v003a011/v003a011.pdf

Noam
źródło

Wielkie dzięki. To doskonale odpowiada temu, co chcę wiedzieć.

sagnik

Przepraszam, zrobię to.

sagnik