Certificates in Data Structures

by

Yitong Yin

Time: 2pm on Tuesday, Nov 30
Venue: 3530

A classic lower bound technique for static data structures is the
communication complexity. By seeing the algorithm and the table as two
players who compute the query via communications, a data structure is
reduced to a communication protocol. This technique has following
limitations: first, due to an obvious barrier, it can only prove very
small lower bound; and second, it tells us little about other aspects
of data structure complexity, such as nondeterminism or the
interactive proofs.

To approach these limitations, we study certificates in data
structures. We show that unlike the communication complexity, there
exist hard problems that are hard to certify, and the famous richness
lemma in communication complexity holds for certificates with exactly
the same parameters. We also use certificates to prove high lower
bounds for high dimensional problems in distributed localized data
structures. All these results are due to a combinatorial
characterization of certificates in data structures.