I'd second this, if only because I have nothing further than an undergrad CS degree and I can read computational complexity papers just fine. You don't need muc

I'd second this, if only because I have nothing further than an undergrad CS degree and I can read computational complexity papers just fine. You don't need much extra education to understand a paper, you might to understand some of the implications of it