Negative Representations of Information

Abstract

In this dissertation I present the concept of negative representations of information, discuss some possible implementations, and explore its attributes and applications. The concept is summarized by the phrase ``everything except....'' What follows---the exceptions---are the negative image of the idea being conveyed: For instance, the statement ``I like to eat everything except tofu, mole and key lime pie,'' defines a person's culinary preferences by explicitly stating what they don't like. In this work I explore the idea from two perspectives and its implications for hiding data. Firstly, I consider the case of the negative representation being an inexact depiction of the positive set, i.e. when not all possible items are characterized. For example, the above gastronomic description does not exhaustively list all of the dishes disliked by the person, as it easy to imagine recipes that nobody would like. I address the question of how to generalize from the given set of items to a likely set, outline a specific scheme, and discuss its computational properties. Secondly, I study the case when we want the negative representation to exactly depict all the items not in the positive set. I show how to efficiently create a compact representation to accomplish this, and discuss the properties of the arrangement. Several characteristics of describing data negatively are elucidated throughout this work: primarily, that a negative representation can be used to constrain the knowledge gained regarding the positive image, that the amount of information per item is generally lower in a negative representation, and that the way in which answers are inferred using a positive or negative set is fundamentally different. Finally, I outline some operations that take advantage of this change of perspective and that help address some of the privacy concerns of the day.

Back to publications
Back to previous page