Kommunikationskomplexität für die Assoziativitätsentscheidung

12

Sei { 0 , . . . , N - 1 } und : S × S S . Ich möchte die Kommunikationskomplexität berechnen, um zu entscheiden, ob assoziativ ist.S=0,...,n-1:S×SS

Das Modell ist das folgende. ist als Matrix M gegeben . Alice (bzw. Bob) erhält die Hälfte der Einträge der Matrix nach dem Zufallsprinzip (dasselbe gilt für Bob). Ich möchte die ungünstigste Anzahl von Einträgen berechnen, die Alice an Bob senden muss, damit Bob über die Assoziativität von entscheiden kann .M

Tatsächlich ist es einfach, das Problem der Entscheidung über die Gleichheit zweier Bitketten der Größe auf das Problem der Entscheidung über die Assoziativität von über S zu reduzieren . Dies bedeutet, dass die Kommunikationskomplexität der Assoziativität durch Ω ( n ) geringer ist . Ich vermute jedoch, dass diese LB nicht eng ist. Da ich an einem Eingang der Größe n 2 definiere , hätte ich es vorgezogen, eine Kommunikationskomplexität von Ω ( n 2 ) zu finden .Ω(n)SΩ(n)n2Ω(n2)

Gibt es ein bekanntes Ergebnis für dieses Problem? Ist die Antwort aus einem offensichtlichen Grund, den ich nicht sehe?n2

Sylvain Peyronnet
quelle
Können Sie das Modell näher erläutern? Wie sehen die Eingaben aus, die Alice und Bob erhalten, und ob diese randomisiert oder deterministisch (oder quantum) sind?
Robin Kothari
Ich habe entsprechend bearbeitet. Ich interessiere mich für randomisierte oder deterministische Dinge (aber nicht für Quanten), auch wenn für mich praktisch nur der deterministische Rahmen von Bedeutung ist (ich plane, das Ergebnis zu verwenden, um LB auf die Größe einer OBDD zu beweisen).
Sylvain Peyronnet
1
Ich denke, dies wird normalerweise als Einwegkommunikation bezeichnet, da Bob in Ihrem Modell keine Bits an Alice senden darf.
Domotorp

Antworten:

10

Es gibt binäre Operationen auf S . Die Frage ist, wie viele von ihnen assoziativ sind. Kleitman, Rothschild und Spencer gibt eine asymptotische Zählen Formel für dieses Problem in ihrem Papier Die Anzahl der Halbgruppen der Ordnung n . Es hat eine relativ einfache Form in den sogenannten "nicht seltenen Fällen", in denen der Peak von f ( t ) dominiert, so dass die anderen Terme vernachlässigt werden können, ohne die Asymptotik zu beeinflussen. Sie sollten in der Lage sein, eine Untergrenze für Ihre Frage anzugeben, indem Sie die Mathematik mit dieser Formel durchgehen.nn2Snf(t)

Per Vognsen
quelle
1
Danke, ich werde mir dieses Papier ansehen und hierher zurückkehren, um es Ihnen mitzuteilen.
Sylvain Peyronnet