BARRINGTON D. PARKER, Circuit Judge:

Lamont Reeves appeals from a judgment of conviction in the United States District Court for the Eastern District of New York (Garaufis, J.) for possession of child pornography. This appeal requires us to consider the validity of a condition of supervised release that obligated Reeves, upon entry into a "significant romantic relationship," to notify the United States Probation Department and to inform the other party to the relationship of his conviction. We conclude that the condition is unduly vague and not "reasonably necessary" to achieve the objectives of 18 U.S.C. § 3553(a)(2). Accordingly, the condition is vacated.

BACKGROUND

In 2006. Reeves became the subject of a federal investigation arising from the theft of Social Security funds. That investigation led to charges, to which he ultimately pled guilty, that he had stolen payments directed to his father who, in fact, had died some ten years earlier. In the course of this investigation, federal agents discovered that Reeves maintained an extensive home library of DVDs and CDs. After Reeves consented to a search of these items, the agents discovered that three of the DVDs contained child pornography. Based on this discovery, the Government charged Reeves with theft of the Social Security funds and with three counts of possession of child pornography. See 18 U.S.C. § 2252(a)(4)(B). Reeves subsequently entered into a plea agreement to resolve the charges. The agreement contemplated a period of incarceration and a term of supervised release, a condition of which required him to register as a sex offender. The Probation Department prepared a Pre-Sentence Report ("PSR") covering all charges that recommended a period of incarceration from 51 to 63 months and a term of supervised release. Although the PSR recommended various conditions of supervised release, it did not recommend the condition that is the subject of this appeal.

Reeves is a 50 year-old father of two grown children, who was previously a long-time employee of the New York court system with no history of domestic violence, no prior involvement with the law except for the theft of Social Security funds, and no prior history of pedophilia. A psychological evaluation conducted in connection with the preparation of the PSR indicated that, while it was difficult to predict the risk of recidivism, Reeves "does not present with predatory tendencies toward children and test results suggest that he is not sexually attracted to children per se." The report recommended that he participate in sex-offender treatment and that his Internet activity be monitored. Another report indicated that Reeves "has had a consistent employment history, understands and appreciates the illegality and immorality of his offense conduct and is willing to participate in an intervention plan."

At sentencing, Reeves's counsel argued for a term of incarceration below the advisory guideline range, which the government opposed. The district court expressed concern that Reeves didn't "really understand the gravity of what he [had] been involved in." Addressing Reeves, the court stated, "You're going to have to have therapy. You're going to have to accept that you have a problem and try to resolve it." Ultimately, the district court imposed a below-guidelines sentence of 40 months incarceration followed by five years supervised release. The sixth special condition of supervised release entered on the Judgment of Conviction required Reeves to "notify the Probation Department when he establishes a significant romantic relationship and . . . inform the other party of his prior criminal history concerning his sex offenses." The condition also provided that "[t]he defendant understands that he must notify the Probation Department of that significant other's address, age, and where the individual may be contacted." This condition was not recommended in the PSR or by the government, nor was it discussed at sentencing. No party had notice of the condition until it appeared in the Judgment of Conviction.

DISCUSSION

We review de novo questions of law arising from the imposition of a condition of supervised release. United States v. Johnson, 446 F.3d 272, 277 (2d Cir. 2006). "A district court retains wide latitude in imposing conditions of supervised release," United States v. MacMillen, 544 F.3d 71, 74 (2d Cir. 2008), and therefore we subject the conditions themselves to "an abuse of discretion standard, where any error of law constitutes an abuse of discretion." Johnson, 446 F.3d at 277. The government does not contest that, even though Reeves did not object to the challenged condition at sentencing, we apply a relaxed plain error review here because he did not receive prior notice of the condition and the error relates only to sentencing. See Fed.R.Crim.P. 52(b); United States v. Sofsky, 287 F.3d 122, 125-26 (2d Cir. 2002) (reviewing a supervised release condition "without insisting on strict compliance with the rigorous standards of Rule 52(b)" where the PSR did not recommend the condition and defendant had no prior knowledge that it would be imposed).

Under 18 U.S.C. § 3583(d), district courts must impose certain mandatory conditions of supervised release. However, the condition in question is not among those required by the statute. District courts also have discretion to impose other, non-mandatory conditions of supervised release — yet this authority is not unlimited. By statute, release conditions must, among other things, be "reasonably related" to certain prescribed sentencing factors and "involve[] no greater deprivation of liberty than is reasonably necessary" to achieve the purposes of sentencing. Id.; see United States v. Myers, 426 F.3d 117, 123-24 (2d Cir. 2005). Reeves contends that the condition in question is not reasonably related to these statutory factors and that the associated deprivation is greater than necessary.

Before we reach any of these concerns, we must determine what the condition actually means. If a condition, however well-intentioned, is not sufficiently clear, it may not be imposed. "Due process requires that [a] condition[] of supervised release be sufficiently clear to give the person of ordinary intelligence a reasonable opportunity to know what is prohibited, so that he may act accordingly." United States v. Simmons, 343 F.3d 72, 81 (2d Cir. 2003) (internal quotation marks omitted). There, we explained that a defendant has a "due process right to conditions of supervised release that are sufficiently clear to inform him of what conduct will result in [the defendant] being returned to prison." Id. (internal quotation marks omitted). A condition is "unconstitutional if it is so vague that `men of common intelligence must necessarily guess at its meaning and differ as to its application.'" MacMillen, 544 F.3d at 76 (quoting Simmons, 343 F.3d at 81). On the other hand, a good deal of flexibility is afforded district courts. "[C]onditions need not be cast in letters six feet high, or . . . describe every possible permutation, or . . . spell out every last, self-evident detail." Johnson, 446 F.3d at 280 (internal quotation marks omitted).

We easily conclude that people of common intelligence (or, for that matter, of high intelligence) would find it impossible to agree on the proper application of a release condition triggered by entry into a "significant romantic relationship." What makes a relationship "romantic," let alone "significant" in its romantic depth, can be the subject of endless debate that varies across generations, regions, and genders. For some, it would involve the exchange of gifts such as flowers or chocolates; for others, it would depend on acts of physical intimacy; and for still others, all of these elements could be present yet the relationship, without a promise of exclusivity, would not be "significant." The history of romance is replete with precisely these blurred lines and misunderstandings. See, e.g., Wolfgang Amadeus Mozart, The Marriage of Figaro (1786); Jane Austen, Mansfield, Park (Thomas Egerton, 1814); When Harry Met Sally (Columbia Pictures 1989); He's Just Not That Into You (Flower Films 2009).

This does not end our inquiry, however, since a subjective element in a release condition may be sufficiently specific if tethered to objective criteria. For example, in Simmons we explained that a release condition prohibiting defendant's possession or viewing of pornographic material was not unconstitutionally vague because, notwithstanding the elusive nature of what qualifies as pornography in the artistic or cultural context, "federal law provides considerable guidance as to the meaning of the term pornography. . . . [that] avoids reference to subjective standards." 343 F.3d at 81-82.

Here, by contrast, the supervised release condition has no objective baseline. No source provides anyone — courts, probation officers, prosecutors, law enforcement officers, or Reeves himself — with guidance as to what constitutes a "significant romantic relationship." We accept the force of Reeves's assertion that his continued freedom during supervised release should not hinge on the accuracy of his prediction of whether a given probation officer, prosecutor, or judge would conclude that a relationship was significant or romantic. See Simmons, 343 F.3d at 81 (explaining that a condition of supervised release must provide clear guidance as to what conduct will result in being returned to prison).

In addition to being too vague to be enforceable, we are not persuaded that the special condition is "reasonably related" to the sentencing objectives of 18 U.S.C. § 3553(a), as required by § 3583(d). A condition of supervision is related to the statutory goals if it is "designed, in light of the crime committed, to promote the [defendant's] rehabilitation and to insure the protection of the public." United States v. Tolla, 781 F.2d 29, 34 (2d Cir. 1986). No condition is presumed valid; rather, a condition is reasonable only if it is not "unnecessarily harsh or excessive." Id.

We have no doubt that in the appropriate circumstance a court, on the recommendation of the Probation Department, could require a defendant to notify third-parties of risks arising from the defendant's criminal record, personal history, or characteristics. See U.S.S.G. § 5D1.3(c)(13). But the history and characteristics of Reeves's offense do not indicate that he poses a risk to those with whom he would have "a significant romantic relationship." Reeves has two children from two separate relationships and there are no allegations of domestic violence or abuse in any of these relationships. He possessed but did not create or distribute child pornography, and his psychological evaluation noted that he "does not present with predatory tendencies toward children and test results suggest that he is not sexually attracted to children per se." Nothing in the record suggests that he has been a threat to a romantic partner. In short, on these facts, we are hard-pressed to see how the notification requirement is reasonably necessary to protect someone with whom Reeves might choose to associate. Nor is it at all apparent that such a notification requirement will promote his rehabilitation. To the contrary, the requirement would almost certainly adversely affect, and could very well prematurely end, any intimate relationship he might develop, placing him at a greater risk of social isolation and thus impair, rather than enhance, his rehabilitation.

We also find that the condition effects an unnecessary deprivation of liberty, because it is not reasonably necessary for deterrence, the protection of the public, or rehabilitation, and, in addition, is not narrowly tailored. To determine if a condition imposes an unnecessary deprivation of liberty, we must first identify the "cognizable liberty interest" with which the condition interferes. Myers, 426 F.3d at 125. Reeves contends that he enjoys a right to enter into and to maintain intimate personal relationships and that the condition unnecessarily burdens that right. The right which Reeves invokes is, as the government concedes, well-established. See id. at 125 n. 8 (citing Roberts v. U.S. Jaycees, 468 U.S. 609, 617-18, 104 S.Ct. 3244, 82 L.Ed.2d 462 (1984) (explaining that "choices to enter into and maintain certain intimate human relationships must be secured against undue intrusion by the State because of the role of such relationships in safeguarding the individual freedom that is central to our constitutional scheme")); see also Sanitation Recycling Indus., Inc. v. City of New York, 107 F.3d 985, 996 (2d Cir. 1997) (explaining that the constitutional right "extends to relationships that `attend the creation and sustenance of a family — marriage, childbirth, the raising and education of children, and cohabitation with one's relatives'") (quoting Roberts, 468 U.S. at 619, 104 S.Ct. 3244). The government contends — correctly — that Reeves has sharply diminished associational rights during his supervised release. As a result, it argues that the condition does not infringe these rights because it is limited in duration and scope, and is narrowly-tailored to serve the compelling government interest in protecting children affected by any such romantic relationship. Cf. Farrell v. Burke, 449 F.3d 470, 497 (2d Cir. 2006) (concluding that a defendant who had been convicted of sodomy with boys between the ages of 13 and 16 had a diminished First Amendment right to access pornography because of his status as a paroled sex offender).

Where a condition of supervised release impairs a protected associational interest, "our application of [§ 3583(d) requirements] must reflect the heightened constitutional concerns" involved. Myers, 426 F.3d at 126. Specifically, "a deprivation of that liberty is `reasonably necessary' only if the deprivation is narrowly tailored to serve a compelling government interest." Id. Although the government's interest in protecting a romantic partner's children is no doubt compelling, the special condition makes no mention of children. Consequently, it is not reasonably directed — or directed at all for that matter — towards this objective. Even assuming arguendo that the goal of the condition is the protection of children, we would conclude that it is not narrowly tailored since it applies to any significant romantic relationship, even those which would not bring Reeves into contact with children. See United States v. Peterson, 248 F.3d 79, 86 (2d Cir. 2001) ("In view of the defendant's prior child sex abuse, the court had justification to impose a condition of probation that prohibits the defendant from being at educational and recreational facilities where children congregate. . . . [H]owever, there would be no justification to forbid the defendant from being at parks and educational or recreational facilities where children do not congregate.").

CONCLUSION

For the forgoing reasons, the condition of supervised release is VACATED and the case REMANDED for proceedings consistent with this decision.