A jury convicted Rasim Causevic of one count of making a materially false statement, see 18 U.S.C. § 1001(a)(2), and one count of making a materially false statement in an immigration matter, see 18 U.S.C.A. § 1546(a). Mr. Causevic appealed, contending that he was denied his right to be confronted with the witnesses against him, see U.S. Const, amend. VI, and challenging the sufficiency of the evidence. Because we conclude that Mr. Causevic’s confrontation rights were violated, we reverse his convictions and remand for further proceedings.
I.
Since Mr. Causevic challenges the sufficiency of the evidence, we state the facts favorably to the guilty verdict. Mr. Causevic and his sister, Fadila Okanovic, entered the United States as Bosnian refugees from the former Yugoslavia during the civil war in that country. After a refugee has been in this country for a year, he or she may apply for permanent resident status, which, in turn, may eventually lead to citizenship. About ten years after Mr. Causevic arrived, he filed an application for permanent-resident status (also known as a Form 1-485) but did not complete the process. He filed another Form 1-485 three years later. The Citizen and Immigration Service (CIS) determines whether to grant applications for permanent residency, and, when conducting a routine background check, the CIS learned that Mr. Causevic might be sought in his home country on a murder charge. The CIS notified Immigration and Customs Enforcement (ICE), which obtained a report from the International Police (an Interpol want) that a “Rasim Causevic” was wanted in Bosnia-Herzegovina for murder, that the crime had occurred during the civil war in the former Yugoslavia, and that it involved the killing of a soldier in “Rasim Causevic’s” unit.
CIS Officers John Stewart and Ron Mace then interviewed Mr. Causevic to determine whether he was the person named in the Interpol want. They conducted the interview in English, and Mr. Causevic asked his sister, who accompa*1001nied him, to assist him twice: once to spell the name of his hometown and another time to explain his right to counsel. The officers began by questioning Mr. Causevic about his answer of “no” to a question on his Form 1-485 asking whether he had “ever ... been arrested, cited, charged, indicted, fined or imprisoned for breaking or violating any law” other than traffic laws. He confirmed that he had answered “no” to that question on the application and stated that his answer was still “no.” Officer Stewart then asked Mr. Causevic whether he had ever killed anyone while he was in the army or militia in the former Yugoslavia. He denied having done so, though he said that he had shot long distances while he was a soldier and did not always know whether he had hit anyone. Finally, the officer asked him whether he had killed anyone at any time before entering the United States, and again his answer was “no.” After completing the interview, Officer Stewart prepared a written statement that included Mr. Causevic’s answers during the interview and Officer Stewart read the document to him. Mr. Causevic signed it under oath and in the presence of Officer Stewart and Ms. Okanovic.
Immediately afterward, two agents from ICE, which enforces immigration and customs laws, interviewed Mr. Causevic without his sister present. Mr. Causevic was again asked whether he had ever been arrested and whether he had killed anyone while in the armed services or before coming to the United States, and he responded in the negative once more. When the agents showed Mr. Causevic the Interpol want, he confirmed that he was the person named in the document but denied committing the crime. The agents then asked Ms. Okanovic to come into the interview room, telling her that they thought her brother might be more “forthcoming” if she were present; she came in and told her brother to tell the truth, and, as she put it, he “told them everything.” When asked whether he had committed any crimes, Mr. Causevic said “yes,” that in 1995, “I shot in body six bullets,” and that the victim “died after about two minutes.” Mr. Causevic asserted that did not know what else to do because the man was coming toward him with a knife. He added that he was taken from the scene, “put ... downtown for three days,” and then transferred to a unit with about three hundred other people until the jail was unlocked and everyone left.
Mr. Causevic was charged with six counts, all of which related to making false statements. The jury acquitted him on the first four counts, which were based on allegations that he falsely stated in his original and second Form 1-485 that “he had never been arrested.” But the jury returned a guilty verdict on Counts V and VI. Each of these two counts alleged that on the day he was interviewed, Mr. Causevic falsely stated that he had never been arrested, had never killed anyone while in the armed forces in the former Yugoslavia, and had never killed anyone before coming to the United States. The counts differed only in that Count V charged him with violating § 1001(a)(2), a general prohibition on false statements in federal matters, and Count VI charged him with violating § 1546(a), which pertains specifically to immigration proceedings.
During trial, Mr. Causevic objected to the admission of a Bosnian judgment convicting him of murder following a trial in absentia; the judgment (translated into English) recited that Mr. Causevic had committed murder by firing six bullets at a man at close range while they were serving in what it called an independent army of West Bosnia. The district court concluded that the judgment was not testimonial and thus its admission would not vio*1002late Mr. Causevie’s right to confront the witnesses against him.
II.
Mr. Causevic maintains that the district court erred in admitting the Bosnian judgment of conviction because its admission violated the Confrontation Clause, which states, “In all criminal prosecutions, the accused shall enjoy the right ... to be confronted with the witnesses against him.” U.S. Const, amend. VI. We review the district court’s rejection of this contention de novo. United States v. Holmes, 620 F.3d 836, 840 (8th Cir.2010).
Mr. Causevic challenges the government’s use of the judgment as substantive proof of an element of the charged crimes. In particular, he contends that his confrontation rights were violated when the government introduced the Bosnian murder conviction as proof that he killed someone, which he had denied. The government acknowledges that it relied on the conviction to show, contrary to Mr. Causevie’s CIS interview and related written statement, that he had fatally shot a man before coming to the United States.
Under the Sixth Amendment, a defendant has the right to confront those who “bear testimony” against him. Crawford v. Washington, 541 U.S. 36, 51, 124 S.Ct. 1354, 158 L.Ed.2d 177 (2004). Therefore a witness may not give “testimony against a defendant” without appearing at trial, unless that witness is unavailable and the defendant had previously had an opportunity for cross-examination. Melendez-Diaz v. Massachusetts, — U.S. —, 129 S.Ct. 2527, 2531, 174 L.Ed.2d 314 (2009). Although the Court in Crawford declined to define the term “testimonial,” it gave examples of documents that usually fall within the “core class of testimonial statements” covered by the Confrontation Clause, including “affidavits, custodial examinations, [and] prior testimony that the defendant was unable to cross-examine.” Id. at 51-52, 124 S.Ct. 1354 (internal quotation marks and citations omitted); see Melendez-Diaz, 129 S.Ct. at 2531.
At first blush, it seems that the Bosnian judgment, as a public record, differs significantly from Crawford’s examples of testimonial statements, as well as the analysts’ reports at issue in Melendez-Diaz, which the Court emphasized were created specifically for use at the defendant’s trial for cocaine distribution, and identical to testimony that the analysts would have given had the government called them as witnesses. And the Ninth Circuit, in a case that the government relies on, has stated that “it is undisputed that public records, such as judgments, are not themselves testimonial [and] do not fall within the prohibition established ... in Crawford.” United States v. Weiland, 420 F.3d 1062, 1076-77 (9th Cir.2005), cert. denied, 547 U.S. 1114, 126 S.Ct. 1911, 164 L.Ed.2d 667 (2006). In that case, the defendant had appealed his conviction for being a felon in possession of a firearm, arguing that he had a Sixth Amendment right to cross-examine those attesting to the authenticity of his prior convictions. Id. at 1066, 1076. We agree with the Weiland court that criminal judgments may be admitted to show that a defendant has a prior conviction without violating the Confrontation Clause. See id. at 1078-79. But the defendant here challenges the government’s use of a conviction for a significantly different purpose, namely, to show that he in fact committed the crime of which he was convicted. This is a difference that makes for a legal distinction.
The Supreme Court long ago addressed this distinction in Kirby v. United States, 174 U.S. 47, 19 S.Ct. 574, 43 L.Ed. 890 (1899), and it has cited Kirby favorably in two post-Crawford cases: Melendez-Diaz, 129 S.Ct. at 2534, and Davis v. Washing*1003ton, 547 U.S. 813, 825, 126 S.Ct. 2266, 165 L.Ed.2d 224 (2006). In Kirby, the defendant was charged with receiving property that had been stolen from the United States, and his indictment alleged, inter alia, that three named men had stolen stamps from a post office and that the defendant had received the stamps with the intent to convert them to his gain. Id. at 48-49, 19 S.Ct. 574. A relevant statute provided that proof that the alleged thief (the “principal felon”) had been convicted was “conclusive evidence” that the property had been stolen, and the defendant challenged that statute’s constitutionality. Id. at 48-50, 19 S.Ct. 574. Over the defendant’s objection, the government introduced court records showing that two of the men named in the defendant’s indictment pleaded guilty to stealing stamps, the other was convicted by a jury, and all three were sentenced to prison. Id. at 49, 19 S.Ct. 574.
The Supreme Court held in Kirby that it was “fundamental error” for the trial court to admit evidence of the convictions. Id. at 60, 19 S.Ct. 574. In explaining its holding, the Court observed that when a “conviction” is an element of a crime, a record of conviction is admissible to show the fact of conviction because “a fact of that nature could only be established by a record.” But such a record should not be used to prove that the property the defendant received “was actually stolen from the United States.” Id. at 54, 19 S.Ct. 574. The Court held that admitting the convictions in this circumstance violated the defendant’s Sixth Amendment right to confront the witnesses against him, “[o]ne of the fundamental guaranties of life and liberty”; the defendant had had no opportunity or right to confront the witnesses who testified against the man convicted by a jury or the two men who pleaded guilty to the crime. Id. at 55,19 S.Ct. 574.
We' believe that the Supreme Court’s recent decisions make plain that Kirby’s holding remains vital because these cases have identified the judgments of conviction in Kirby as testimonial. In Davis, the Supreme Court cited Kirby to support an assertion that its “own Confrontation Clause jurisprudence was carefully applied only in the testimonial context.” Davis, 547 U.S. at 825, 126 S.Ct. 2266 (emphasis added). The Court relied on Kirby again in Melendez-Diaz, 129 S.Ct. at 2534: There the state argued, inter alia, that the drug-testing reports were not subject to the Confrontation Clause because they were not evidence “against” the defendant but merely evidence of a fact that, in itself, was not incriminating. In response, the Court remarked that one piece of evidence seldom sufficed to support a conviction. It added that it was not surprised that the state failed to come up with a case to support its position, “since such a holding would be contrary to longstanding case law,” and it used Kirby to illustrate its point: “In Kirby ... the Court considered [the defendant’s] conviction for receiving stolen property, the evidence for which consisted, in part, of the records of conviction of three individuals who were found guilty of stealing the relevant property. Though this evidence proved only that the property was stolen, and not that [the defendant] received it, the Court nevertheless ruled that admission of the records violated [the defendant’s] rights under the Confrontation Clause.” It is apparent to us that the Court in both Davis and Melendez-Diaz endorsed the continuing validity of the Kirby decision, and made plain that the judgments of conviction in that case were testimonial, as the Court has used that term to determine when a defendant has a right to be confronted by adverse witnesses. Thus we conclude that “testimonial evidence” encompasses not only “prior *1004testimony that the defendant was unable to cross-examine,” Crawford, 541 U.S. at 51-52, 124 S.Ct. 1354, but also judgments of conviction based on trials during which the defendant was unable to cross-examine, when those convictions are used as proof of facts underlying the crime charged.
Following the same reasoning, we conclude that the Bosnian judgment at issue here was testimonial because the government used it as evidence that Mr. Causevic had lied when he said that he had not killed anyone. Mr. Causevic obviously had no opportunity at his false-statements trial to cross-examine the witnesses against him in his murder trial. The admission of the testimonial evidence therefore violated the Confrontation Clause unless the witnesses were “unavailable to testify, and the defendant had had a prior opportunity for cross-examination.” Crawford, 541 U.S. at 53-54, 124 S.Ct. 1354. As the proponent of the evidence, the government had the burden to show its admissibility. See United States v. Turning Bear, 357 F.3d 730, 738 (8th Cir.2004); United States v. Arnold, 486 F.3d 177, 213-14 (6th Cir.2007). But the government argued only that the judgment was non-testimonial and made no effort to show that the witnesses were unavailable; this failure alone precludes admissibility. The government also made no showing that Mr. Causevic had a prior opportunity for cross-examination. We know that he was absent during his murder trial, and the government provided no basis for concluding that he would have had a right of cross-examination even if he had been there: It did not explain how the Bosnian justice system operated at the time of the murder trial or, more specifically, show that defendants had a right of cross-examination in that system. Although the record reflects that Mr. Causevic had an attorney in the murder case, we cannot tell from the record if the lawyer cross-examined witnesses, or even had the right to do so. In the circumstances, the judgment based on the murder conviction was admitted in violation of the Confrontation Clause.
The government does not maintain on appeal that admission of the Bosnian judgment was harmless, so we are not obliged to reach the issue. See United States v. Williams, 627 F.3d 324, 329 (8th Cir.2010); United States v. Cacioppo, 460 F.3d 1012, 1025-26 (8th Cir.2006). Though we have discretion to review sua sponte for harmless error, we see no basis for doing so here. Before deciding to conduct such a review, we consider, among other things, whether the harmlessness is so certain that a reversal would merely “result in protracted, costly and futile proceedings in district court.” Lufkins v. Leapley, 965 F.2d 1477, 1481 (8th Cir.1992). (And even when we conduct sua sponte review, we err on the side of the defendant. United States v. Kenyon, 397 F.3d 1071, 1081 (8th Cir.2005) (citing Lufkins, 965 F.2d at 1481)). Here the harmlessness is far from certain: The government offered the tainted murder conviction, potentially powerful evidence in the minds of jurors, as proof that the defendant killed a man, an element of the government’s case; and the Bosnian court’s detailed findings about the crime that were included in the judgment could only have enhanced the power of that evidence. The government had no witnesses to the killing. Other trial evidence showed that Mr. Causevic had some difficulty with English (he also had an interpreter at trial), and that the CIS officers and ICE agents did not record their interviews with him. So we cannot say that the harmlessness is so manifest that a new trial would be futile. We see no occasion for full-blown harmless-error review.
We thus conclude that Mr. Causevic is entitled to a new trial because he was *1005denied his constitutional right to be confronted by the witnesses against him.
III.
We must also address Mr. Causevic’s challenge to the sufficiency of the evidence because he is entitled to an acquittal if the government failed to make out its case. Burks v. United States, 437 U.S. 1, 18, 98 S.Ct. 2141, 57 L.Ed.2d 1 (1978). In determining whether the district court should have granted Mr. Causevic’s motion for an acquittal, we consider all of the evidence presented in the district court, even though we have decided that some of it was erroneously admitted. “An error in the admission of evidence may warrant a new trial without the disputed evidence, but if the evidence admitted at the first trial was sufficient to support a conviction, the defendant is not entitled to a judgment of acquittal.” United States v. Eagle, 515 F.3d 794, 806 (8th Cir.2008). We review the sufficiency issue de novo, viewing the evidence in the light most favorable to the guilty verdict, resolving conflicts in favor of the government, and accepting all reasonable inferences that support the jury’s verdict. United States v. Washington, 318 F.3d 845, 852 (8th Cir.2003). We may not reverse unless no reasonable jury could have found Mr. Causevic guilty beyond a reasonable doubt. Id.
Mr. Causevic was convicted of violating § 1001(a)(2) and § 1546(a). Each count alleged that he knowingly made material false statements to the CIS when he said that “he had never been arrested ..., that he had never killed anyone during his service in the armed forces or militia in the former Yugoslavia, that he had never killed anyone before coming to the United States.” Mr. Causevic contends that the government failed to offer evidence to support a finding beyond a reasonable doubt that any one of the statements was false, was material, or was knowingly made; these findings are necessary to both convictions. See 18 U.S.C. § 1001(a)(2), § 1546(a). But if there is evidence to support a finding beyond a reasonable doubt that any of the violations in a count in the indictment occurred, we must uphold the conviction on that count. See United States v. Van Nguyen, 602 F.3d 886, 900 (8th Cir.2010), cert. denied, — U.S. —, 131 S.Ct. 342, 352, 178 L.Ed.2d 222, 229 (2010).
We believe that the evidence admitted at trial and that we have already recited, viewed favorably to the verdict, was more than sufficient to support a finding beyond a reasonable doubt that Mr. Causevic falsely denied that he had killed anyone before coming to the United States. Mr. Causevic contends, however, that the government failed to establish the element of materiality because it did not show that the statement affected the CIS’s decision to deny his permanent-residency application. But under the relevant statutes, a false statement may be material even if the agency did not actually rely on it to make its decision; the statement need only have a “natural tendency to influence,” or be “capable of influencing, the decision.” United States v. Henderson, 416 F.3d 686, 692 (8th Cir.2005), cert. denied, 546 U.S. 1175, 126 S.Ct. 1343, 164 L.Ed.2d 57 (2006); see also Kungys v. United States, 485 U.S. 759, 770, 108 S.Ct. 1537, 99 L.Ed.2d 839 (1988). The CIS may grant permanent-resident status only to aliens who are “admissible to the United States for permanent residence,” 8 U.S.C.A. § 1255(a)(2), and an alien who “admits acts which constitute the essential elements of ... a crime involving moral turpitude” see 8 U.S.C. § 1182(a)(2)(A)(i)(I), are inadmissible. By denying having killed anyone, Mr. Causevic denied an element of a crime involving *1006moral turpitude, ie., murder, see Franklin v. INS, 72 F.3d 571 (8th Cir.1995), and his statement thus supported a finding of eligibility. We therefore believe that his denial was “capable of influencing” the CIS’s decision.
Mr. Causevie argues that his case is different because the evidence shows that the statement occurred after CIS had made its decision. If he is right, we would face the question of whether a false statement can have a “tendency to influence” or be “capable of influencing” an already fully-formed decision, see Henderson, 416 F.3d at 692, but we need not answer that question here because we conclude that the evidence supports a finding beyond a reasonable doubt that Mr. Causevic’s statement preceded the CIS’s decision. Officer Stewart testified that when he and another CIS officer interviewed Mr. Causevic, they had not decided whether to grant his application. The officer added that even after that interview, during which Mr. Causevie denied having killed anyone, they still had not made a decision; they did not have sufficient evidence that the defendant was the person in the Interpol want, a document that CIS agents were not permitted to see. The ICE agents, who had access to the Interpol want, later showed it to Mr. Causevie before he admitted having killed someone.
In support of his argument, Mr. Causevic asserts that Officer Stewart’s testimony shows that he knew — before Mr. Causevic’s statement that he had not killed anyone — that his Form 1-485 application would be automatically denied because a subsequent application will not be granted when, as here, an earlier Form 1-485 application was deemed “abandoned.” To the contrary, however, Officer Stewart repeatedly resisted counsel’s attempts to get him to admit that the abandoned application prevented Mr. Causevie from prevailing, and we are aware of no evidence to support his assertion that it had that effect.
Nor does the record support Mr. Causevic’s contention that ICE Agent Shane Nestor testified that before the CIS agents had interviewed Mr. Causevie, one of them told him “that Mr. Causevic’s application was going to be denied for providing false information.” Agent Nestor acknowledged that he had said, in a form sent to the United States Attorney to initiate a case against Mr. Causevie, that CIS had stated that it was going to deny his application. But Agent Nestor testified that the CIS agent made this statement only after both the CIS interview and the ICE interview were concluded. Because the evidence supported a finding beyond a reasonable doubt that the CIS did not decide to deny Mr. Causevic’s application until after his false statement, he cannot prevail on a sufficiency-of-the-evidence argument that is bottomed on a contrary finding of fact.
Mr. Causevie maintains, finally, that he could not have knowingly made the false statements because he was not sufficiently proficient in English to understand the CIS officers’ questions. Mr. Causevie correctly notes that some witnesses agreed that he spoke “broken” English, but we do not think that that is enough to require a jury to conclude that he could not understand the questions that he answered, notably without consulting his sister, who was available to assist him. And one of the witnesses who agreed that his English was “broken” testified that he had spoken several times with Mr. Causevie and had had no difficulty understanding him. Though there is evidence that Mr. Causevic had some difficulty with the language, that evidence did not compel a reasonable juror to find that he did not understand the questions nor does it support the conclusion that no reasonable juror could find beyond a reasonable doubt that Mr. Cau*1007sevic “knowingly” answered the relevant question. We therefore deny Mr. Causevic’s challenge to the sufficiency of the evidence.
IV.
Because we conclude that the admission of the Bosnian judgment violated Mr. Causevie’s Sixth Amendment right to be confronted by the witnesses against him, we reverse his convictions and remand for further proceedings.