Higinia Martinez-de Bojorquez (“Martinez”) petitions for review of a decision of the Board of Immigration Appeals (“BIA”). The BIA refused to consider Martinez’s appeal from the Immigration Judge’s denial of relief under former section 212(c) of the Immigration and Nationality Act (“INA”). The Immigration-Judge (“IJ”) had concluded that Martinez’s departures from the United States while an earlier appeal had been pending with the BIA resulted in a withdrawal of that appeal pursuant to 8 C.F.R. § 1003.4,
1
rendering Martinez’s original deportation order final. The IJ therefore ruled that Martinez was no longer a permanent resident eligible for section 212(c) relief. The BIA refused to consider Martinez’s contentions, finding that no proceedings after the alleged withdrawal of the earlier appeal were valid. Martinez timely petitioned for review. Because deportation proceedings against Martinez began before April 1, 1997, this case is governed by the transitional rules set forth in section 309(c) of the Illegal Immigration Reform and Immigrant Responsibility Act of 1996 (“IIRI-RA”), Pub. L. No. 104-208, div. c., 110 Stat. 3009. Pursuant to the transitional rules, we have jurisdiction under former 8 U.S.C. § 1105a, as amended by IIRIRA.
See Kalaw v. INS,
*802 I. Background, and Procedural History
Martinez, a native and citizen of Mexico, first came to the United States in 1972. She spent over a decade here as an undocumented alien but in the 1980s was able to obtain legal status, eventually becoming a lawful permanent resident in 1987. In December 1992, the former Immigration and Naturalization Service (“INS”) 3 initiated deportation proceedings against Martinez under former section 241 of the INA, 8 U.S.C. § 1251 (Supp.1995), charging that she knowingly assisted and aided her cousin to enter the United States illegally. Martinez had a hearing before the IJ in September 1993. After hearing testimony and receiving other evidence, the IJ found Martinez deportable as charged. Through her counsel, Martinez indicated that she reserved the right to appeal the IJ’s decision. The IJ informed Martinez that she had ten days during which to file her notice of appeal, but made no mention of the fact that the appeal would be deemed withdrawn pursuant to INS regulations if she were to depart the country — even temporarily — while the appeal was pending. After Martinez filed the proper forms with the BIA, she received a number of notifications informing her that her appeal was pending and setting forth a briefing schedule, but she was again not informed that her departure from the United States would constitute a withdrawal of the appeal.
The BIA did not issue a decision in Martinez’s case until four-and-a-half years later, in March 1998. While Martinez’s appeal was pending, we issued our decision in
Ortega de Robles v. INS,
The IJ held a hearing on Martinez’s section 212(c) application in May 1998. Martinez presented the relevant documentation and testified on her own behalf, particularly stressing her family ties in the United States, including the fact that her husband was a legal permanent resident and that her children and grandchildren were all United States citizens. Martinez also testified that, other than the smuggling charge for which she was found de-portable, she had not had any problems with law enforcement or immigration officials. 4 Unfortunately for Martinez, however, she also testified that she had been making brief visits to her doctor and her dentist just across the border in Mexico over the past two to three years. Martinez explained that she went to Mexico for these visits because her employer-provided health insurance covered a greater percentage of medical treatment in Mexico than it did in the United States.
After Martinez’s testimony, counsel for the INS argued that Martinez was no *803 longer eligible for section 212(c) relief because her departures-to Mexico while her appeal was pending at the BIA constituted a withdrawal of her appeal under 8 C.F.R. § 1003.4. 5 The IJ noted that this seemed a “very harsh rule,” but he asked counsel to brief the issue and continued the hearing to a later date. After the parties had made their submissions, the, IJ found that Martinez’s departures had indeed constituted a waiver of her appeal with the BIA, which meant that Martinez’s original order of deportation had become effective and that Martinez was therefore not .eligible for section 212(c) relief because she was no longer a legal permanent resident. The IJ added:
I will just tell you frankly that I have a real intellectual problem with that view of the law. I don’t think that a person such as yourself who departed purely for dental work and who was gone no longer than required to accomplish the purpose of your trip, who strayed no farther from the border than a few miles at the most and who was each time lawfully admitted using your green card when you returned to the country that those departures should be such — have such a dire effect. But I’m not empowered under the law to consider the reasonable [sic] or arbitrariness of the regulation.
AR 182-83. The IJ also noted that, but for the application of § 1003.4, he would have been inclined to grant section 212(c) relief as a matter of discretion.
Martinez appealed the IJ’s decision to the BIA. The BIA refused to consider her claims, in essence upholding the finding that Martinez’s brief departures from the United States had withdrawn the earlier appeal and had rendered the initial deportation order final. Martinez timely petitioned for review.
II. Discussion
Martinez raises a number of challenges to the application of 8 C.F.R. § 1003.4 to her case. Several of her arguments are foreclosed by our recent decision in
Aguilera-Ruiz v. Ashcroft,
It is well-established that aliens facing deportation are entitled to due process under the Fifth Amendment to the United States Constitution.
See Landon v. Plasencia,
We find the situation presented in this case analogous to that addressed by
Padillar-Agustin
and its progeny. Martinez has been a lawful permanent resident of this country since 1987. At her deportation hearing, she was informed of her right to appeal, but she was not told that, by virtue of § 1003.4, her appeal would be deemed waived if she left the country for even a few minutes. Martinez was allowed to keep her “green card,’’ which identified her as a legal permanent resident eligible to freely travel to and from this country. When she filed her appeal with the BIA, Martinez received a number of notifications regarding the process, but at no time was she told that her appeal would be forfeit if she went' to Mexico even briefly. The BIA then took four-and-a-half years to decide her appeal, a substantial amount of time during which it is not unreasonable for a legal permanent resident to have to travel outside the country. Finally, as far we can discern from the record, Martinez’s absences were all very short — not longer than two days — and involved trips only a few miles from the border. We hold that the “concatenation” of circumstances in this case, but particularly the undisputed fact that Martinez was never warned about the severe consequences that even a brief departure from the United States would have on her case, constitute a violation of due process.
See Walters v. Reno,
*805
Our conclusion is the same when we analyze Martinez’s due process claim under the test set out by the Supreme Court in
Mathews v. Eldridge,
First, the private interest that will be affected by the official action; second, the risk of an erroneous deprivation of such interest through the procedures used, and the probable value, if any, of additional or substitute procedural safeguards; and finally, the Government’s interest, including the function involved and the fiscal and administrative burdens that the additional or substitute procedural requirement would entail.
Id.
at 335,
Finally, the additional burden imposed on the government in having to provide a warning regarding the effect of 8 C.F.R. § 1003.4 is not substantial. While we do not decide what type of warning would be appropriate under the circumstances because it is clear from the recórd that no notice was given to Martinez, we are confident that providing notice to a person such as Martinez would result in minimal cost to the government. Providing such notice, however, would go a long way in remedying the inequities that the application of 8 C.F.R. § 1003.4 can cause.
In sum, all of the Mathews factors weigh in favor of a finding that due process requires that some form of notice be given directly to individuals in Martinez’s circumstances before their appeals are deemed waived pursuant to 8 C.F.R. § 1003.4 when they briefly leave the United States. 8
*806
When an alien raises a due process challenge to his or her deportation proceedings, we generally require a showing of prejudice from the constitutional violation.
See Ortiz v. INS,
III. Conclusion
We hold that, under the circumstances of this case, the application of 8 C.F.R. § 1003.4 without any notice whatsoever constituted a violation of due process. We therefore find that Martinez’s original appeal to the BIA was not withdrawn pursuant to the regulation and that the IJ erred in finding that Martinez was not eligible for section 212(c) relief because she was no longer a legal permanent resident. We remand to the BIA for further proceedings consistent with this opinion.
PETITION GRANTED; REMANDED.
Notes
. Former 8 C.F.R. § 3.4 was recodified at 8 C.F.R. § 1003.4 on March 5, 2003, pursuant to the reorganization of regulations resulting from the creation of the Department of Homeland Security. See 68 Fed. Reg. 10,349 (March 5, 2003). Throughout this opinion we refer to the regulation by its current citation, § 1003.4, even though the earlier proceedings referred to the earlier version. We note, however, that the relevant language of the regulation remains unchanged.
. The government contends that we do not have jurisdiction to review this case because Martinez failed to exhaust her administrative remedies.
See
8 U.S.C. § 1105a(c) (Supp. 1995). That jurisdictional argument, however, is intertwined with the merits of this case because it depends on a finding that Martinez's departures from the United States resulted in a waiver of her BIA appeal. If Martinez did not waive her appeal, then she did exhaust her remedies and we have jurisdiction over this case. Of course, we have
*802
jurisdiction to determine our jurisdiction.
See United States
v.
Ruiz,
. On March 1, 2003, the INS ceased to exist and its functions were transferred to the newly created Department of Homeland Security. See
Aguilera-Ruiz v. Ashcroft,
. Martinez did appear to concede that she had not been truthful at her original immigration hearing regarding the circumstances of the smuggling charge.
. 8 C.F.R. § 1003.4 provides, in relevant part: Departure from the United States of a person who is the subject of deportation proceedings subsequent to the taking of an appeal, but prior to a decision thereon, shall constitute a .withdrawal of the appeal, and the initial decision in the case shall be final to the same extent as though no appeal had been taken.
. We review de novo claims of violations of due process in deportation proceedings.
See Padilla v. Ashcroft,
. Indeed, the due process violation in this case is even clearer than it was in the
Padilla-Agustin
line of cases. In those cases, the BIA had at least made an attempt to inform aliens filing appeals of the possibility that an appeal would be summarily dismissed.
See, e.g., Vargas-Garcia v. INS,
. In response to Martinez's due process claim, the government points to cases indicating that the enactment of administrative regulations provides sufficient notice to the parties involved for due process purposes. However, ''[a]s the
Mathews
balancing test makes’ clear, whether a particular procedure is sufficient to satisfy due process depends on the circumstances.”
Walters,
. In Walters,
