Samir M. Alim petitions for review of a final order of the Board of Immigration Appeals, which affirmed, without opinion, a decision of an immigration judge (“IJ”) denying claims for withholding of removal under 8 U.S.C. § 1231(b)(3), and withholding of removal under the United Nations Convention Against Torture and Other Cruel, Inhuman, or Degrading Treatment or Punishment (“CAT”), Pub.L. 105-277, § 2242, 112 Stat. 2681-761, 2681-822 (1998). See 8 C.F.R. § 208.16(b)-(c). For the reasons discussed below, we dismiss the petition in part, and deny the petition in part.
I. Factual and Procedural Background
Mr. Alim, a native and citizen of Syria, was admitted to the United States in September of 1990 as a non-immigrant visitor for pleasure, with authorization to remain for six months. Upon admission, he presented a Bolivian passport and a U.S. non-immigrant visa issued in the name of Carlos Cabrera. He remained in the country longer than the six months authorized, and had two children in the U.S. with a Bolivian woman named Gina Ibanez. Ms. Iba-nez returned to Bolivia with the children in 1997.
In 1997, Mr. Alim married a U.S. citizen named Lora, who filed a visa petition for the benefit of Mr. Alim. Lora gave birth to a child in the U.S. in 1997. In 1998, Mr. Alim was arrested for assaulting Lora, and pled nolo contendere (or no contest) in Florida circuit court for domestic battery in violation of Fla. Stat. § 784.03(1)(A). Adjudication was withheld, and Mr. Alim was sentenced to nine months’ probation, fined $100, and ordered to stay away from Lora. Lora proceeded with the visa petition, and she and Mr. Alim were interviewed by the Immigration and Naturalization Service in January of 1999. At that interview, Mr. Alim stated that he had never been arrested or convicted of a crime. In July of 1999, Mr. Alim traveled to Syria for one month, and then to Bolivia.
In October of 1999, Mr. Alim was indicted in federal court for making false statements at his INS interview, in violation of 18 U.S.C. § 1001. Lora withdrew the visa petition, and divorced Mr. Alim in November of 1999.
A. The Immigration Proceedings
On January 10, 2000, the INS served a notice to appear on Mr. Alim, commencing removal proceedings. The notice charged Mr. Alim with removability on various grounds: (1) under 8 U.S.C. § 1227(a)(1)(A), as an alien inadmissible at the time of entry, for seeking to procure a visa or admission into the U.S. by fraud, in violation of 8 U.S.C. § 1182(a)(6)(C)(i); (2) under 8 U.S.C. § 1227(a)(1)(A), as an alien inadmissible at the time of entry, for not being in possession of valid entry documentation, in violation of 8 U.S.C. § 1182(a)(7)(A)(i)(I); (3) under 8 U.S.C. § 1227(a)(1)(B), as an alien present in the U.S. for a period of time longer than originally permitted; and (4) under 8 U.S.C. § 1227(a) (2) (E) (i), for committing a crime of domestic violence after admission to the U.S.
On April 5, 2000, Mr. Alim married another U.S. citizen, Elizabeth. As had Lora, Elizabeth also filed a visa petition for Mr. Alim’s benefit.
Mr. Alim was convicted on the federal false statements charge on April 12, 2000. The INS subsequently amended its charges against Mr. Alim on May 9, 2000, alleging that he was also subject to removal under 8 U.S.C. § 1227(a)(2)(A)(ii) as an *1243alien convicted after admission to the U.S. of two or more crimes involving moral turpitude (i.e., the 1998 domestic battery-plea and the 2000 false statements conviction).
An IJ held a hearing on September 28, 2000. With one exception, Mr. Alim admitted all of the factual allegations supporting the INS’ charges. In order to preserve his claim for cancellation of removal, Mr. Alim denied that he sought to enter the U.S. by fraud. At some time before the hearing, Mr. Alim submitted an application for cancellation of removal, presumably under 8 U.S.C. § 1229b. Mr. Alim also explained that he was planning on filing an application for adjustment of status to that of a permanent resident under 8 U.S.C. § 1255, but had yet to do so because Elizabeth’s visa petition was pending. The IJ explained that Mr. Alim did not meet the 10-year continuous residence requirement to be eligible for cancellation of removal. He then returned the cancellation of removal application to Mr. Alim’s counsel, without objection.
In November of 2000, Mr. Alim filed a petition for a writ of error coram nobis in the Florida circuit court where he pled no contest to domestic battery in 1998. He sought to vacate his plea under Rule 3.172 of the Florida Rules of Criminal Procedure because the court had not advised him of the potential immigration consequences. The state responded by filing a short memorandum. The state did not challenge the factual allegations made by Mr. Alim, but asked the court to convert the disposition of the case to a “nolle prosequi,”1 which the state court clerk did on March 2, 2001.
In early 2002, Elizabeth’s visa petition on behalf of Mr. Alim was approved. In March of 2002, Mr. Alim filed an application to adjust his status to that of a permanent resident under 8 U.S.C. § 1255. Elizabeth, however, withdrew her visa petition some time later in 2002.
The IJ held another hearing on January 17, 2003. Mr. Alim admitted to being removable under three of the five grounds alleged by the INS. He denied removability under 8 U.S.C. § 1227(a)(2)(E)®, for being convicted of a crime of domestic violence, and denied removability under 8 U.S.C. § 1227(a)(2)(A)(ii), for being convicted of two crimes involving moral turpitude after admission. The IJ found that all of the charges supporting removability were sustained by clear and convincing evidence. At the conclusion of the hearing, Mr. Alim said that he would be filing an application for withholding of removal and relief under the U.S. implementation of the CAT.
On February 13, 2003, Mr. Alim filed an application for asylum under 8 U.S.C. § 1158, withholding of removal under 8 U.S.C. § 1231(b)(3), and withholding of removal under the CAT. At an evidentiary hearing on May 20, 2003, Mr. Alim offered copies of the U.S. Department of State reports on Syria and his own testimony. There was no other evidence presented. After the IJ noted that the application was untimely insofar as it requested asylum, Mr. Alim testified in support of his claims for withholding of removal under § 1231(b)(3) and withholding of removal under the CAT.
B. Mr. Alim’s Testimony and the Immigration Judge’s Ruling
Mr. Alim, 39 years old at the time of the May 30, 2003 hearing, testified that he has *1244been a Christian since he was baptized at the age of one, and that his family is Christian. He has no family in Syria to support him financially because Christians suffer extreme discrimination and have trouble finding work on account of their religion.
When he was in his early twenties, his cousin, also a Christian, left Syria to fight in a Lebanese civil war on behalf of Christians. A family member told Mr. Aim that his cousin was shot and killed in Lebanon by Muslims because he was suspected of being a spy for Israel. The family member also showed Mr. Aim a picture of the cousin sitting on top of an Israeli tank. Mr. Aim does not know how the family member knew how or why the cousin was killed. Mr. Aim could not produce a death certificate or other physical evidence relating to his cousin’s death.
When he was a teenager, Mr. Aim joined a group called the “Christian Unity Brothers.” As a member of this group, Mr. Aim worked at converting Muslims to Christianity. There was a “bad point” or “black point” in his school records, and “negative reports” against him because he was a member of this group. Certain unidentified Muslims also went “after him” for being an outspoken Christian. While in civilian life, however, Mr. Aim was never arrested, detained, or imprisoned for any reason.
Mr. Aim joined the Syrian air force in 1981. Neither his Christian faith, nor his membership in the Christian Unity Brothers, precluded him from serving in the military. Athough his superiors did not know he was in a specific group, they did know Mr. Aim was an outspoken Christian. Sometime in 1987 or 1988, while he was still in the air force, one of his friends, also a Christian, was chased and shot by a group of Muslims.
Mr. Aim was never detained, arrested, or imprisoned while serving in the military. He was automatically promoted at least once during his eight years of service. He testified, however, that the Syrian military discriminates against its Christian servicemen in job placements. He was therefore denied certain rights and treated badly while serving in the military.
In mid-1989, Mr. Aim deserted the Syrian military, and spent approximately six months traveling throughout the country in an effort to evade capture. In 1990, he was able to leave Syria illegally with the help of a friend. He boarded a flight to Bolivia, where he spent five or six months, before using a false Bolivian passport to enter the United States.
In 1999, Mr. Aim returned to Syria to visit his ill, 74-year-old mother, and spent 30 days there. He fraudulently entered and exited through Jordan with the help of an old friend, successfully evading Syrian immigration and law enforcement authorities. He first testified that he entered Syria with a false passport, but then said that the passport was not false, but merely misspelled his name. The IJ then indicated that this still constituted fraud.
Mr. Aim believed that if removed to Syria, he would be tortured, persecuted, or killed for being a Christian or for deserting the military. He further believed he would be imprisoned in a military prison named Palmera for deserting the military. He testified that prisoners at Palmera do not have visitation rights, cannot communicate with their families, and spend the rest of them lives incarcerated.
The IJ issued an oral decision adverse to Mr. Aim. The IJ found that Mr. Aim admitted all of the factual allegations supporting the INS’ charges of removability at the January 17, 2003, hearing, and found that Mr. Aim was removable on all five grounds alleged by the INS. The IJ *1245then proceeded to Mr. Alim’s claims for relief.2
The IJ did not mention Mr. Alim’s application for cancellation of removal, but found that Mr. Alim’s application for adjustment of status was abandoned because Elizabeth had withdrawn her visa petition, and Mr. Alim never sought a waiver of inadmissibility, which was required because of his criminal convictions. Alternatively, he ruled that even if this claim was not abandoned, he would deny Mr. Alim adjustment of status in the exercise of his discretion.
The IJ denied Mr. Alim’s asylum claim under 8 U.S.C. § 1158 as untimely. He noted that Mr. Alim was seeking asylum as a Christian from a predominantly Muslim country, and because he deserted the Syrian military. But he found that this did not reflect any changed conditions in Syria, or exceptional circumstances that would justify its late consideration.
The IJ proceeded to analyze the evidence Mr. Alim offered in support of his claims for withholding of removal under § 1231(b)(3) and the CAT. The IJ made an adverse credibility determination with respect to Mr. Alim. He also doubted Mr. Alim’s credibility because he had committed multiple acts of fraud both in the U.S. and Syria. He doubted whether Mr. Alim would actually be persecuted or tortured if removed, given that he spent six months in Syria after deserting the military without being captured, and -willingly returned to Syria in 1999 for 30 days to visit his mother. Finally, he noted an inconsistency in Mr. Alim’s testimony. Mr. Alim first testified that, in 1999, he re-entered Syria with a false passport, but then testified that the passport was valid, and only incorrectly spelled his name.
The IJ rejected the § 1231(b)(3) and CAT claims insofar as they were based on the possibility of persecution or torture on account of Mr. Alim’s Christian faith. He found that Mr. Alim’s case-in-chief was based on his cousin being killed in Lebanon, but found this testimony highly speculative and conclusory. He also rejected the claims because Mr. Alim was never detained or arrested either in private or military life for being a Christian, despite his open practice of Christianity. He further rejected Mr. Alim’s CAT claim insofar as it was based on the threat of torture on account of his military desertion and illegal exit from Syria in 1990. He doubted whether Mr. Alim actually deserted the military. To the extent he believed that Mr. Alim deserted the military, he was not convinced that, if removed, Mr. Alim would actually be caught for deserting and leaving Syria illegally. In case Mr. Alim was caught for deserting and leaving illegally, the IJ doubted that he would be punished unreasonably.
Mr. Alim appealed the IJ’s decision to the BIA. His brief to the BIA stated that the IJ denied his § 1231(b)(3) and CAT claims for withholding removal, and repeated, practically verbatim, the IJ’s factual findings. His brief did not mention his application for cancellation of removal. As for his application for adjustment of status, he mentioned that the IJ found it to be abandoned, but did not dispute the IJ’s ruling. He argued that the IJ erred in making an adverse credibility finding, and in finding he did not meet the burden of proof for asylum — a well-founded fear of persecution. In his conclusion, he request*1246ed that the BIA grant him asylum under § 1158, withholding of removal under 8 U.S.C. § 1253(h),3 and/or withholding of removal under the CAT. The BIA summarily affirmed the IJ’s order without an opinion, and Mr. Alim filed a timely petition for review here.
II. Jurisdiction
We must first consider whether we have subject-matter jurisdiction to hear Mr. Alim’s petition. See, e.g., Resendiz-Alcaraz v. U.S. Attorney Gen., 383 F.3d 1262, 1266 (11th Cir.2004). The government argues that we lack subject-matter jurisdiction over the petition for two reasons. First, 8 U.S.C. § 1252(a)(2)(C) strips us of subject-matter jurisdiction because Mr. Alim was convicted of two crimes involving moral turpitude. Second, Mr. Alim failed to exhaust his administrative remedies as to his claims before the BIA. The government’s first argument relates to the petition as a whole, while the second is claim-specific. We address each argument in turn.
A. 8 U.S.C. § 1252(a)(2)(C)
Our jurisdiction to review final orders of removal is limited by 8 U.S.C. § 1252(a)(2)(C), which provides:
Notwithstanding any other provision of law (statutory or nonstatutory), including section 2241 of Title 28, or any other habeas corpus provision, and sections 1361 and 1651 of such title, and except as provided in subparagraph (D), no court shall have jurisdiction to review any final order of removal against an alien who is removable by reason of having committed a criminal offense covered in section 1182(a)(2) or 1227(a)(2)(A)(iii), (B), (C), or (D) of this title, or any offense covered by section 1227(a)(2)(A)(ii) of this title for which both predicate offenses are, without regard to their date of commission, otherwise covered by section 1227(a)(2)(A)(i) of this title.
This provision strips us of jurisdiction to “review a final order of removal of (1) an alien, (2) who is removable, (3) because he committed a criminal offense enumerated in the statute.” Resendiz-Alcaraz, 383 F.3d at 1266 (citing Fernandez-Bernal v. U.S. Attorney Gen., 257 F.3d 1304, 1308 (11th Cir.2001)).
We agree with the parties that the only relevant statutory provisions referenced in § 1252(a)(2)(C) that could strip us of subject-matter jurisdiction are §§ 1227(a)(2)(A)(i) and (ii), which provide as follows:
(i) Crimes of moral turpitude
Any alien who—
(I) is convicted of a crime involving moral turpitude committed within five years (or 10 years in the case of an alien provided lawful permanent resident status under section 1255(j) of this title) after the date of admission, and
(II) is convicted of a crime for which a sentence of one year or longer may be imposed,
is deportable.
(ii) Multiple criminal convictions
Any alien who at any time after admission is convicted of two or more crimes involving moral turpitude, not arising out of a single scheme of criminal misconduct, regardless of whether confined therefor and regardless of whether the convictions were in a single trial, is de-portable.
*1247So, whether we have subject-matter jurisdiction depends on whether Mr. Aim is removable for the reason stated in § 1227(a)(2)(A)(ii), for which both predicate offenses are, without regard to their date of commission, otherwise covered by § 1227(a)(2)(A)®. See 8 U.S.C. § 1252(a)(2)(C).
We turn to §§ 1227(a)(2)(A)® and (ii) to determine whether Mr. Aim’s 2000 conviction and 1998 plea meet the statutory requirements. There is no dispute that his 2000 conviction for making false statements to the INS is a crime involving moral turpitude, and is covered by § 1227(a)(2)(A)®. See Itani v. Ashcroft, 298 F.3d 1213, 1215 (11th Cir.2002) (crimes involving false statements are crimes of moral turpitude). There is also no dispute that the false statements conviction and the 1998 domestic battery plea do not arise out of a single scheme of criminal misconduct. See 8 U.S.C. § 1227(a)(2)(A)(ii). Thus, subject-matter jurisdiction depends on whether Mr. Aim’s 1998 domestic battery plea counts as a second conviction for purposes of § 1227(a)(2)(A)® & (ii), and, thus, for purposes of § 1252(a)(2)(C). The answer to that question is no.
The 1998 domestic battery plea was vacated because Mr. Aim was not advised— as required by Florida law — of the immigration consequences when he pled no contest. Thus, the narrow jurisdictional question is whether an alien remains “convicted” of an offense, as that term is defined in the Immigration and Nationality Act, after the conviction or plea has been vacated on the merits to remedy a violation of constitutional or statutory rights that occurred during the underlying criminal proceeding.
The INA defines the term “conviction” in 8 U.S.C. § 1101(a)(48)(A) as follows:
(a) As used in this chapter—
(48) The term “conviction” means, with respect to an alien, a formal judgment of guilt of the alien entered by a court or, if adjudication of guilt has been withheld, where—
(i) a judge or jury has found the alien guilty or the alien has entered a plea of guilty or nolo contendere or has admitted sufficient facts to warrant a finding of guilt, and
(ii) the judge has ordered some form of punishment, penalty, or restraint on the alien’s liberty to be imposed.
(emphasis added).
As explained a bit later, the BIA has construed § 1101(a)(48)(A), and thus, we are confronted with “an agency’s construction of the statute which it administers.” Chevron U.S.A., Inc. v. Natural Resources Defense Council, Inc., 467 U.S. 837, 842, 104 S.Ct. 2778, 81 L.Ed.2d 694 (1984). In such a case, we are required to conduct a two-step analysis:
First, always, is the question whether Congress has directly spoken to the precise question at issue. If the intent of Congress is clear, that is the end of the matter; for the court, as well as the agency, must give effect to the unambiguously expressed intent of Congress. If, however, the court determines Congress has not directly addressed the precise question at issue, the court does not simply impose its own construction on the statute, as would be necessary in the absence of an administrative interpretation. Rather, if the statute is silent or ambiguous with respect to the specific issue, the question for the court is whether the agency’s answer is based on a permissible construction of the statute.
Id. at 842-43,104 S.Ct. 2778.
1. The Statute’s Silence
The words of a statute are normally ascribed their plain meaning, see, e.g., Con *1248 solidated Bank, N.A. v. U.S. Dep’t of Treasury, 118 F.3d 1461, 1463 (11th Cir.1997), but § 1101(a)(48)(A) does not specify how to treat a nolo contendere plea which has subsequently been vacated on the merits to remedy a violation of the alien’s constitutional or statutory rights. The statute defines a conviction up through the time of sentence, but says nothing about what effect, if any, the conviction or plea should be given when there is a subsequent vaca-tur because the alien’s statutory or constitutional rights were violated during the underlying criminal proceeding. See, e.g., INS v. Aguirre-Aguirre, 526 U.S. 415, 424, 119 S.Ct. 1439, 143 L.Ed.2d 590 (1999) (court should ask “whether the statute is silent or ambiguous with respect to the specific issue before it ... ”) (quotations omitted).
We recognize our prior decision in Re-sendiz-Alcaraz, 383 F.3d at 1265-69, but do not find it controlling on this precise issue. In Resendiz-Alcaraz, we held that a conviction vacated pursuant to a state rehabilitative measure still counts as a “conviction” under § 1101(a)(48)(A). See id. A conviction vacated pursuant to a state rehabilitative measure still meets the literal definition of a “conviction” under § 1101(a)(48)(A), and it makes no difference that the conviction is later expunged. See id. at 1268 (“[T]he statutory definition on its face appears to negate for immigration purposes the effect of state rehabilitative measures that purport to expunge or otherwise remove a conviction.”). Resen-diz-Alcaraz, however, does not require us to hold that all vacated convictions or nolo contendere pleas, regardless of the circumstances, continue to count as “convictions” under § 1101(a)(48)(A). The actual holding of Resendiz-Alcaraz — as opposed to dicta in the opinion — is that the statute speaks clearly only as to vacatur or ex-pungement pursuant to state rehabilitative measures. The conviction in Resendiz-Alcaraz was not set aside because the alien’s statutory or constitutional rights were violated during the underlying criminal proceeding; it was expunged pursuant to a statute requiring that, where sentence is suspended, the case be closed and the conviction expunged, once the case is finally terminated. See id. at 1265. The situation presented here was not addressed in Resendiz-Alcaraz, and thus, that decision does not control this case. Indeed, Resen-diz-Alcaraz acknowledged that its holding did not govern a case like Mr. Alim’s:
As the First Circuit has noted, “[t]he emphasis that Congress placed on the original admission of guilt plainly indicates that a subsequent dismissal of charges, based solely on rehabilitative goals and not on the merits of the charge or on a defect in the underlying criminal proceeding, does not vitiate that original admission.” [Herrera-Inirio v. INS, 208 F.3d 299, 306 (1st Cir.2000)].
Id. at 1270 (emphasis added).
A hypothetical helps to illustrate that Congress did not expressly address the issue before us in § 1101(a)(48)(A). Suppose an alien is charged with a felony punishable by five years in prison. The alien does not speak much English, has spent only a short time in the U.S., and is completely unfamiliar with the American judicial system. Although he is indigent and constitutionally entitled to appointed counsel, see Gideon v. Wainwright, 372 U.S. 335, 343-44, 83 S.Ct. 792, 9 L.Ed.2d 799 (1963), no attorney is appointed to represent him. He decides, on the advice of his cellmate, to plead guilty. At change of plea hearing, the trial court does not advise him of his basic constitutional rights; the court does not tell him that he has the right to a trial by jury, the right to testify or not testify, and the right to court-appointed counsel if he is indigent. *1249With the court’s encouragement — and without knowing enough to be able to intelligently waive the right to counsel — he pleads guilty. The court adjudicates him guilty and sentences him to a year in prison. After he is sentenced, someone in jail tells him that the court should have provided him with an attorney and informed him of his basic constitutional rights. Based on this information, he files a pro se notice of appeal to challenge the guilty plea and sentence. The appellate court appoints counsel and, after briefing, notices the trial court’s obvious constitutional errors. Because uncounseled convictions are presumptively void, see, e.g., Burgett v. Texas, 389 U.S. 109, 115-16, 88 S.Ct. 258, 19 L.Ed.2d 319 (1967), the appellate court vacates the conviction and remands the case for appropriate proceedings. After the remand, the state decides not to pursue the matter any further and files a one-line memorandum asking the trial court to convert the disposition to a “nolle prosequi.” The court grants the request, thereby vacating the conviction, and the alien is released from custody.
If § 1101(a)(48)(A) did not permit consideration of any post-sentence vacaturs— regardless of the reason underlying the vacatur in question — the conviction in our hypothetical would remain a conviction for immigration purposes. So too would a conviction that was vacated on appeal (with a judgment of acquittal entered) due to insufficient evidence. These outcomes are so foreign, so antithetical, to the longstanding principles underlying our criminal justice system and our notions of due process that we would expect Congress to have spoken very clearly if it intended to effect such results. It has not, however, done so. See United States v. Sanges, 144 U.S. 310, 322, 12 S.Ct. 609, 36 L.Ed. 445 (1892) (“It is impossible to presume an intention on the part of Congress to make so serious and far-reaching an innovation in the criminal jurisprudence of the United States.”).
As we read § 1101(a)(48)(A), Congress did not address the effect to be given a conviction or nolo contondere plea that is subsequently vacated because of a defect in the underlying criminal proceeding. Given the statutory silence, we turn to see if the BIA has construed the statute, and, if so, whether that construction is entitled to deference under Chevron and its progeny.
2. The BIA’s Interpretation
The BIA, in a series of decisions, has ruled that the effect of a subsequent event on a conviction or nolo contondere plea under § 1101(a)(48)(A) depends on what the subsequent event is. If vacatur or expungement takes place pursuant to a state rehabilitative measure, there is still a conviction for purposes of § 1101(a)(48)(A).4 If, on the other hand, vacatur occurs because there was a legal defect in the underlying proceeding (i.e., a violation of a constitutional or statutory right), then there is no longer a conviction for purposes of the INA. See, e.g., In re Roldan-Santoyo, 22 I & N Dec. 512, 522-23, 1999 WL 126433 (BIA 1999), vac’d sub nom. Lujan-Armendariz v. I.N.S., 222 F.3d 728 (9th Cir.2000); In re Rodriguez-Ruiz, 22 I & N Dec. 1378, 1379-80, 2000 WL 1375514 (BIA 2000); In re Pickering, 23 I & N Dec. 621, 624, 2003 WL 21358480 (BIA 2003).
Recently, in a case very similar to this one, the BIA held that an Ohio narcotics *1250conviction no longer counts for immigration purposes if it has been set aside because the defendant was nob — as required by state law — advised of the immigration consequences of his guilty plea. See In re Adamiak, 23 I & N Dec. 878, 879-80, 2006 WL 307908 (BIA Feb. 8, 2006) (“Under these circumstances, we find that the Ohio court’s vacat[ur] of the respondent’s conviction should be recognized in immigration proceedings. In the absence of a statutory directive to the contrary, we are required by 28 U.S.C. § 1738 to give full faith and credit to this state court judgment.”).
We defer to the BIA’s interpretation of a statute if it is reasonable and does not contradict the clear intent of Congress. See, e.g., Jaggernauth v. U.S. Attorney Gen., 432 F.3d 1346, 1350 (11th Cir.2005). Today, we join those circuits that have found the BIA’s approach to be reasonable and entitled to deference. See Pinko v. Gonzales, 432 F.3d 193, 209-10 (3d Cir.2005) (“Given its long-standing, consistent practice, the agency may reasonably read the statutory language analyzed above to authorize its drawing this distinction among vacated convictions.”); Cruz-Garza v. Ashcroft, 396 F.3d 1125, 1129 (10th Cir.2005) (“In sum, the treatment of vacated convictions is now fairly well-settled. Notwithstanding the Fifth Circuit’s tenuous adherence to a categorical disregard of all vacaturs, the ‘rest of the nation’ has taken to the middle ground staked out by the BIA on the basis of the text and legislative history of § 1101(a)(48)(A).”); Sandoval v. I.N.S., 240 F.3d 577, 583 (7th Cir.2001) (conviction did not count under § 1101(a)(48)(A) where it was vacated pursuant to state procedure for remedying constitutional violations, and thus, fell “outside the category of [rehabilitative] statutes discussed in Roldan-Santoyo”) (decided while Rodriguez-Ruiz was only an interim decision).
Only the Fifth Circuit apparently disagrees with the BIA’s approach. See Renteria-Gonzalez v. U.S. Attorney Gen., 322 F.3d 804, 812-13 (5th Cir.2003). On reflection, we do not find Renteria-Gonza-lez persuasive. First, its rationale is contrary to ours (and that of the Third, Seventh, and Tenth Circuits). Second, the reasoning of Renteria-Gonzalezw&s strongly criticized by a concurring judge, as well as by a subsequent Fifth Circuit panel. See id. at 820 (Benavides, J., concurring) (criticizing the majority for “painting with too broad a brush,” and emphasizing “that none of the convictions in the five cases cited by the majority was vacated based on the merits of the underlying criminal proceeding, i.e., a violation of a statutory or constitutional right”); Discipio v. Ashcroft, 369 F.3d 472, 475 (5th Cir.2004) (“Thus, a person completely exonerated by the courts may nonetheless face removal as a convicted criminal. We should interpret statutes to avoid results so patently absurd, ... and constitutionally questionable.”) (citations omitted), vac’d on denial of rehearing en banc, 417 F.3d 448, 450 (5th Cir.2005). That criticism, in our view, was well-founded.
3. Application of the BIA Approach
After removal proceedings commenced, Mr. Alim filed a petition for a writ of error coram nobis in the Florida circuit court where he pled no contest to domestic battery. His petition specifically alleged that, at the time of -his plea, the court did not advise him that he could be deported. Mr. Alim’s petition specifically mentioned Rule 3.172 of the Florida Rules of Criminal Procedure.
Rule 3.172(c)(8) requires that a court accepting a plea inform the defendant “that if he or she is not a United States citizen, the plea may subject him or her to *1251deportation ...” Where the defendant proves he has been prejudiced, a court’s failure to inform him of this potential consequence renders the plea void as involuntary. See, e.g., Peart v. Florida, 756 So.2d 42, 45-46 (Fla.2000); Marriott v. Florida, 605 So.2d 985, 987-88 (Fla. 4th DCA 1992). A petition for writ of error coram nobis is the method by which an out-of-custody criminal defendant in Florida can vacate such an involuntary plea. See Peart, 756 So.2d at 45-46; Florida v. Seraphin, 818 So.2d 485, 487 (Fla.2002).
The state responded to Mr. Alim’s co-ram nobis petition by filing a one-page memorandum asking the clerk to convert the disposition of the case to a “nolle pro-sequi.” The state court clerk subsequently filed a one-page document granting the state’s request, thereby showing that the no contest plea was vacated.
The BIA’s decision in Adamiak is directly on point. Like Ohio law, Florida law requires that a court inform a criminal defendant who is not a citizen of the immigration consequences of his plea. Like the defendant in Adamiak, Mr. Alim was not informed of this consequence, as required by state law. And like the defendant’s plea in Adamiak, Mr. Alim’s plea was vacated to remedy this legal defect in the underlying criminal proceeding. Mr. Alim’s 1998 no contest plea to domestic battery is therefore no longer a “conviction” under § 1101(a)(48)(A). See Adamiak, 23 I & N Dec. at 879-880.
The only difference between Adamiak and this case is that the state court order vacating the defendant’s conviction in Adamiak expressly noted the state law pursuant to which the conviction was vacated. The state court order here does not mention Rule 3.172. It merely mentions the prosecutor’s memorandum, which also does not cite to Rule 3.172. Thus, it could be argued that while we know that the conviction in Adamiak was vacated to remedy a violation of a specified right, we may not know exactly why Mr. Alim’s plea was vacated. Because Mr. Alim’s plea could have been vacated for reasons other than to remedy a violation of Rule 3.172, perhaps it should still be treated as a “conviction” under § 1101(a)(48)(A). The government, in fact, raised this point at oral argument.
But we see no reason why we cannot look to Mr. Alim’s coram nobis petition for the reason underlying the state court’s decision to vacate the plea. That, in fact, is what the BIA and the federal courts have done. See, e.g., Pickering, 23 I & N Dec. at 625 (BIA turned to the affidavit of alien in support of his petition to vacate his conviction because the Canadian court’s order did not reference any law pursuant to which the conviction was vacated); Pinko, 432 F.3d at 215 (“If the order does not give a clear statement of reasons, the agency may look to the record before the court when the order was issued.”). On this record, we have no reason to doubt that Mr. Alim’s plea was vacated for the reason provided in his petition. This is particularly so because the state did not challenge or contest Mr. Alim’s factual allegations.
In sum, the 1998 no contest plea was vacated to remedy a violation of Mr. Alim’s rights under Florida law. Under the BIA’s interpretation of § 1101(a)(48)(A), to which we defer, Mr. Alim is not “convicted” of domestic battery for immigration purposes. Because Mr. Alim was not convicted of two crimes involving moral turpitude, 8 U.S.C. § 1252(a)(2)(C) does not strip us of subject-matter jurisdiction over his petition. We now turn to the government’s argument that we lack subject-matter jurisdiction over specific claims.
*1252B. Exhaustion of Administrative Remedies
The government argues that we lack subject-matter jurisdiction because Mr. Alim failed to exhaust his administrative remedies as to each claim for relief that he made throughout his removal proceedings. As noted earlier, Mr. Alim raised five different claims at various points in the removal proceedings: (1) cancellation of removal under 8 U.S.C. § 1229b; (2) asylum under 8 U.S.C. § 1158; (3) withholding of removal under 8 U.S.C. § 1231(b)(3); (4) withholding of removal under the CAT; and (5) adjustment of status under 8 U.S.C. § 1255. We do not consider the claim for adjustment of status under 8 U.S.C. § 1255 because Mr. Alim has abandoned it on appeal. See Sepulveda v. U.S. Attorney Gen., 401 F.3d 1226, 1228 n. 2 (11th Cir.2005). We dismiss the claim for asylum for lack of subject-matter jurisdiction on a different ground, and dismiss the cancellation of removal claim because that claim was not raised before the BIA. As to the claims for withholding of removal under 8 U.S.C. § 1231(b)(3), and withholding of removal under the CAT, we conclude that Mr. Alim exhausted his administrative remedies, and reach the merits of those claims.
1. Asylum
Although the parties did not brief this specific issue, we are “obligated to inquire into subject-matter jurisdiction sua sponte whenever it may be lacking.” Chacon-Botero v. U.S. Attorney Gen., 427 F.3d 954, 956 (11th Cir.2005) (quotations omitted). An alien may not apply for asylum “unless [he] demonstrates by clear and convincing evidence that the application has been filed within 1 year after the date of the alien’s arrival in the United States.” 8 U.S.C. § 1158(a)(2)(B). An untimely application may be considered in certain circumstances:
An application for asylum may be considered notwithstanding subparagraphs (B) and (C), if the alien demonstrates to the satisfaction of the Attorney General either the existence of changed circumstances which materially affect the applicant’s eligibility for asylum or extraordinary circumstances relating to the delay in filing an application within the period specified in subparagraph (B).
8 U.S.C. § 1158(a)(2)(D). Questions of timeliness and the applicability of these exceptions are left exclusively to the Attorney General. The immediately subsequent provision, entitled “Limitation on judicial review,” provides that “[n]o court shall have jurisdiction to review any determination of the Attorney General under paragraph (2).” 8 U.S.C. § 1158(a)(3).
According to § 1158(a)(3), a court does not have subject-matter jurisdiction to review an asylum application that is denied as untimely under § 1158(a)(2)(B). See Fahim v. U.S. Attorney Gen., 278 F.3d 1216, 1218 (11th Cir.2002) (“We join the 8th and 9th Circuits in holding that the language of 8 U.S.C. § 1158(a)(3) precludes federal court review of determinations made by the Attorney General pursuant to 8 U.S.C. § 1158(a)(2).”). See also Chacon-Botero, 427 F.3d at 956-957; Sanchez v. U.S. Attorney Gen., 153 Fed.Appx. 698, 699 (11th Cir.2005).
The IJ denied Mr. Alim’s application for asylum pursuant to § 1158(a)(2). His oral decision, as it relates to Mr. Alim’s asylum application, provides:
FURTHER ORDERED respondent’s application of asylum is untimely and he has failed to establish an exceptional circumstance of changed country condition to warrant its consideration.
*1253A.R. at 47. The IJ thus denied the asylum application because it was untimely under § 1158(a)(2)(B), and because Mr. Alim failed to show changed or extraordinary circumstances under § 1158(a)(2)(D) to warrant its late consideration.
A review of Mr. Alim’s asylum claim would necessarily entail a review of the IJ’s basis for denying it. The BIA affirmed the IJ’s decision without an opinion, and thus, the IJ’s decision is the final order of removal. See Sepulveda, 401 F.3d at 1230. Because Mr. Alim’s asylum application was denied under § 1158(a)(2), we lack subject-matter jurisdiction pursuant to § 1158(a)(3) to review the final order of removal as it pertains to the asylum claim. See Chacon-Botero, 427 F.3d at 956-957; Fahim, 278 F.3d at 1218.
2. Remaining Claims
A court may review a final order of removal only if “the alien has exhausted all administrative remedies available to the alien as of right[.]” 8 U.S.C. § 1252(d)(1). This requirement is jurisdictional, “so we lack jurisdiction over claims that have not been raised before the BIA.” Sundar v. INS, 328 F.3d 1320, 1323 (11th Cir.2003). See also Fernandez-Bernal, 257 F.3d at 1317 n. 13. Cf. Asencio v. INS, 37 F.3d 614, 615-16 (11th Cir.1994) (interpreting predecessor exhaustion provision, 8 U.S.C. § 1105a(c)).
a. Cancellation op Removal under 8 U.S.C. § 1229b
Mr. Alim argues that the IJ erred in denying his request for cancellation of removal pursuant to 8 U.S.C. § 1229b. At some time before the September 28, 2000, hearing, Mr. Alim’s counsel submitted an application for cancellation of removal. After noting that Mr. Alim did not meet the 10-year continuous residence requirement to be eligible for cancellation of removal, the IJ returned the application to Mr. Alim’s counsel, without objection.5 We will assume that this constituted a denial of the application on the merits by the IJ. But in his appeal to the BIA, Mr. Alim never discussed the merits of his application for cancellation of removal, let alone the IJ’s basis for denying it. Neither his procedural summary of the proceedings before the IJ, nor his prayer for relief, mentioned his application for cancellation of removal. Mr. Alim therefore failed to exhaust his administrative remedies in regard to his application for cancellation of removal, and thus, we lack subject-matter jurisdiction over this claim. See 8 U.S.C. § 1252(d)(1); Sundar, 328 F.3d at 1323; Asencio, 37 F.3d at 615-16.
b. Withholding op Removal under 8 U.S.C. § 1231(b)(3) and the CAT
The government argues that we lack subject-matter jurisdiction over Mr. Alim’s claims for withholding of removal under 8 U.S.C. § 1231(b)(3) and the CAT because Mr. Alim failed to exhaust his administrative remedies. The government concedes that Mr. Alim raised both of these claims before the IJ. See Brief for Respondent at 35, 36. It further concedes that the May 20, 2003, evidentiary hearing primarily consisted of testimony from Mr. Alim in support of these two claims. See Brief for Respondent at 10-12. It argues, however, that Mr. Alim did not raise either of these claims in his brief to the BIA. According to the government, Mr. Alim’s brief only argued the merits of the asylum claim, rather than the § 1231(b)(3) and CAT claims. It recognizes that Mr. Alim re*1254ferred to the § 1231(b)(3) and CAT claims in both his procedural summary of the proceedings before the IJ and in his prayer for relief, but it considers these to be passing references to the claims, rather than actual presentations of the claims to the BIA.
We disagree with the government that Mr. Alim made only passing references to his § 1231(b)(3) and CAT claims before the BIA, and conclude that Mr. Alim exhausted his administrative remedies. His procedural summary of the case expressly stated that the issues decided by the IJ “concerned his applications for relief from withholding of removal under [INA] section 241(b)(3)(A) [§ 1231(b)(3)(A)] and protection under the Convention Against Torture.” A.R. 6. These were the only two claims that the IJ heard evidence on. The brief also recounts the IJ’s factual findings, and legal conclusions, on the merits of these two claims. The brief argues that the IJ erred in determining that Mr. Alim did not make a credible witness, a finding that could only be relevant to the merits of Mr. Alim’s § 1231(b)(3) and CAT claims. The brief then formally requests that the BIA withhold removal under the INA6 and/or the CAT, with specific references to the applicable federal statutes and regulations. Thus, we proceed to the merits of Mr. Alim’s claims for withholding of removal under § 1231(b)(3) and the CAT.
III. Merits
The BIA affirmed the IJ’s oral decision without an opinion. “When the BIA summarily affirms the IJ’s decision without an opinion, the IJ’s decision becomes the final removal order.” Sepulveda, 401 F.3d at 1230. We review the IJ’s decision “as if it were the Board’s.” Al Najjar v. Ashcroft, 257 F.3d 1262, 1284 (11th Cir.2001).
A. Legal Standards
The IJ’s factual finding that “an alien is statutorily ineligible for ... withholding is reviewed under the substantial evidence test.” Id. at 1283 (quotations omitted). That is, “we must affirm the IJ’s decision if it is supported by reasonable, substantial, and probative evidence on the record as a whole.” Sepulveda, 401 F.3d at 1230 (quotations omitted). This is a “highly deferential standard of review,” and “the IJ’s decision can be reversed only if the evidence compels a reasonable fact finder to find otherwise.” Id. (citations omitted). Thus, the evidence must compel, rather than merely support, the conclusion that the IJ erred. See Fahim, 278 F.3d at 1218.
An IJ’s adverse credibility determinations are also factual findings, and thus, are also subject to the substantial evidence test, and may not be overturned unless the record compels that result. See D-Muhumed v. U.S. Attorney Gen., 388 F.3d 814, 818 (11th Cir.2004); Forgue v. U.S. Attorney Gen., 401 F.3d 1282, 1287 (11th Cir.2005). As the trier of fact, the IJ “must determine credibility, and this court may not substitute its judgment for that of the [IJ] with respect to credibility findings.” D-Muhumed, 388 F.3d at 818. See also Forgue, 401 F.3d at 1286. Once the IJ makes an adverse credibility determination, the burden is on the alien to show that the determination “was not supported by specific, cogent reasons, or was not *1255based on substantial evidence.” Forgue, 401 F.3d at 1287.
An alien is entitled to withholding of removal under § 1231(b)(3) if he can show that his “life or freedom would be threatened in that country because of the alien’s race, religion, nationality, membership in a particular social group, or political opinion.” 8 U.S.C. § 1231(b)(3)(A). The alien “bears the burden of demonstrating that it is more likely than not he will be persecuted or tortured upon being returned to his country.” Sepulveda, 401 F.3d at 1232. Persecution is an “extreme concept requiring more than a few isolated incidents of verbal harassment or intimidation,” and “mere harassment does not amount to persecution.” Id. at 1231.
An alien is entitled to withholding of removal under the CAT if he shows that it is “more likely than not that he will be tortured upon his return to his home country.” 8 C.F.R. § 208.16(c)(2). See also Cadet v. Bulger, 377 F.3d 1173, 1180 (11th Cir.2004). “Torture” is “any act by which severe pain or suffering, whether physical or mental, is intentionally inflicted on a person ... by or at the instigation of a public official or other person acting in an official capacity.” 8 C.F.R. § 208.18(a)(1). See also D-Muhumed, 388 F.3d at 819-20. Torture “is an extreme form of cruel and inhuman treatment and does not include lesser forms of cruel, inhuman or degrading treatment or punishment that do not amount to torture.” 8 C.F.R. § 208.18(a)(2).
In his petition here, Mr. Alim bases his § 1231(b)(3) and CAT arguments on the asserted probability that he will suffer persecution and/or torture on account of his Christian faith if removed to Syria. First, he argues that the IJ erred in making an adverse credibility determination against him. Second, he contends that the IJ erred in failing to find that he suffered past persecution on account of his Christian faith while living in Syria.7 Third, he asserts that the IJ’s decision is not based on substantial evidence, and that the evidence compels the conclusion that he is entitled to withholding of removal under both § 1231(b)(3) and the CAT, because he will more likely than not be persecuted and/or tortured for being a Christian if removed to Syria.8
B. Review of the IJ’s Factual Findings
The IJ’s credibility determinations were specific, cogent, and supported by substantial evidence. The IJ doubted Mr. Alim’s credibility because he committed multiple acts of fraud: Mr. Alim deserted the Syrian air force, exited Syria illegally, entered the U.S. by fraud, falsely stated that he had not been convicted of a crime when he applied for adjustment of status, and then, after visiting Syria in 1999 for 30 days, exited Syria by fraud. The IJ also doubted whether Mr. Alim would actually be persecuted or tortured, given that he spent six months in Syria after deserting the military without being captured, and willingly returned to Syria in 1999 for 30 days to visit his mother. He further noted an inconsistency in Mr. Alim’s testimony. Mr. Alim first testified that, in 1999, he reentered Syria with a false passport, but *1256later testified that the passport was valid, but merely incorrectly spelled his name. The IJ then explained that this still constituted fraud. We find these determinations are well-supported by the record and find nothing compelling us to conclude that the IJ was wrong. Moreover, we note that these credibility determinations were but a small part of the factual basis for the IJ’s conclusions. Those conclusions were primarily based on Mr. Alim’s inability to articulate specific instances where he was persecuted or tortured, and the lack of evidence suggesting that Mr. Alim would be persecuted or tortured if removed to Syria.
The IJ found that Mr. Alim’s case was based on his cousin being killed after leaving Syria to fight a war in Lebanon on behalf of Christians. He found this evidence unconvincing because Mr. Alim had no first-hand knowledge of the circumstances of his cousin’s death, he could not produce a death certificate or other physical evidence, and the person who informed him merely showed him a picture of the cousin sitting on top of an Israeli tank. The IJ was also not convinced that Mr. Alim’s experience in the military supported his claims. His superiors knew he was a Christian, but he was never harmed for being a Christian, served for eight years, and was never arrested, detained or imprisoned while in the military for any reason. The IJ further noted that Mr. Alim was never arrested or detained while in Syria during his civilian life. According to the IJ, there was no reason to find that Mr. Alim would be persecuted and/or tortured for being Christian if removed to Syria today, because he was not persecuted and/or tortured for being a Christian when he lived in Syria. He found Mr. Alim’s testimony to be too vague and con-clusory to warrant withholding of removal under § 1231(b)(3) or the CAT.
These findings are also supported by substantial evidence. Mr. Alim could not explain how he knew why his cousin was killed, or how he knew who killed him. The family member who told him that his cousin was killed did not have first-hand knowledge of the circumstances of the murder either. Nor could Mr. Alim provide a death certificate or other corroborating evidence. Moreover, the evidence regarding Mr. Alim’s cousin equally supported the conclusion that he was killed because he was a spy for Israel, instead of on account of his Christian faith. Nor did Mr. Alim provide evidence compelling us to conclude that he would be the target of any persecution or torture in Syria because of something that happened to his cousin, in Lebanon, during a civil war. See, e.g., Roy v. Ashcroft, 389 F.3d 132,140 (5th Cir.2004) (petitioner did not show that he would more likely than not be tortured if removed, where evidence concerned “his father’s brother-in-law, and his father’s nephew,” and petitioner “was not present when his family members were arrested, harassed, or beaten”). In sum, the evidence regarding Mr. Alim’s cousin does not compel us to conclude that Mr. Alim suffered past persecution or torture, or will more likely than not suffer persecution or torture if removed to Syria.
Mr. Alim’s testimony of his civilian life as a Christian in Syria largely consisted of vague statements that Syrian Christians are discriminated against and have trouble finding work. He testified that Syrian Muslims feel they will go to heaven for killing a Christian, but he never testified as to any specific instance where he was persecuted or tortured. He testified that while living in Syria, he was a member of a Christian group that tried to convert Muslims and that this upset the Muslim authorities. He mentioned an instance where his friend was shot in 1987 or 1988 *1257for being an outspoken Christian. He never testified, however, to an instance where he was persecuted or tortured for converting Muslims to Christianity. He did say that, on account of his Christian faith, certain unidentified people went “after him,” there was a “bad point” or “black point” in his school records, and there were “negative reports” about him. But these statements were vague, and even if true, do not compel us to find that he was (or will be) persecuted or tortured.
Mr. Alim was in the Syrian military for eight years, was a Christian when he entered the military, and was known to be a Christian throughout his tenure in the military. He testified that Christians are discriminated against in the military, and that he was treated badly and denied certain rights while in the military. But he failed to provide any explanation or detail as to the nature of the discrimination or “bad” treatment. Nor did he explain what rights of his were violated, or how. Military authorities knew that he was an “outspoken” Christian while he was in the military, yet he was never arrested, detained or imprisoned for any reason. Indeed, he was promoted at least once during those eight years.
At the very most, Mr. Alim’s testimony describes instances of harassment and intimidation, but “mere harassment does not amount to persecution,” Sepulveda, 401 F.3d at 1231. See also Sanchez, 153 Fed.Appx. at 701 (petitioner did not establish past persecution or that he would more likely than not be persecuted if removed, where only evidence offered was that he received threatening telephone calls from guerrilla group, and found his car window shattered and a threatening note attached to a rock in the car). Mr. Alim was certainly not tortured. In essence, the “record lacks sufficient evidence that anyone in [Syria] has the present inclination to persecute” or torture Mr. Alim for being a Christian. Fahim, 278 F.3d at 1218.
IV. Conclusion
We have subject-matter jurisdiction over the petition because Mr. Alim has not been convicted of two crimes involving moral turpitude. The term “conviction,” as defined in § 1101(a)(48)(A), does not include a nolo contendere plea or conviction that has been vacated on the merits to remedy a violation of constitutional or statutory rights. The 1998 domestic battery plea was vacated because Mr. Alim was not informed of the immigration consequences of his plea, as required by Florida law, and therefore is not a conviction for purposes of § 1101(a)(48)(A).
Although we are not stripped of subject-matter jurisdiction over Mr. Alim’s petition, we only exercise jurisdiction over his claims for withholding of removal under § 1231(b)(3) and the CAT. We do not address the adjustment of status claim because it has been abandoned on appeal. The asylum claim cannot be judicially reviewed because it was denied as untimely, and Mr. Alim failed to exhaust his administrative remedies as to the cancellation of removal claim. As to the claims under § 1231(b)(3) and the CAT, substantial evidence supports the IJ’s findings and conclusions.
Mr. Alim’s petition is dismissed in part and DENIED IN PART.