I live in Alaska and have lived in many frigid parts of the US including northern Minnesota. Each of us has has our own tolerance limits so there will be some variance there. I've found that anything below -20F is getting pretty tough. An easy run at -20 to -30 is okay, but I tend to keep these short (30 - 60 min), but have done 2+ hours through -24 (not fun).
Likewise, re: intervals-speed sessions-races, somewhere around 15-20 below you're running into some limits. I've ski-raced at -20 and it can be pretty rough on you.