Informationskomplexität von Abfragealgorithmen?

Informationskomplexität war ein sehr nützliches Werkzeug für die Komplexität der Kommunikation, das hauptsächlich dazu diente, die Kommunikationskomplexität verteilter Probleme zu verringern.

Gibt es ein Analogon der Informationskomplexität für die Abfragekomplexität? Es gibt viele Parallelen zwischen Abfragekomplexität und Kommunikationskomplexität. Häufig (aber nicht immer!) wird eine Untergrenze in einem Modell in eine Untergrenze im anderen Modell übersetzt. Manchmal ist diese Übersetzung nicht ganz einfach.

Gibt es einen Begriff der Informationskomplexität, der nützlich ist, um die Abfragekomplexität von Problemen zu verringern?

Ein erster Durchgang scheint darauf hinzudeuten, dass die Informationskomplexität nicht sehr nützlich ist. Beispielsweise ist die Abfragekomplexität beim Berechnen des ODER von Bits für randomisierte Algorithmen und für Quantenalgorithmen, während die einfachste Anpassung des Begriffs der Informationskomplexität darauf hinweist, dass Informationen, die von einem Abfragealgorithmus gelernt werden, sind höchstens (da der Algorithmus stoppt, wenn er die erste in der Eingabe sieht ).$N$$\Omega(N)$$\Omega(\sqrt{N})$$O(\log N)$$1$

Ja, die Informationstheorie ist nützlich, um die untere Grenze der Abfragekomplexität von Problemen in der Informatik zu beweisen.

Alexander Golynski gab ein gutes Beispiel in seinem auf der SODA 2009 vorgestellten bahnbrechenden Papier mit dem Titel "Cell probe lower bounds for succinct data structures" Bit-Probe-Modell für (prägnante) Datenstrukturen. Sie können das Papier aus dem Cache des Bürgers oder aus dem ACM-Repository herunterladen . Es scheint keine Journalversion des Artikels zu geben.

Sie könnten auch an folgenden Artikeln aus seiner Bibliographie interessiert sein, die auch die Komplexität der Kommunikation mit der Informationstheorie in Verbindung bringen:

• Peter Bro Miltersen, Noam Nisan, Shmuel Safra und Avi Wigderson. Zu Datenstrukturen und asymmetrischer Kommunikationskomplexität. Journal of Computer and System Sciences, 57 (1): 37–49, 1998. [link]
• Anna Gal und Peter Bro Miltersen. Die Zellprüfkomplexität prägnanter Datenstrukturen. Im Internationalen Kolloquium über Automaten, Sprachen und Programmierung, S. 332–344, 2003. [link]