Denis Xavier Charles
Microsoft Research, Redmond, USA

Bloomier filters using random graphs and number theory.

A Bloomier filter is an efficient data structure for storing functions
that have a static support. We give two new constructions for Bloomier filters
using ideas from graph theory and linear algebra over finite fields. The
construction using graph theory is simpler and faster to construct than
existing constructions. The construction using linear algebra is slower to
construct but achieves close to the optimal storage. This is joint work with
Kumar Chellapilla.