Messages often refer to entities such as people, places and events. Correct
identification of the intended reference is an essential part of communication.
Lack of shared unique names often complicates entity reference. Shared knowledge
can be used to construct uniquely identifying descriptive references for entities
with ambiguous names. We introduce a mathematical model for `Reference by
Description', derive results on the conditions under which, with high probability,
programs can construct unambiguous references to most entities in the domain of
discourse and provide empirical validation of these results.