Biography
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