In his best known work, joint with Steven Rudich, he introduced the notion of natural proofs, a class of strategies used to prove fundamental lower bounds in computational complexity.
Το πιο γνωστό έργο του, από κοινού με τον Στίβεν Ρούντιτς, εισήγαγαν την έννοια των φυσικών αποδείξεων, μια τάξη στρατηγικών που χρησιμοποιούνται για να αποδείξουν τα θεμελιώδη κάτω όρια στην υπολογιστική πολυπλοκότητα.