Christopher B. Wilson

Associate Professor

Phone: (541) 346-3412

Education

BS, 1978, University of Oregon
MS, 1980, PhD, 1984, University of Toronto

Research Interests

Wilson's research addresses complexity classes derived from parallel computational models. These can be usefully compared to sequential classes to determine to what extent parallelism can be expected to speed up computations. In particular, he examines the classes NC and AC, which describe, in slightly different ways, the class of problems that can be solved very quickly in parallel using a reasonable amount of hardware. The main issues, such as whether NC differs from what can be computed in polynomial time sequentially, do not appear to be resolvable given the current state of the theory, much like the classical P versus NP question.

One approach has been to define relativized versions of these classes and then construct oracles that witness particular relationships among these classes. This approach indicates how these classes can be related in possible computational worlds and points out that only nonrelativizing proof techniques are able to finally resolve these questions. In a related issue he is trying to find a good measure of relativized space-bounded computation. This has been a surprisingly interesting and difficult area.

The difference between the NC and AC characterizations can be roughly expressed as that between the powers of exclusive and concurrent write on a PRAM. Wilson has examined the structure of the NC and AC hierarchies by applying a uniform decomposition technique to express any level of a hierarchy as a lower level with an oracle for another low level. From this it becomes possible to deduce certain structural properties of the hierarchies.

Wilson has also been examining the power of Boolean circuits that have a restriction placed on the number of negation gates they may contain. This creates what can be called a semimonotone circuit. There have been some recent results that would answer fundamental questions in complexity theory if they could be carried over to the nonmonotone case. Semimonotone circuits form a natural intermediate approach. Using these, Wilson has obtained a constructive and efficient version of a classical result of Markov.

Wilson's research has been funded by the National Science Foundation.

Selected Publications

Santha, M., and C. Wilson. 1991. Polynomial size constant depth circuits with a limited number of negations. Proceedings of the Eighth Symposium on Theoretical Aspects of Computer Science, Hamburg, Germany (February): 228--237.

Allender, E., and C. Wilson. 1990. Downward translations of equality. Theoretical Computer Science 75 (3): 335--346.

Wilson, C. 1990. On the decomposibility of NC and AC. SIAM Journal on Computing 19 (2): 384--396.

Wilson, C. 1988. A measure of relativized space which is faithful with respect to depth. Journal of Computer and System Sciences 36 (3): 303--312.

send feedback to: webmaster@cs.uoregon.edu