William Evans
Professor
Academic Information
Professor (since 2020), Associate Professor (2004-2020), Assistant Professor (2001-2004), University of British Columbia; Assistant Professor, University of Arizona (1996-2000); NSERC Postdoctoral Fellow, University of British Columbia (1994-1996); PhD Computer Science, University of California at Berkeley (1994); B.S. Computer Science, Yale University (1987).
Research Areas
Research Groups
Interests
My research interests are in the design of algorithms and the understanding of the fundamental limitations of various models of computation. I've pursued this interest in various areas of computer science:
* Graph Drawing - I study problems related to the geometric representation of graphs. For example, I'm interested in what graphs can be represented using contact or visibility between geometric objects, and how several graphs can be represented simultaneously using a shared set of objects.
* Algorithms that operate with uncertain input - What guarantees can an algorithm make if it knows that its input is uncertain but the uncertainty is bounded? How do we design and analyze algorithms that can gain more certainty at a price?
* Computational geometry - I'm interested in geometric problems or problems whose solution requires geometric techniques. I've been particularly interested in problems arising from geographic information systems. For example, problems in map drawing and concise surface (terrain) representation.
* Information theory - How is computation influenced by random noise? What price do you pay for using Boolean gates that produce the wrong output randomly with some small probability? I've been studying questions of this type using tools from information theory and computational complexity theory.
* Program compression - Software that is intended for palm-top computers, cell phones, and embedded controllers is getting more and more complicated, yet space, weight, price, and power consumption issues limit the amount of memory available to run this software. I'm interested in automatically reducing software's memory footprint without changing its function; essentially, exploring techniques that could be used in a very aggressive space-optimizing compiler. Software is also frequently downloaded across potentially slow network connections. I'm interested in how to represent and compress this software to reduce transmission time. In this case, I have the flexibility to choose a compressed form that may require decompression before execution.