Ryan Williams (computer scientist)

For other people named Ryan Williams, see Ryan Williams (disambiguation).
Richard Ryan Williams

Ryan Williams (November 2010)
Born 1979 (age 36–37)
Residence USA
Nationality American
Fields Computational complexity theory, Algorithms
Institutions Carnegie Mellon University
IBM Almaden Research Center
Stanford University
Alma mater Cornell University
Carnegie Mellon University
Doctoral advisor Manuel Blum

Richard Ryan Williams, known as Ryan Williams (born 1979), is an American computer scientist working in computational complexity theory.

Education

Williams received his Ph.D in computer science in 2007 from Carnegie Mellon University under the supervision of Manuel Blum.[1] From 2010 to 2012, he was a member of the Theory Group of IBM Almaden Research Center. Since Fall 2011, he is a professor at Stanford University.[2]

Research

Williams has been a member of the programme committee for the Symposium on Theory of Computing in 2011 and various other conferences. He won the Ron V. Book best student paper award at the IEEE Conference on Computational Complexity in 2005 and 2007,[3] and at the best student paper award at the International Colloquium on Automata, Languages and Programming in 2004 from the European Association for Theoretical Computer Science.[4]

Williams’s result that the complexity class NEXP is not contained in ACC0 received the best paper award at the Conference on Computational Complexity in 2011.[5] Complexity theorist Scott Aaronson has called the result "one of the most spectacular of the decade".[6]

Williams is also an expert on the computational complexity of k-anonymity.[7]

Selected publications

  • Meyerson, Adam; Williams, Ryan (2004), "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, NY, USA: ACM, pp. 223–228, doi:10.1145/1055558.1055591, ISBN 158113858X 
  • Williams, R. (2005), "Better Time-Space Lower Bounds for SAT and Related Problems", IEEE Conference on Computational Complexity (CCC), pp. 40–49 
  • Williams, R. (2005), "A New Algorithm for Optimal 2-Constraint Satisfaction and Its Implications", Theoretical Computer Science, 348 (2-3): 357–365, doi:10.1016/j.tcs.2005.09.023 
  • Williams, R. (2008), "Time-Space Lower Bounds for Counting NP Solutions Modulo Integers", Computational Complexity, 17 (2): 179–219, doi:10.1007/s00037-008-0248-y 
  • Williams, R. (2011), "Non-Uniform ACC Circuit Lower Bounds", IEEE Conference on Computational Complexity (CCC) (PDF), pp. 115–125, doi:10.1109/CCC.2011.36 

References

  1. ↑ Ryan Williams at the Mathematics Genealogy Project
  2. ↑ Curriculum vitae, retrieved 2015-05-16.
  3. ↑ Proceedings of 20th Annual IEEE Conference on Computational Complexity (CCC'05) San Jose, CA June 11-June 15, ISBN 0-7695-2364-1, and Twenty-Second Annual IEEE Conference on Computational Complexity (CCC'07) San Diego, California, June 13-March 16, ISBN 0-7695-2780-9.
  4. ↑ "Best Student ICALP Paper". European Association for Theoretical Computer Science (EATCS).
  5. ↑ Program for CCC2011 at http://computationalcomplexity.org/
  6. ↑ Aaronson, Scott (November 8, 2010), "State of circuit lower bounds now slightly less humiliating", Technology Review, Massachusetts Institute of Technology.
  7. ↑ Meyerson & Williams (2004).
This article is issued from Wikipedia - version of the 11/14/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.