There was a recent post on LWN suggesting that three specific Nokia patents may cover Theora. A deeper analysis indicates that’s just not true.
Two of the patents 6,950,469 and 7,263,125, are post-VP3 and therefore not relevant because the patent filing dates are after the invention and introduction of VP3 (the basis for Theora.) Thus, Theora predates these patents and could not infringe.
The other patent, 6,504,873, requires the affirmative step of defining a “linear equation” between two reference pixels. Theora does not use such an equation; thus it doesn’t satisfy the limitations of the claims and does not infringe.