Private Uniform Language Generation
Organizations: King Abdullah University of Science and Technology.
Abstract
We study uniform language generation under approximate differential privacy. Given a uniformly bounded number of distinct examples from an unknown target language, a generator must produce infinitely many new examples from that language with probability one while protecting the privacy of its input. We introduce a new combinatorial dimension termed the nested branching dimension and prove that a language class is privately uniformly generatable if and only if both its closure dimension and nested branching dimension are finite. Previous work characterizes non-private uniform generation by the finiteness of the closure dimension alone. Our results therefore identify an additional combinatorial obstruction imposed by privacy.
Differential Privacy
Differential privacy limits how much an algorithm’s outputs can reveal about any one person’s data, with formal guarantees.
See all 314 papers