In joint work with Timothy Chan (to appear in SODA'16), we give deterministic algorithms for APSP, Orthogonal Vectors, Batch Partial Match, etc., that essentially match the randomized running times. The talk will give algorithms researchers even more reason to know complexity theory.