Ryan Williams

Ryan Williams studies what can and cannot be efficiently computed, independently of any particular computer. Some questions which haunt him are: When can interesting algorithms be used to prove that other kinds of algorithms do not exist? (When can we use algorithms to prove lower bounds?) Is exhaustive search really the best possible algorithm for general searching, or are there more efficient methods? (Is the Strong Exponential Time Hypothesis true?) Does every function implementable with low memory also have a fast implementation? (Does P = PSPACE?) Could computers themselves help us make progress on answering these questions?