  Releasing the result size of conjunctive queries and graph pattern queries
under differential privacy (DP) has received considerable attention in the
literature, but existing solutions do not offer any optimality guarantees. We
provide the first DP mechanism for this problem with a fairly strong notion of
optimality, which can be considered as a natural relaxation of
instance-optimality to a constant.
