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.
Нејзината работа во теоријата на комплексност ја вклучува класификацијата на проблемите со приближување, покажувајќи дека некои проблеми во НП остануваат тешки, дури и кога е потребно само приближно решение, и пионерски методи за делегирање на пресметки на недоверливи сервери.