Null Fehler randomisierte Kommunikationskomplexität vs. deterministische Kommunikationskomplexität

Es ist bekannt, dass für -Fehler die Worst-Case-Definition der randomisierten Kommunikationskomplexität und die durchschnittliche Falldefinition äquivalent sind. Wenn der Fehler jedoch , ist die randomisierte Kommunikationskomplexität im schlimmsten Fall dieselbe wie die deterministische Kommunikationskomplexität. $\Theta(1)$ $0$

Ist bekannt, dass eine Funktion eine überkonstante deterministische Kommunikationskomplexität, aber eine zufällige Kommunikationskomplexität mit konstantem Nullfehler aufweist?

Was ist allgemein eine Zeugenfunktion, die die deterministische Kommunikationskomplexität von der fehlerfreien randomisierten Kommunikationskomplexität trennt?

Jede Hilfe wird geschätzt.

communication-complexity sagnik
quelle

Du meinst das Gegenteil (klein randomisiert, aber groß deterministisch)?

Noam

Ja, es tut mir sehr leid für dieses Durcheinander. Ich möchte eine konstante, fehlerfreie, randomisierte Kommunikationskomplexität, aber eine super konstante, deterministische Kommunikationskomplexität. Ich habe mich mit dem Problem der Satz-Disjunktheit befasst. Da und das Hastad-Wigderson-Protokoll bereits ein einseitiges Protokoll für die Satz-Disjunktheit von ergibt Kosten Das Problem läuft darauf hinaus, eine einseitige Obergrenze mit konstantem Kosten-Random-Boundated-Error für Nicht-k-Set-Disjunktheit zu beweisen. Gibt es schon ein Ergebnis?

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

Antworten:

In der Tat ist bekannt, dass für die Unterscheidung von Mengen von Größen aus Elementen Fehler-randomisierte Kommunikationskomplexität , während die deterministische Komplexität . $\log(n)$ $n$ $0$ $\Theta(\log n)$ $\Theta(\log^2 n)$

Es sei daran erinnert, dass es höchstens eine quadratische Lücke geben kann, da die randomisierte Komplexität mit Fehlern von unten durch die nicht deterministischen und co-nicht deterministischen Komplexitäten begrenzt wird. $0$

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

Noam
quelle

Vielen Dank. Das beantwortet perfekt, was ich wissen möchte.

Sagnik

Entschuldigung, das werde ich tun.

Sagnik