## Andrew C. Yao

Curriculum Vitae

Professor Yao's research activities
are in the design of efficient computer
algorithms, and
complexity theories in emerging new
areas of theoretical computer science,
such as quantum communication and
computing. He is investigating
new paradigms for designing fast
quantum algorithms, and mathematical
tools for the security analysis of
quantum cryptographic protocols.
Professor Yao is also interested
in exploring how far existing algorithms
are from the best possible, in terms
of the amount of computing resources
(such as running time) required.
He is studying this problem
within the framework of the Boolean
Circuit Model, in which computations
are performed by networks composed
of elementary logic gates. A concrete
goal is to show that certain natural
problems, such as the ``Traveling
Salesman's Problem,'' cannot be computed
by Boolean circuits of depth logarithmic
in its input lengths. Such results
would have much implications in computing
theory far beyond the circuit model
under which the results are derived.

Ph.D. in Physics, Harvard, 1972

Ph.D. in Computer Science, University of Illinois, 1975