Software reliability via run-time result-checking.
Exact analysis of Dodgson elections: Lewis Carroll's 1876 voting system is complete for parallel access to NP.
Compositional refinement of interactive systems.
Contention in shared memory algorithms.