1. Home
2.  > 
3. Academics
4.  > 
5. Faculty Bios
6.  > 
7. Science, Mathematics, and Computing Faculty
8.  > 
9. Aaron Williams

Aaron Williams

Areas of Specialization

• Theoretical Computer Science
• Discrete Mathematics

Interests

Research Interest: Algorithms, gray codes, de Bruijn sequences, computational complexity of video games, graph theory, combinatorics

Teaching Interest: Algorithms and data structures, discrete mathematics, artificial intelligences, programming languages, history of video games

Other Interests: Bicycling, travel, retro video games, jenga, Chromebooks 

Biography

PhD in Computer Science, University of Victoria
MMath in Combinatorics, University of Waterloo
BMath in Computer Science & BMath in Combinatorics, University of Waterloo

Dr. Williams has completed a series of postdocs including one in Computer Science at the University of Guelph with Joe Sawada in 2009, another in Mathematics at Carleton University with Brett Stevens in 2010-2011, and another in Mathematics at McGill University with Bruce Shepherd in 2012-2013. He has been teaching at Simon's Rock since 2014.

Highlights

Research with Students

• Buttons & Scissors is a popular puzzle app for both Android and iOS devices. The study of its difficulty (or "computational complexity") was initiated at Simon's Rock by students Harrison Gregg, Jody Leonard, and Aaron Santiago. This work eventually led to a joint publication with a dozen researchers from around the world.
• De Bruijn Sequences are classic objects in combinatorial mathematics with applications to computer science. Summer research with the student Oscar Hernandez led to a simple new algorithm for constructing de Bruijn sequences. This work was published and became the basis for Oscar’s senior thesis.

Media

• In 2009 Dr. Williams discovered a shortcoming in the FIFA World Cup tiebreaker rules. The flaw can lead to situations in which three different countries can argue that they logically deserve a top-2 position after the initial group stage. The story was picked up by the American Mathematical Society and was featured in various television and newspaper reports. The issue has not been resolved by FIFA (see FIFA 2018 rules Article 20.6     ) even though two soccer officials gave contradictory interpretations of the scenarios he had constructed.
• Dr. Williams helped prove that a simple generalized version of Super Mario Bros. is NP-complete. This result was published along with a new result establishing its PSPACE-completeness. Media attention included cursory coverage by Wired and Popular Science, and more in-depth coverage by MIT and other sources.

Publications

See ResearchGate for a full list of publications.