Ryan Williams (computer scientist)

from Wikipedia, the free encyclopedia
Ryan Williams

Richard Ryan Williams (* 1979 ) is an American theoretical computer scientist.

Williams studied at Cornell University and received his PhD in 2007 from Carnegie Mellon University under Manuel Blum (Algorithms and Resource Requirements for Fundamental Problems). From 2010 to 2012 he was in the theory group of the IBM Almaden Research Center and from 2011 Assistant Professor at Stanford University . He has been an Associate Professor at the Massachusetts Institute of Technology since 2017 .

He deals with complexity theory ( e.g. of K-anonymity ) and is known for proving that the complexity class NEXPTIME is not included in the circuit complexity class AC0 . He achieved a breakthrough after a long search for such barriers for AC0.

In 2014 he was invited speaker at the International Congress of Mathematicians in Seoul (Algorithms for circuits and circuits for algorithms: connecting the tractable and intractable).

Fonts (selection)

  • with Adam Meyerson: On the complexity of optimal k-anonymity, Proceedings of the Twenty-third ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems (PODS '04), New York, 2004, ACM, pp. 223–228
  • Better Time-Space Lower Bounds for SAT and Related Problems, IEEE Conference on Computational Complexity (CCC), 2005, pp. 40-49
  • A New Algorithm for Optimal 2-Constraint Satisfaction and Its Implications, Theoretical Computer Science, Volume 348, 2005, pp. 357-3365.
  • Time-Space Lower Bounds for Counting NP Solutions Modulo Integers, Computational Complexity, Volume 17, 2008, pp. 179-219
  • Non-Uniform ACC Circuit Lower Bounds, IEEE Conference on Computational Complexity (CCC), 2011, pp. 115-125, pdf

Web links

Individual evidence

  1. ↑ Ryan Williams in the Mathematics Genealogy Project (English)Template: MathGenealogyProject / Maintenance / id used
  2. ^ Williams, Non-Uniform ACC Circuit Lower Bounds, Preprint 2010, IEEE Conference on Computational Complexity (CCC), 2011, pp. 115-125
  3. ^ A Circuit Lower Bound Breakthrough , Luca Trevisan's blog , November 8, 2010
personal data
SURNAME Williams, Ryan
ALTERNATIVE NAMES Williams, Richard Ryan (full name)
BRIEF DESCRIPTION American theoretical computer scientist
DATE OF BIRTH 1979