Getting them out will probably require cutting, either with a thin or ultra thin wheel in an angle grinder and/or a metal cut-off wheel in a Dremel. Either of those tools potentially can get the job done, and which one to use depends on what the access situation is. But if you can get both tools into the work, then the angle grinder should always be faster and better for this job.
It would probably be faster and easier to cut the bolt head instead of through the nut, however access always rules for these jobs, and you may be forced to make the less desirable choice on that. Another possible approach might be to grind the bolt head, instead of slicing it off. If grinding seems like a better idea on one or both of them, then use a standard thick grinding wheel instead of the thin slicing wheel.
And there is one other last resort tool to consider, if it's physically impossible to use either of the other ones. A fresh, high quality metal blade (Diablo, ...) in a reciprocating saw can also get this job done. However, those brute force saws can do lots of damage in a heartbeat and can be much more difficult to control, so extreme care is a must with that one. I have successfully used a recip saw/Diablo myself on frozen LCA bolts, and can confirm it's incredibly fast and highly effective. But that applies to anything else that the blade touches as well, and it would only take a second for one of those saws to possibly create a much bigger problem than you already have.
Regardless of which tool you use, block off the O2 sensor, its wiring with solid plastic or metal, along with anything else in the work area that might get damaged if the cutting tool slips. Full wraparound goggles or face shield is mandatory (for me anyway). Good luck with it!