Petitioner Lennox Thom (“Petitioner”) sought a writ of habeas corpus to vacate his final order of removal and to direct the Board of Immigration Appeals to adjudicate his application for 212(c) relief from deportation. The United States District Court for the Southern District of New York (Mukasey, C.J.) denied his petition, holding that he is ineligible for 212(c) relief under three provisions of the immigration law: 1) the so-called five-year bar, established by section 511 of the Immigration Act of 1990, Pub.L. No. 101-649, 104 Stat. 4978, 5042 (Nov. 20, 1990) (codified at 8 U.S.C. § 1182(c) (1994) (repealed)), which precludes otherwise eligible lawful permanent resident aliens from applying for 212(c) relief if they have served at least five years in prison for an aggravated felony conviction; 2) section 440(d) of the An-titerrorism and Effective Death Penalty Act (“AEDPA”), Pub.L. No. 104-132, 110 Stat. 1214 (Apr. 24,1996), which eliminated 212(c) relief for certain criminal aliens, including those convicted of aggravated felonies, irrespective of the amount of time they served in prison; and 3) section 304(b) of the Illegal Immigration Reform and Immigrant Responsibility Act of 1996 (“IIRIRA”), Pub.L. No. 104-208, 110 Stat. 3009, 594-97 (Sept. 30, 1996), which repealed 212(c) relief and replaced it with a form of relief called “cancellation of removal,” which is unavailable to aggravated felons.
We agree that Petitioner is ineligible for 212(c) relief and affirm the judgment of the district court.
BACKGROUND
Petitioner, a Guyanan national, entered the United States as a lawful permanent resident in 1969. In 1982, after what we now know was a trial in New York state court, he was convicted of second degree murder and of criminal possession of a weapon in the second degree. He was sentenced to a term of imprisonment of twenty years to life. Later that year, he *160was again convicted in New York state, this time for criminal possession of marijuana in the second degree, and was sentenced to one year in prison.
Upon Petitioner’s incarceration in New York’s Downstate Correctional Facility, various notifications and documents were exchanged between that state prison and the Immigration and Naturalization Service (“INS”).1 As these communications are relevant to one of Petitioner’s claims, we will review them briefly. In a form dated October 29, 1982, the prison notified the INS of Petitioner’s murder conviction and that his earliest possible release date was October 4, 2001. On May 30, 1984, the INS sent the prison a standard “de-tainer” notice — formally known as an “Immigration Detainer — Notice of Action.” This form indicated that an “[ijnvestigation has been initiated to determine whether this person [Petitioner] is subject to deportation.” The document stated that it was “for notification purposes only” and that it did not limit the prison’s discretion with respect to any decision affecting the Petitioner. The document also directed the prison to notify the INS at least 30 days prior to Petitioner’s release or in the event of his death or transfer. On July 6, 1984, the INS sent the prison another such de-tainer notice.
On April 13, 1987, the INS requested that the prison furnish it with a copy of Petitioner’s sentence and commitment order, and the prison answered this request shortly thereafter. The prison also complied with a similar request dated May 11, 1987. On January 27, 1988, the INS was notified that the Petitioner had been transferred to the Sullivan Correctional Facility-
Over ten years later — and three years before the expiration of Petitioner’s minimum sentence — the INS sent the prison another detainer notice, as well as a Notice to Appear and a Warrant for Arrest, all dated June 3, 1998. The Notice to Appear was served on Petitioner by regular mail on June 9, 1998. The Notice to Appear charged: 1) that Petitioner’s murder conviction rendered him removable as an aggravated felon under sections 101(a)(43)(A) and 101(a)(43)(F) of the Immigration and Nationality Act (INA), and 2) that his marijuana conviction rendered him removable as an alien convicted of a controlled substance offense under section 237(a)(2)(B)(i) of the INA.
At his March 31, 1999 removal hearing before an Immigration Judge (IJ), Petitioner, through counsel, admitted his murder and marijuana convictions and conceded removability as an alien convicted of a controlled substance offense. He argued, however, that because his 1982 murder conviction preceded the relevant statutory definition of “aggravated felony,” which was established by Congress in 1988, see Anti-Drug Abuse Act of 1988, § 1227(a)(2)(A)(iii), Pub.L. No. 100-690, 102 Stat. 4181, 4469-4470 (Nov. 18, 1988), his conviction was not for an aggravated felony, and that to apply this definition retroactively would be unconstitutional. Petitioner also maintained that he was eligible for 212(c) relief. See 8 U.S.C. § 1182(c) (1994) (repealed).
The IJ found Petitioner removable as charged. It held that Petitioner’s murder conviction qualified as an “aggravated felony” despite the fact that the conviction pre-dated the relevant statutory definition of that term. It further held that Petitioner was ineligible for 212(c) relief, because the IIRIRA had abolished that form of relief for all removal proceedings institut*161ed after April 1, 1997. It also noted that, while the AEDPA’s elimination of 212(c) relief for aggravated felons did not apply to aliens who were already in deportation proceedings on the date of that law’s enactment, April 24, 1996, see Henderson v. INS, 157 F.3d 106, 128-130 (2d Cir.1998), there was no indication that Petitioner was in proceedings at that time. Finally, the IJ pointed out that, even if the AEDPA and IIRIRA did not apply to Petitioner, he would be independently precluded by the five-year bar from seeking 212(c) relief. See 8 U.S.C. § 1182(c) (1994) (repealed) (barring 212(c) relief for any “alien who has been convicted of one or more aggravated felonies and has served for such felony or felonies a term of imprisonment of at least 5 years”).2
Petitioner then appealed, pro se, to the BIA. In addition to the arguments he made to the IJ, he asserted that, even if his removal proceedings had begun in 1998, the doctrine of laches should bar the INS from applying current law to him, since the INS waited sixteen years from the time of his murder conviction to institute removal proceedings. The BIA agreed with the IJ’s determinations, and stated that it could not consider Petitioner’s laches argument, because it lacked authority to apply the doctrine of equitable estoppel against the government. Accordingly, the BIA dismissed the appeal.
On February 23, 2001, Petitioner, again proceeding pro se, filed a habeas petition under 28 U.S.C. § 2241 in the United States District Court for the Southern District of New York. He made three arguments: 1) that the IIRIRA and the AED-PA’s elimination of 212(c) relief may not be applied retroactively to his 1982 murder conviction; 2) that his deportation proceedings in fact commenced in 1984 upon the INS’s issuance of a detainer notice in 1984, and that the IIRIRA and the AED-PA therefore do not apply to his case; and 3) that the doctrine of laches precludes the application of post-1990 law to his case.
In an order dated May 31, 2001, the district court (Mukasey, C.J.) rejected all of Petitioner’s claims and denied the petition. This appeal followed.3
DISCUSSION
On appeal, Petitioner renews the three arguments that he made to the district court. We find each one unpersuasive and accordingly affirm the judgment below.
I.
First, Petitioner argues that the IIRIRA and the AEDPA’s elimination of 212(c) relief cannot be retroactively applied to his 1982 murder conviction, which was obtained after a trial. He contends that the Supreme Court’s decision in INS v. St Cyr, 533 U.S. 289, 121 S.Ct. 2271, 150 L.Ed.2d 347 (2001), which held that these laws may not be applied retroactively to aliens who had pled guilty to deportable offenses, should be extended to cover aliens who were convicted after going to trial. Our decision in Rankine v. Reno, *162319 F.3d 93 (2d Cir.2003), however, squarely forecloses this argument. In Rankine, we reasoned that “it is choosing ‘to forgo fighting the conviction of a qualifying crime and enter a plea’ that leads to an expectation of relief from removal. The petitioners here assumed no similarly heightened expectation from their decision to go to trial.” Id. at 100 (quoting St. Cyr v. INS, 229 F.3d 406, 419 (2d Cir.2000)). Aliens who decide to go to trial, we held, do not rely on the availability of 212(c) relief, but rather upon “their claim of innocence .... Their reliance, therefore, was on ... ‘familiar criminal justice considerations’ and the application of the criminal laws rather than on the availability of § 212(c) relief.” Id. at 102. See also Swaby v. Ashcroft, 357 F.3d 156, 161-62 (2d Cir.2004) (holding that an alien may not escape Rankine’s rule by attesting that he relied on the availability of 212(c) relief in rejecting a plea agreement and deciding to go to trial).
Petitioner makes an interesting, but ultimately unpersuasive, attempt to distinguish Rankine. He begins by positing that the only reason that St. Cyr and Rankine found that an alien’s decision to plead guilty gave rise to reliance and expectation interests was that such a decision by the alien was motivated by the desire to receive a sentence of less than five years in order to preserve the alien’s eligibility for 212(c) relief under the five-year bar. See 8 U.S.C. 1182(c) (1994) (repealed) (barring 212(c) relief for any alien who has served a term of imprisonment of at least five years for an aggravated felony conviction). He then goes on to argue that, because the five-year bar was not in place in 1982 when he was deciding between pleading guilty and going to trial, his decision to go to trial did not bespeak a lack of desire to preserve his eligibility for 212(c) relief.
We conclude that, whatever else is wrong with Petitioner’s argument, its initial premise is flawed. While St. Cyr and Rankine recognized that the desire to evade the five-year bar might well be one of an alien’s salient motivations in pleading guilty, see, e.g., St. Cyr, 533 U.S. at 323, 121 S.Ct. 2271 (noting, as an “instructive” example, the case of an alien in parallel litigation, in which the IJ found that the sole purpose of his guilty plea was to ensure that he received a sentence of less than five years), these cases did not hold, as Petitioner suggests, that this was the only reason that a plea of guilty indicated an alien’s reliance on the availability of 212(c) relief.
In deciding to plead guilty, an alien may have relied on the availability of 212(c) relief for any number of reasons. For example, an alien may have decided to plead guilty to a lesser offense based on the simple calculation that his chances of receiving 212(c) relief would be worsened by a conviction at trial for a more severe offense. See Matter of Edwards, 20 I. & N. Dec. 191, 195, 1990 WL 385757 (BIA 1990) (in evaluating a 212(c) application, an IJ weighs the humanitarian reasons favoring relief against the “nature” and “seriousness” of the alien’s criminal record). An alien might also have considered that pleading guilty and thereby accepting responsibility for his crime would strengthen his 212(c) application. See In re Catalina Arreguin De Rodriguez, 21 I. & N. Dec. 38, 39, 1995 WL 314389 (BIA 1995) (granting 212(c) application in part because of the alien’s acceptance of responsibility through pleading guilty, an act which bolsters an alien’s claim of rehabilitation). Or an alien may have pled guilty simply because he was willing to bear a prison term, whereas he would have taken his chances at trial if he knew that conviction would entail deportation. See generally St. Cyr, 533 U.S. at 322, 121 S.Ct. 2271 (“[A]s a *163general matter, alien defendants considering whether to enter into a plea agreement are acutely aware of the immigration consequences of their convictions.”).4 Indeed, if the Supreme Court’s rationale in St Cyr were as narrow as Petitioner suggests, the Court could have easily limited its ruling to aliens who would have faced more than five years in prison if they had proceeded to trial.5 For these reasons, we find Petitioner’s attempt to escape Rankine unavailing.
Following Rankine, we must therefore conclude that Petitioner’s decision to contest his murder charges at trial did not give rise to a reasonable reliance or a settled expectation as to the availability of 212(c) relief.6 Because Petitioner does not claim any other basis for such a reliance or expectation, see, e.g., Restrepo v. McElroy, No. 99-2703, 2004 WL 652802, 369 F.3d 627 (2d Cir. April 1, 2004), we hold that the IIRIRA and the AEDPA may be applied retroactively to him.7
*164II.
In the alternative, Petitioner argues that the IIRIRA and the AEDPA may not be applied to his case because the deportation proceedings against him were pending at the time those laws came into effect. Specifically, Petitioner contends that his deportation proceedings began when the INS issued a detainer notice to his prison in 1984, and not when the INS served or filed a Notice to Appear in 1998.8
The question of whether these laws may be applied retroactively to a pending deportation proceeding is controlled by the two-step retroactivity analysis established in Landgraf v. USI Film Prods., 511 U.S. 244, 114 S.Ct. 1483, 128 L.Ed.2d 229 (1994). Under Landgraf, a court must first determine whether Congress has prescribed the statute’s temporal reach. Id. at 280, 114 S.Ct. 1483. If Congress has not, a court must then determine whether application of the statute to the pre-enactment conduct at hand would have a “retroactive effect.” Id. If it would, then, “in keeping with our ‘traditional presumption’ against retroactivity, we presume that the statute does not apply to that conduct.” Martin v. Hadix, 527 U.S. 343, 352, 119 S.Ct. 1998, 144 L.Ed.2d 347 (1999) (quoting Landgraf, 511 U.S. at 280, 114 S.Ct. 1483).
Petitioner is correct in stating that Congress did not intend that the IIRIRA and the AEDPA be applied retroactively to pending deportation proceedings. By its terms, the IIRIRA’s abolition of 212(c) relief does not apply to aliens who are in deportation proceedings as of April 1, 1997. See IIRIRA § 309(a), 110 Stat. 3009, 625; see also St. Cyr, 229 F.3d at 414. And, with regard to the AEDPA, we found in Henderson, 157 F.3d at 129, that there was “abundant direct evidence,” id., that Congress did not intend that law to apply to aliens whose proceedings were pending on the date of its enactment, April 24, 1996.
We find no reason, however, to accept Petitioner’s contention that his deportation proceedings began in 1984. We hold, instead, that his proceedings started in 1998, the year in which the INS served him with a Notice to Appear and filed that Notice with the immigration court.9 Un*165like the service or filing of a Notice to Appear,' the INS’s issuance of a detainer notice is of limited significance — it is “merely a method of advising the prison officials to notify the I.N.S. of the petitioner’s impending release or transfer .... The detainer expresses only the intention of the I.N.S. to make a determination of deportability, if and when, the subject of the notice becomes available at a later time.” Waldron v. INS, 17 F.3d 511, 515 (2d Cir.1994) (internal quotation marks and brackets omitted). And, the language and legislative histories of the IIRIRA and the AEDPA seem to us to be clear that deportation proceedings may not be deemed to have begun with the issuance of a detainer notice. We are, therefore, unpersuaded by Petitioner’s claim that the issuance of a detainer notice prevents the application of the IIRIRA and the AEDPA to his case.
III.
Petitioner’s final claim is that, even if his removal proceedings began in 1998, the doctrine of laches should preclude the government from applying post-1990 law,10 since thé INS waited an allegedly “inordinate” amount of time from the date of his murder conviction to institute proceedings against him.11
The government responds, inter alia, that the defense of laches may not be invoked against it in this context.12 See United States v. Angell, 292 F.3d 333, 338 (2d Cir.2002) (“[LJaches is not available against the federal government when it undertakes to enforce a public right or protect the public interest.”); see also Costello v. United States., 365 U.S. 265, 281-82, 81 S.Ct. 534, 5 L.Ed.2d 551 (1961) (noting that “[i]t has consistently been held in the lower courts that delay which might support a defense of laches in ordinary equitable proceedings between private litigants will not bar a denaturalization proceeding brought by the Government,” but reserving the question). Rather than deciding the question, we, like the Supreme Court in Costello, find it more expedient to dispose of Petitioner’s claim on its specific merits.13
*166In considering Petitioner’s laches claim, it is important to make clear what Petitioner is not arguing. He is not, for example, asserting that the government’s conduct in this case rose to the level of a due process violation. Cf. Singh v. Reno, 182 F.3d 504, 507 (7th Cir.1999) (finding that an alien had stated a substantial due process claim where the INS filed an Order to Show Cause in 1992, but then “drag[ged] its feet,” despite the alien’s pleas for a hearing, until it finally held a hearing in late 1996, after the AEDPA had abrogated his right to seek 212(c) relief).
Similarly, Petitioner’s laches claim should be distinguished from an argument sounding in the presumption against retro-activity. One can imagine a case in which the INS has for years declined to bring deportation proceedings against an alien, despite his conviction for a deportable crime, because, in the INS’s estimation, the alien would be a very strong candidate for 212(c) relief. Cf. Matter of Gordon, 17 I. & N. Dec. 389, 392, 1980 WL 121901 (BIA 1980) (noting that an INS District Director “has every right, in fact, a duty, to exercise his prosecutive judgment whether or not to institute a deportation proceeding against an alien .... If, in screening the file of, and possibly after consultation with, such an alien, it appears to him that a deportation proceeding would surely result in a grant of section 212(c) relief ... it would be pointless to institute an expensive, vexatious, and needless deportation proceeding.”). Such an alien might reasonably rely on the INS’s inaction and decide on that basis to make important commitments to his residency in the United States (such as by marrying, establishing a business, and losing ties with his home country) only later to find that, after Congress had eliminated 212(c) relief, the INS seeks to deport him. Under these circumstances — and where Congress’s intent as to the retroactivity of the elimination of .212(c) relief is unclear — an alien might argue with some force that he has demonstrated the kind of reasonable reliance and settled expectations under Landgraf 511 U.S. at 270, 114 S.Ct. 1483, that would render the elimination of 212(c) relief impermissibly retroactive if applied to him.14
Unlike a laches defenses, this retroactivity argument — which is not before us and as to the validity of which we therefore express no opinion15 — focuses on .the reasonableness of an alien’s reliance on the continued availability of 212(c) relief. As a result, the diligence of the INS’s conduct is not particularly relevant to it.
Diligence is, by contrast, crucial to the defense of laches. A party claiming this defense must establish two elements: 1) a lack of diligence by the party against whom the defense is asserted, and 2) prejudice to the party asserting the defense. Costello, 365 U.S. at 282, 81 S.Ct. 534. Petitioner cannot establish either element. We find no lack of diligence in the INS’s decision to institute deportation proceedings three years before the expiration of *167Petitioner’s twenty-year minimum sentence. If the INS had instituted deportation proceedings immediately after Petitioner’s 1982 murder conviction, or at any time until shortly before the expiration of his minimum term, it might well have been a colossal waste of time. Any number of events might make his later deportation unnecessary or inappropriate. For example, Petitioner might not survive until the end of his long prison term. Conditions in the country to which he would be deported might preclude his immediate deportation upon release, see 8 C.F.R. § 208.17(a) (providing for deferral of removal under the Convention Against Torture, where it is more likely than not that the alien will be tortured if deported), thus making the INS’s resources better used elsewhere. And, the law with respect to deportation of aliens like Petitioner might change so as to make deportation impossible or unlikely. See generally Cheryl Shanks, Immigration and the Politics of American Sovereignty, 1890-1990 (2001) (documenting cycles in immigration policy over the last century). For these and other similar reasons, delay in a case like the one before us, far from indicating a lack of diligence, suggests common sense on the part of the INS.
Moreover, it is highly unlikely that Petitioner would have received 212(c) relief, given the seriousness and recency of his crime, had proceedings been instituted earlier in his prison term. See, e.g., Matter of Rodriguez-Vera, 17 I. & N. Dec. 105, 107, 1979 WL 44368 (BIA 1979) (stating that the alien’s murder conviction is an “extremely serious negative factor which may be overcome only by a showing of unusual or outstanding equities,” and noting that the alien’s opportunity to demonstrate rehabilitation is “of necessity limited inasmuch as he is in the early stages of serving a fifteen and one-half year prison sentence”). Under the circumstances, it would be hard to say that Petitioner has met his burden of showing that he was prejudiced by the INS’s alleged delay.
CONCLUSION
Having determined that Petitioner is ineligible for 212(c) relief, we AFFIRM the district court’s denial of his habeas corpus petition.
. This agency is now called the Bureau of Citizenship and Immigration Services, but we will refer to it as the INS in view of the period in which this case arose.
. The IJ also denied other forms of relief to Petitioner, such as cancellation of removal. Because these forms of relief are not at issue in this appeal, we will not discuss them further.
. An earlier panel of this court appointed counsel and issued a certificate of appealability (COA) on the issue of whether Petitioner's murder conviction was obtained pursuant to a guilty plea and, if so, whether INS v. St. Cyr, 533 U.S. 289, 121 S.Ct. 2271, 150 L.Ed.2d 347 (2001), applied. But, because this habeas petition was brought under 28 U.S.C. § 2241, the COA requirement of 28 U.S.C. § 2253 does not apply. See Drax v. Reno, 338 F.3d 98, 106 n. 12 (2d Cir.2003). Our review is therefore not limited by the COA.
. See also Mattis v. Reno, 212 F.3d 31, 39-40 (1st Cir.2000) ("[TJhere is reason to believe that there might be some aliens who [decide to plead guilty] in actual and reasonable reliance on the availability of § 212(c) relief. Good defense counsel in criminal cases often advise clients about immigration law consequences. There may well be those who pled despite having a colorable defense because the act of accepting responsibility would bode well for their § 212(c) application. Similarly, there may be aliens who pled to lesser offenses than those charged in order to ensure that they would serve less than five years of prison time.”).
. In this respect, we note that the Ninth Circuit relied on St. Cyr's reasoning to hold that the five-year bar itself may not be applied retroactively to an alien who pleads guilty. See Toia v. Fasano, 334 F.3d 917, 920-21 (9th Cir.2003) ("We hold that St. Cyr compels the result in this case.”). Under this holding, reasons other than the possible avoidance of the five-year rule had to be involved in the alien’s guilty plea.
. Speaking only for myself: If I were judging on a clean slate, I would read the Supreme Court's seminal decision on civil retroactivity, Landgraf v. USI Film Prods., 511 U.S. 244, 114 S.Ct. 1483, 128 L.Ed.2d 229 (1994) — at a minimum — to say that, where Congress has not made its intent clear, courts should presume that any civil statute that would be considered ex post facto in the criminal context was meant to apply prospectively only. (This reading would be particularly appropriate in cases where, as here, the civil law in question imposes consequences very like those of criminal penalties. See, e.g., Fong Haw Tan v. Phelan, 333 U.S. 6, 10, 68 S.Ct. 374, 92 L.Ed. 433 (1948) (“[DJeportation is a drastic measure and at times the equivalent of banishment or exile.”).) Indeed, I believe Landgraf goes even further and that its anti-retroactivity presumption is triggered by statutes whose retroactive application, while not the equivalent of criminal ex post facto, nevertheless would run afoul of "familiar considerations of fair notice, reasonable reliance, and settled expectations.” Landgraf, 511 U.S. at 270, 114 S.Ct. 1483. And, I would expect that the Supreme Court’s future decisions in this field will confirm such readings of Land-graf. I would, therefore, be very much inclined to agree with the dissent that the IIRI-RA and the AEDPA do not bar Petitioner from 212(c) relief. I would be so inclined, that is, were it not for the fact that I am unconvinced by the dissent's ingenious interpretation of Domond v. U.S. INS, 244 F.3d 81 (2d Cir.2001), and Rankine, 319 F.3d 93. Instead, I read those cases as foreclosing the argument that the conviction of an alien, without more, presents a retroactivity problem.
. Moreover, as the tribunals below recognized, even if the IIRIRA and the AEDPA do not apply to Petitioner, the five-year bar would independently preclude him from seeking 212(c) relief. In Buitrago-Cuesta v. INS, 7 F.3d 291, 292 (2d Cir.1993), this court held that the five-year bar applies retroactively to aliens who were convicted before Congress established that bar in 1990. Petitioner maintains, however, that Buitrago-Cuesta’s reasoning was undermined by the Supreme Court’s subsequent retroactivity cases, such as Landgraf v. USI Film Prods., 511 U.S. 244, 114 S.Ct. 1483, 128 L.Ed.2d 229 (1994), and St. Cyr, 533 U.S. 289, 121 S.Ct. 2271, 150 L.Ed.2d 347. While we have recently sug*164gested that, in light of St. Cyr, Buitrago-Cues-ta's holding may perhaps have to be read not to apply to aliens who pleaded guilty before the enactment of the five-year bar, see, e.g., Theodoropoulos v. INS, 358 F.3d 162, 168 (2d Cir.2004) (citing, inter alia, De Cardenas v. Reno, 278 F.Supp.2d 284, 294 (D.Conn.2003)), it is clear that Buitrago-Cuesta remains good law with respect to this case, where the conviction was obtained after a trial, see Reid v. Holmes, 323 F.3d 187, 189 (2d Cir.2003) (per curiam).
. Even if Petitioner were correct, it might be that the five-year bar would independently preclude him from 212(c) eligibility. Buitra-go-Cuesta seemingly did not address whether the five-year bar applies retroactively to pending proceedings, and, in view of our holding, see infra, that Petitioner's removal proceedings commenced in 1998, we need not consider whether it does.
. Since both the service and filing of the Notice to Appear occurred after April 1, 1997, we need not address an issue that has divided some circuits. Compare, e.g., Jimenez-Angeles v. Ashcroft, 291 F.3d 594, 598 (9th Cir.2002) (holding that, for purposes of the IIRIRA, proceedings commence only upon the INS’s filing of a Notice to Appear with the immigration court); Armendariz-Montoya v. Sonchik, 291 F.3d 1116, 1119 (9th Cir.2002) (same in AEDPA context); DeLeon-Holguin v. Ashcroft, 253 F.3d 811, 814 (5th Cir.2001) (same) with Cunningham v. Attorney General, 335 F.3d 1262, 1267 (11th Cir.2003) (per curiam) (holding, in the IIRIRA context, that service of the Notice to Appear was, on the facts of that case, sufficient to start proceedings); Alanis-Bustamante v. Reno, 201 F.3d 1303, 1304 (11th Cir.2000) (holding, in the IIRIRA context, that the combination of service of the Order to Show Cause and the issuance of a *165detainer notice sufficed to begin the proceedings).
. Although Petitioner is unclear on this point, we interpret him to be arguing that the INS should be barred from applying the five-year bar as well as the IIRIRA and the AED-PA.
. To support his claim that this sixteen-year period was excessive, Petitioner points to a statutory provision that was in place during part of the relevant time. That provision required that, "in the case of an alien who is convicted of an offense which makes the alien subject to deportation, the Attorney General shall begin any deportation proceeding as expeditiously as possible after the date of the conviction.” 8 U.S.C. § 1252(i) (1988).
. The government also asserts that 8 U.S.C. § 1252(g) deprives this court of jurisdiction to consider the claim, since it involves the Attorney General’s discretionary decision to "com-menee proceedings, adjudicate cases, or execute removal orders.” § 1252(g); see also Reno v. American-Arab Anti-Discrim. Comm., 525 U.S. 471, 119 S.Ct. 936, 142 L.Ed.2d 940 (1999) (interpreting this provision). Given our disposition of Petitioner's claim, however, we need not address this non-constitutional jurisdictional argument. See Fama v. Comm’r of Corr. Servs., 235 F.3d 804, 816 n. 11 (2d Cir.2000).
.In contrast with the various decisions on laches, it seems settled that the government may, in the appropriate circumstances, be equitably estopped in the immigration context. See, e.g., Rojas-Reyes v. INS, 235 F.3d 115, 126 (2d Cir.2000); Drozd v. INS, 155 F.3d 81, 90 (2d Cir.1998); Corniel-Rodriguez v. INS, 532 F.2d 301, 307 (2d Cir.1976). Petitioner, however, specifically denies that he is making an equitable estoppel claim.
. This would be especially so if the alien could show that part of his reliance was based on the fact that' — during the relevant period— the BIA regularly granted 212(c) relief to aliens whose 212(c) applications were considerably weaker than his own. We note in this regard that, in the years preceding the AED-PA, over half of the applications for 212(c) relief were successful. See St. Cyr, 533 U.S. at 296 n. 5, 121 S.Ct. 2271.
. It is, in any event, doubtful that such a claim would succeed on the facts of this case. An incarcerated alien seems unlikely to be able to claim to be surprised by the INS’s decision to postpone removal proceedings until near the end of his minimum prison term, and, hence, credibly to assert that he made life shaping decisions relying on the INS’s disinclination to institute proceedings against him.