He introduced the method of probabilistic restriction for proving super-polynomial lower bounds on circuit complexity in a paper joint with Merrick Furst and James B.

[8] Their result was later improved to be an exponential lower bound by Andrew Yao and Johan Håstad.

[12] With fellow graduate student David Lichtenstein, Sipser proved that Go is PSPACE hard.

[13] In quantum computation theory, he introduced the adiabatic algorithm jointly with Edward Farhi, Jeffrey Goldstone, and Samuel Gutmann.

In 1975, he wagered an ounce of gold with Leonard Adleman that the problem would be solved with a proof that P ≠ NP by the end of the 20th century.