Her work in complexity theory includes the classification of approximation problems, showing that some problems in NP remain hard even when only an approximate solution is needed, and pioneering methods for delegating computations to untrusted servers.
Hennes arbete i komplexitetsteori omfattar klassificering av tillnärmnings problem, som visar att vissa problem i NP förblir hårda även när endast en ungefärlig lösning behövs, och banbrytande metoder för att delegera beräkningar för betrodda servrar .