Ryan Williams

An American theoretical computer scientist at MIT known for his work on circuit lower bounds and fine-grained complexity.

1 articleLast mentioned

Ryan Williams is an American theoretical computer scientist and a professor in the Department of Electrical Engineering and Computer Science at MIT. He received his PhD from Carnegie Mellon University under Manuel Blum and was previously a professor at Stanford University.

In 2010 he proved that the nondeterministic exponential-time class NEXP is not contained in the circuit class ACC0, a result credited with breaking a long stalemate in circuit lower bounds. He is also known for his work connecting algorithm design to lower-bound proofs, for fine-grained complexity, and for results on the relationship between time and space in computation.

This entry is based on AIPOST articles and widely known facts. If something is wrong, please send us a correction request.

Articles covering this entry

  • ETH Disproof by OpenAI's AI: What Changes for P vs NP and CryptographyAI News ·

    …tead, it arranged for Impagliazzo and Paturi of UC San Diego, along with Ryan Williams of MIT, who had earlier proven refutations of stronger versions of ETH, t…

    Read article

Found a mistake or missing an entry?

Wiki entries are based on AIPOST articles and widely known facts. If an entry is wrong, send us a correction request and we will check and fix it. Names from new articles are added to the wiki after the article is published.